Graph embedding
It is well known that any finite graph can be embedded in 3-dimensional Euclidean space
[1] A planar graph is one that can be embedded in 2-dimensional Euclidean space
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".
[2] This article deals only with the strict definition of graph embedding.
The weaker definition is discussed in the articles "graph drawing" and "crossing number".
, the complement of the union of the points and arcs associated with the vertices and edges of
An embedded graph uniquely defines cyclic orders of edges incident to the same vertex.
The set of all these cyclic orders is called a rotation system.
However handling these face-based orders is less straightforward, since in some cases some edges may be traversed twice along a face boundary.
To overcome this combinatorial nuisance, one may consider that every edge is "split" lengthwise in two "half-edges", or "sides".
Other equivalent representations for cellular embeddings include the ribbon graph, a topological space formed by gluing together topological disks for the vertices and edges of an embedded graph, and the graph-encoded map, an edge-colored cubic graph with four vertices for each edge of the embedded graph.
[8] At the same time, the graph genus problem is 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.
The first breakthrough in this respect happened in 1979, when algorithms of time complexity O(nO(g)) were independently submitted to the Annual ACM Symposium on Theory of Computing: one by I. Filotti and G.L.
Their approaches were quite different, but upon the suggestion of the program committee they presented a joint paper.
[9] However, Wendy Myrvold and William Kocay proved in 2011 that the algorithm given by Filotti, Miller and Reif was incorrect.
[10] In 1999 it was reported that the fixed-genus case can be solved in time linear in the graph size and doubly exponential in the genus.
[11] It is known that any finite graph can be embedded into a three-dimensional space.
[1] 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.
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"; the book thickness of the graph is the minimum number of halfplanes needed for such a drawing.
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 ith vertex at the point (i,i2,i3) of the moment curve.
