Graph embedding

Graph embedding is a way of drawing graphs on different surfaces so that the edges only meet at their endpoints. In topological graph theory, an embedding of a graph means placing the points of the graph, called vertices, on a surface and connecting them with lines, called edges, without any edges crossing except at these points.

A surface can be any connected space, like a flat piece of paper or a sphere. For example, a planar graph can be drawn on a flat surface without any edges crossing. But some graphs need more complex surfaces, like a sphere or a torus, to avoid crossings.

Embeddings help us understand the properties of graphs and are important in many areas, such as computer science and mathematics. They show how graphs can be represented in space and help solve problems about connections and networks.

Terminology

When we draw a graph on a surface like a sphere or a donut, we call this an embedding. The empty spaces around the graph on the surface are called faces. A special kind of embedding, called a 2-cell embedding, makes every face look like an open disk, like a flat piece of paper with no holes.

We can describe how "twisty" a graph is by its genus. A simple flat graph, like one you can draw on paper without lines crossing, has a genus of 0. If a graph can be drawn on a donut shape without lines crossing, it is called a toroidal graph. There are also ways to describe embeddings on different kinds of surfaces, which help us understand the graph’s properties better.

Combinatorial embedding

Main article: Rotation system

When we draw a graph on a surface, we can describe how the edges meet at each vertex in a circle. This circle of edges is called a rotation system. If two drawings of a graph have the same rotation systems, we consider them to be the same type of drawing. This type of drawing is called a combinatorial embedding.

We can also look at how edges form the edges of areas, or "faces," in the drawing. Sometimes, an edge might be used twice to form a face. To make this easier to study, we can think of each edge as two "half-edges." This way, each half-edge is only used once when we walk around a face. There are also other ways to represent these drawings, like using special graphs called ribbon graphs or graph-encoded maps.

Computational complexity

Figuring out how complex a graph is — called finding its genus — is very hard and is known to be NP-hard. This means there’s no quick way to know for sure for big graphs.

But there are smart ways to solve it if you know the genus beforehand. In 1979, researchers found better methods, though some later turned out to have mistakes. By 1999, scientists showed they could solve it quickly for small genus values.

Embeddings of graphs into higher-dimensional spaces

Any finite graph can be shown in three-dimensional space. One way to do this is by placing points on a line and drawing the edges as curves in different halfplanes, like pages in a book. This is called a book embedding, and the book thickness is how many halfplanes are needed.

Another method uses straight lines to connect points placed in general position, meaning no four points lie on the same flat surface. An embedding where graph cycles aren’t linked like chains is called a linkless embedding. A graph can have this type of embedding if it doesn’t include certain graphs from the Petersen family as smaller parts.