Graph embedding: Difference between revisions

Revision as of 15:18, 29 May 2017

Revision as of 14:51, 2 August 2017

Line 1:

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 [[compact space|compact]], [[connected space|connected]] <math>2</math>-[[manifold]].

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

Line 21:

| year = 1995}}.</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}}.</ref>

Line 28:

==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=0-486-41741-7}}.</ref> A '''2-cell 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=3-540-00203-0}}.</ref> A '''closed 2-cell embedding''' is an embedding in which the closure of every face is homeomorphic to a closed disk.

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"/>

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.

The '''maximum genus''' of a [[Graph (discrete mathematics)|graph]] is the maximal integer ''<math>n''</math> such that the graph can be <math>2</math>-cell embedded in an orientable surface of [[Genus (mathematics)|genus]] ''<math>n''</math>.

==Combinatorial embedding==

Line 45:

==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 | 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., [[polynomial time]] algorithms are known to check whether a graph can be embedded into a surface of a given fixed genus as well as to find the embedding.