Content deleted Content added
→Combinatorial embedding: Other equivalent representations |
m Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4 |
||
| (30 intermediate revisions by 19 users not shown) | |||
Line 1:
{{Use American English|date = February 2019}}
{{Short description|Embedding a graph in a topological space, often Euclidean}}
{{Use mdy dates|date = February 2019}}
[[File:Heawood graph and map on torus.png|thumb|The [[Heawood graph]] and associated map embedded in the torus.]]
In [[topological graph theory]], an '''embedding''' (also spelled '''imbedding''') of a [[Graph (discrete mathematics)|graph]] <math>G</math> on a [[surface (mathematics)|surface]] <math>\Sigma</math> is a representation of <math>G</math> on <math>\Sigma</math> in which points of <math>\Sigma</math> are associated with [[graph theory|vertices]] and simple arcs ([[Homeomorphism|homeomorphic]] images of <math>[0,1]</math>) are associated with [[graph theory|edges]] in such a way that:
* the endpoints of the arc associated with an edge <math>e</math> are the points associated with the end vertices of <math>e,</math>
* no arcs include points associated with other vertices,
* two arcs never intersect at a point which is interior to either of the arcs.
Here a surface is a
Informally, an embedding of a graph into a surface is a drawing of the graph on the surface in such a way that its edges may intersect only at their endpoints. It is well known that any finite graph can be embedded in 3-dimensional Euclidean space <math>\mathbb{R}^3</math>.<ref name="3d-gd">{{citation
| last1 = Cohen | first1 = Robert F.
| last2 = Eades | first2 = Peter | author2-link = Peter Eades
Line 19 ⟶ 26:
| 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
| doi-access = free }}.</ref> 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
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 29 ⟶ 38:
==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. A graph that can be embedded on a [[torus]] is called a [[toroidal graph]].
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"/> The '''Euler genus''' of a graph is the minimal integer <math>n</math> such that the graph can be embedded in an orientable surface of (orientable) genus <math>n/2</math> or in a non-orientable surface of (non-orientable) genus <math>n</math>. A graph is '''orientably simple''' if its Euler genus is smaller than its non-orientable genus.
Line 39 ⟶ 50:
==Combinatorial embedding==
{{main|Rotation system}}
An embedded graph uniquely defines [[cyclic order
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 47 ⟶ 58:
==Computational complexity==
The problem of finding the graph genus is [[NP-hard]] (the problem of determining whether an <math>n</math>-vertex graph has genus <math>g</math> is [[NP-complete]]).<ref>{{Citation | last1=Thomassen | first1=Carsten | authorlink = Carsten Thomassen (mathematician) | title=The graph genus problem is NP-complete | year=1989 | journal=Journal of Algorithms | volume=10 | issue = 4 | pages=568–576 | doi = 10.1016/0196-6774(89)90006-0}}</ref>
At the same time, the graph genus problem is [[Fixed-parameter tractability|fixed-parameter tractable]], i.e.,
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
==Embeddings of graphs into higher-dimensional spaces==
It is known that any finite graph can be embedded into a three-dimensional space.<ref name="3d-gd"/>
One method for doing this is to place the points on any line in space and to draw the edges as curves each of which lies in a distinct [[halfplane]], with all halfplanes having that line as their common boundary. An embedding like this in which the edges are drawn on halfplanes is called a [[book embedding]] of the graph. This [[metaphor]] comes from imagining that each of the
Alternatively, any finite graph can be drawn with straight-line edges in three dimensions without crossings by placing its vertices in [[general position]] so that no four are coplanar. For instance, this may be achieved by placing the ''i''th vertex at the point (''i'',''i''<sup>2</sup>,''i''<sup>3</sup>) of the [[moment curve]].
An embedding of a graph into three-dimensional space in which no two of the cycles are topologically linked is called a [[linkless embedding]]. A graph has a linkless embedding if and only if it does not have one of the seven graphs of the [[Petersen family]] as a [[minor (graph theory)|minor]].
==Gallery==
<gallery>
File:Petersen-graph.png|The [[Petersen graph]] and associated map embedded in the projective plane. Opposite points on the circle are identified yielding a closed surface of non-orientable genus 1.
File:Pappus-graph-on-torus.png|The [[Pappus graph]] and associated map embedded in the torus.
File:Klein-map.png|The degree 7 [[Klein graph]] and associated map embedded in an orientable surface of genus 3.
</gallery>
==See also==
| |||