Content deleted Content added
Short description |
Citation bot (talk | contribs) m Alter: isbn, title, page. Add: title-link, citeseerx, isbn. Formatted dashes. | You can use this bot yourself. Report bugs here. | User-activated. |
||
Line 24:
| title = Graph Drawing: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, October 10–12, 1994, Proceedings
| volume = 894
| year = 1995| isbn = 978-3-540-58950-1
}}.</ref> and [[planar graphs]] can be embedded in 2-dimensional Euclidean space <math>\mathbb{R}^2.</math> Often, an '''embedding''' is regarded as an equivalence class (under homeomorphisms of <math>\Sigma</math>) of representations of the kind just described.
Some authors define a weaker version of the definition of "graph embedding" by omitting the non-intersection condition for edges. In such contexts the stricter definition is described as "non-crossing graph embedding".<ref>{{citation|first1=Naoki|last1=Katoh|first2=Shin-ichi|last2=Tanigawa|title=Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings|publisher=Springer-Verlag|series=[[Lecture Notes in Computer Science]]|volume=4598|year=2007|pages=243–253|doi=10.1007/978-3-540-73545-8_25|chapter=Enumerating Constrained Non-crossing Geometric Spanning Trees|isbn=978-3-540-73544-1|citeseerx=10.1.1.483.874}}.</ref>
This article deals only with the strict definition of graph embedding. The weaker definition is discussed in the articles "[[graph drawing]]" and "[[Crossing number (graph theory)|crossing number]]".
Line 34 ⟶ 35:
==Terminology==
If a graph <math>G</math> is embedded on a closed surface <math>\Sigma</math>, the complement of the union of the points and arcs associated with
the vertices and edges of <math>G</math> is a family of '''regions''' (or '''[[face (graph theory)|face]]s''').<ref name="gt01">{{citation|last1=Gross|first1=Jonathan|last2=Tucker|first2=Thomas W.|authorlink2= Thomas W. Tucker| title=Topological Graph Theory|publisher=Dover Publications|year=2001|isbn=978-0-486-41741-7}}.</ref> A '''2-cell embedding''', '''cellular embedding''' or '''map''' is an embedding in which every face is homeomorphic to an open disk.<ref>{{citation|last1=Lando|first1=Sergei K.|last2=Zvonkin|first2=Alexander K.|title=Graphs on Surfaces and their Applications|publisher=Springer-Verlag|year=2004|isbn=978-3-540-00203-
The '''genus''' of a [[Graph (discrete mathematics)|graph]] is the minimal integer <math>n</math> such that the graph can be embedded in a surface of [[Genus (mathematics)|genus]] <math>n</math>. In particular, a [[planar graph]] has genus <math>0</math>, because it can be drawn on a sphere without self-crossing. The '''non-orientable genus''' of a [[Graph (discrete mathematics)|graph]] is the minimal integer <math>n</math> such that the graph can be embedded in a non-orientable surface of (non-orientable) genus <math>n</math>.<ref name="gt01"/>
Line 44 ⟶ 45:
==Combinatorial embedding==
{{main|Rotation system}}
An embedded graph uniquely defines [[cyclic order|cyclic orders]] of edges incident to the same vertex. The set of all these cyclic orders is called a [[rotation system]]. Embeddings with the same rotation system are considered to be equivalent and the corresponding equivalence class of embeddings is called '''combinatorial embedding''' (as opposed to the term '''topological embedding''', which refers to the previous definition in terms of points and curves). Sometimes, the rotation system itself is called a "combinatorial embedding".<ref>{{citation|first1=Petra|last1=Mutzel|author1-link=Petra Mutzel|first2=René|last2=Weiskircher|title=Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings|year=2000|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=1858|pages=95–104|doi=10.1007/3-540-44968-X_10|chapter=Computing Optimal Embeddings for Planar Graphs|isbn=978-3-540-67787-1}}.</ref><ref>{{citation|last=Didjev|first=Hristo N.|contribution=On drawing a graph convexly in the plane|title=
An embedded graph also defines natural cyclic orders of edges which constitutes the boundaries of the faces of the embedding. However handling these face-based orders is less straightforward, since in some cases some edges may be traversed twice along a face boundary. For example this is always the case for embeddings of trees, which have a single face. To overcome this combinatorial nuisance, one may consider that every edge is "split" lengthwise in two "half-edges", or "sides". Under this convention in all face boundary traversals each half-edge is traversed only once and the two half-edges of the same edge are always traversed in opposite directions.
Line 57 ⟶ 58:
The first breakthrough in this respect happened in 1979, when algorithms of [[time complexity]]
''O''(''n''<sup>''O''(''g'')</sup>) were independently submitted to the Annual [[ACM Symposium on Theory of Computing]]: one by I. Filotti and [[Gary Miller (computer scientist)|G.L. Miller]] and another one by [[John Reif]]. Their approaches were quite different, but upon the suggestion of the program committee they presented a joint paper.<ref>{{citation|first1=I. S.|last1=Filotti|author2-link=Gary Miller (computer scientist)|first2=Gary L.|last2=Miller|first3=John|last3=Reif|author3-link=John Reif |title=
In 1999 it was reported that the fixed-genus case can be solved in time [[linear time|linear]] in the graph size and [[Double exponential function|doubly exponential]] in the genus.<ref>{{Citation | last1=Mohar | first1=Bojan | authorlink = Bojan Mohar | title=A linear time algorithm for embedding graphs in an arbitrary surface | year=1999 | journal=[[SIAM Journal on Discrete Mathematics]] | volume=12 | issue=1 | pages=6–26 | doi = 10.1137/S089548019529248X| citeseerx=10.1.1.97.9588 }}</ref>
| |||