Graph embedding

From Wikipedia, the free encyclopedia

 This article or section is missing citations or needs footnotes.
Using inline citations helps guard against copyright violations and factual inaccuracies. (April 2008)

In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs (homeomorphic images of [0,1]) are associated to edges in such a way that:

  • the endpoints of the arc associated to an edge e are the points associated to the end vertices of e,
  • an arc include no 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, connected 2-manifold.

Often, an embedding is regarded as an equivalence class (under homeomorphisms of Σ) of representations of the kind just described.

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.

If a graph G is embedded on a closed surface Σ, the complement of the union of the points and arcs associated to the vertices and edges of G is a family of regions (or faces). A 2-cell embedding is an embedding in which every face is homeomorphic to an open disk. 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 is the minimal integer n such that the graph can be embedded in a surface of genus n. In particular, a planar graph has genus 0, because it can be drawn on a sphere without self-crossing.

The non-orientable genus of a graph is the minimal integer n such that the graph can be embedded in a non-orientable surface of (non-orientable) genus n.

Fixed-parameter tractable 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 genus of a graph. That is, although the problem is NP-complete when the genus is unbounded,[1] it can be solved in an amount of time that is linear in the graph size and doubly exponential in the genus.[2]

[edit] Embeddings of graphs of higher-dimensional manifolds

It is known that any graph can be embedded into a three-dimensional space. The idea is simple. Pick a line in the space and place the vertices of a graph along this line an any order. Draw as many planes through the line as there are edges in the graph and embed each edge into an individual plane.

The above special case of embedding is called book embedding of the graph. This metaphor comes from imagining that each of the planes where an edge is drawn is like a page of a book. It was observed that in fact several edges may be drawn in the same "page". This gave rise to the following problem:

Find a book embedding of a graph with minimal number of pages.

[edit] References

  1. ^ Thomassen, Carsten (1989), “The graph genus problem is NP-complete”, Journal of Algorithms 10 (4): 568–576, DOI 10.1016/0196-6774(89)90006-0 .
  2. ^ Mohar, Bojan (1999), “A linear time algorithm for embedding graphs in an arbitrary surface”, SIAM Journal on Discrete Mathematics 12 (1): 6–26, DOI 10.1137/S089548019529248X .

[edit] See also