# Graph embedding

In topological graph theory, an **embedding** (also spelled **imbedding**) of a graph on a surface Σ is a representation of 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 are the points associated to the end vertices of ,
- 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, connected 2-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 ^{[1]} and planar graphs can be embedded in 2-dimensional Euclidean space .

Often, an **embedding** is regarded as an equivalence class (under homeomorphisms of Σ) 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".^{[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".

## Terminology

If a graph is embedded on a closed surface Σ, the complement of the union of the points and arcs associated to
the vertices and edges of is a family of **regions** (or **faces**).^{[3]} A **2-cell embedding** or **map** is an embedding in which every face is homeomorphic to an open disk.^{[4]} 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*.^{[3]}

The **Euler genus** of a graph is the minimal integer *n* such that the graph can be embedded in an orientable surface of (orientable) genus *n/2* or in a non-orientable surface of (non-orientable) genus *n*. A graph is **orientably simple** if its Euler genus is smaller than its non-orientable genus.

The **maximum genus** of a graph is the maximal integer *n* such that the graph can be 2-cell embedded in an orientable surface of genus *n*.

## Combinatorial embedding

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. 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".^{[5]}^{[6]}^{[7]}

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.

## Computational complexity

The problem of finding the graph genus is NP-hard (the problem of determining whether an *n*-vertex graph has genus *g* is NP-complete).^{[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*(*n*^{O(g)}) were independently submitted to the Annual ACM Symposium on Theory of Computing: one by I. Filotti and 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.^{[9]}

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.^{[10]}

## Embeddings of graphs into higher-dimensional spaces

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. 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 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 *i*th vertex at the point (*i*,*i*^{2},*i*^{3}) 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.

## See also

- Embedding, for other kinds of embeddings
- Book thickness
- Geometric thickness
- Graph thickness
- Doubly connected edge list, a data structure to represent a graph embedding in the plane
- Regular map (graph theory)
- Fáry's theorem, which says that a straight line planar embedding of a planar graph is always possible.
- Triangulation (geometry)

## References

- 1 2 Cohen, Robert F.; Eades, Peter; Lin, Tao; Ruskey, Frank (1995), "Three-dimensional graph drawing", in Tamassia, Roberto; Tollis, Ioannis G.,
*Graph Drawing: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, October 10–12, 1994, Proceedings*, Lecture Notes in Computer Science,**894**, Springer, pp. 1–11, doi:10.1007/3-540-58950-3_351. - ↑ Katoh, Naoki; Tanigawa, Shin-ichi (2007), "Enumerating Constrained Non-crossing Geometric Spanning Trees",
*Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings*, Lecture Notes in Computer Science,**4598**, Springer-Verlag, pp. 243–253, doi:10.1007/978-3-540-73545-8_25, ISBN 978-3-540-73544-1. - 1 2 Gross, Jonathan; Tucker, Thomas W. (2001),
*Topological Graph Theory*, Dover Publications, ISBN 0-486-41741-7. - ↑ Lando, Sergei K.; Zvonkin, Alexander K. (2004),
*Graphs on Surfaces and their Applications*, Springer-Verlag, ISBN 3-540-00203-0. - ↑ Mutzel, Petra; Weiskircher, René (2000), "Computing Optimal Embeddings for Planar Graphs",
*Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings*, Lecture Notes in Computer Science,**1858**, Springer-Verlag, pp. 95–104, doi:10.1007/3-540-44968-X_10, ISBN 978-3-540-67787-1. - ↑ Didjev, Hristo N. (1995), "On drawing a graph convexly in the plane",
*Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings*, Lecture Notes in Computer Science,**894**, Springer-Verlag, pp. 76–83, doi:10.1007/3-540-58950-3_358. - ↑ Duncan, Christian; Goodrich, Michael T.; Kobourov, Stephen (2010), "Planar Drawings of Higher-Genus Graphs",
*Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers*, Lecture Notes in Computer Science,**5849**, Springer-Verlag, pp. 45–56, doi:10.1007/978-3-642-11805-0_7, ISBN 978-3-642-11804-3. - ↑ 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 - ↑ Filotti, I. S.; Miller, Gary L.; Reif, John (1979), "On determining the genus of a graph in O(v O(g)) steps(Preliminary Report)",
*Proc. 11th Annu. ACM Symposium on Theory of Computing*, pp. 27–37, doi:10.1145/800135.804395. - ↑ 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