Graph embedding

Lore & Background

An embedded graph defines cyclic orders of edges at each vertex, called a rotation system; embeddings with the same rotation system form a combinatorial embedding. Face boundaries can be handled by splitting each edge into two half-edges. Other representations include ribbon graphs and graph-encoded maps. The problem of finding the graph genus is NP-hard, but fixed-parameter tractable; early algorithms by Filotti, Miller, and Reif were later found incorrect by Myrvold and Kocay.

Reader's Guide

Graph embedding is a central concept in topological graph theory, providing a rigorous framework for drawing graphs on surfaces without edge crossings. It underpins the classification of graphs by genus, distinguishing planar graphs (genus 0) from toroidal graphs (genus 1) and beyond. The distinction between topological and combinatorial embeddings allows both geometric and algebraic approaches to studying graph structure. The computational complexity of determining graph genus—NP-hard but fixed-parameter tractable—highlights the depth of the problem, with early algorithmic attempts later corrected. Embeddings also extend to higher dimensions, such as book embeddings and linkless embeddings in 3D space. The concept connects to practical data structures like doubly connected edge lists and to theoretical results like Fáry's theorem for planar straight-line embeddings. Overall, graph embedding bridges discrete mathematics, topology, and algorithm design.

Did You Know?

• Any finite graph can be embedded in 3-dimensional Euclidean space.
• A planar graph is one that can be embedded in 2-dimensional Euclidean space.
• The problem of determining whether an n-vertex graph has genus g is NP-hard, but it is not known to be in NP when g is part of the input, so it is not known to be NP-complete.
• A graph has a linkless embedding in 3D if and only if it does not have one of the seven graphs of the Petersen family as a minor.