Graph embedding
Encyclopedia
In topological graph theory
, an embedding 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:
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.
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".
This article deals only with the strict definition of graph embedding. The weaker definition is discussed in the articles "graph drawing
" and "crossing number
".
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). A 2-cell embedding or map 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.
. 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".
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.
(the problem of determining whether an n-vertex graph has genus g is NP-complete
).
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. 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.
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.
One method for doing this is to place the points on any line in space and to draw the m edges as curves each of which lies in one of m distinct 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 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.
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
.
Topological graph theory
In mathematics topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs....
, an embedding of a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
on a surfaceSurface
In mathematics, specifically in topology, a surface is a two-dimensional topological manifold. The most familiar examples are those that arise as the boundaries of solid objects in ordinary three-dimensional Euclidean space R3 — for example, the surface of a ball...
Σ is a representation of
on Σ in which points of Σ are associated to verticesGraph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
and simple arcs (homeomorphic images of [0,1]) are associated to edges
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
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
Compact space
In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...
, connected
Connected space
In topology and related branches of mathematics, a connected space is a topological space that cannot be represented as the union of two or more disjoint nonempty open subsets. Connectedness is one of the principal topological properties that is used to distinguish topological spaces...
2-manifold
Manifold
In mathematics , a manifold is a topological space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the 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.
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".
This article deals only with the strict definition of graph embedding. The weaker definition is discussed in the articles "graph drawing
Graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
" and "crossing number
Crossing number (graph theory)
In graph theory, the crossing number cr of a graph G is the lowest number of edge crossings of a planar drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero.The concept originated in...
".
Terminology
If a graph is embedded on a closed surface Σ, the complement of the union of the points and arcs associated tothe vertices and edges of
is a family of regions (or faces). A 2-cell embedding or map 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
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
is the minimal integer n such that the graph can be embedded in a surface of genus
Genus (mathematics)
In mathematics, genus has a few different, but closely related, meanings:-Orientable surface:The genus of a connected, orientable surface is an integer representing the maximum number of cuttings along non-intersecting closed simple curves without rendering the resultant manifold disconnected. It...
n. In particular, a planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
has genus 0, because it can be drawn on a sphere without self-crossing. The non-orientable genus of a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
is the minimal integer n such that the graph can be embedded in a non-orientable surface of (non-orientable) 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 systemRotation system
In combinatorial mathematics, rotation systems encode embeddings of graphs onto orientable surfaces, by describing the circular ordering of a graph's edges around each vertex....
. 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".
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-hardNP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
(the problem of determining whether an n-vertex graph has genus g is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
).
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
Time complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
O(nO(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
John Reif
John H. Reif is an American academics, and Professor of Computer Science at Duke University, who has made contributions to large number of fields in computer science: ranging from algorithms and computational complexity theory to robotics and to game theory.- Biography :John Reif received a B.S. ...
. Their approaches were quite different, but upon the suggestion of the program committee they presented a joint paper.
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.
Embeddings of graphs into higher-dimensional spaces
It is known that any graph can be embedded into a three-dimensional space.One method for doing this is to place the points on any line in space and to draw the m edges as curves each of which lies in one of m distinct 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
Book embedding
In graph theory, book embedding is a generalization of planar embedding to nonplanar surfaces in the form of a book, a collection of pages joined together at the spine of the book . The vertices of the graph are embedded on the spine, and each edge must lie in one of the pages...
of the graph. This metaphor
Metaphor
A metaphor is a literary figure of speech that uses an image, story or tangible thing to represent a less tangible thing or some intangible quality or idea; e.g., "Her eyes were glistening jewels." Metaphor may also be used for any rhetorical figures of speech that achieve their effects via...
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 graph can be drawn with straight-line edges in three dimensions without crossings by placing its vertices in general position
General position
In algebraic geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the general case situation, as opposed to some more special or coincidental cases that are possible...
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.
An embedding of a graph into three-dimensional space in which no two of the cycles are topologically linked is called a linkless embedding
Linkless embedding
In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into Euclidean space in such a way that no two cycles of the graph have nonzero linking number. A flat embedding is an embedding with the property that every cycle is the...
. A graph has a linkless embedding if and only if it does not have one of the seven graphs of the Petersen family
Petersen family
In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph K6. The Petersen family is named after Danish mathematician Julius Petersen, the namesake of the Petersen graph....
as a minor
Minor (graph theory)
In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
.
See also
- EmbeddingEmbeddingIn mathematics, an embedding is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup....
, 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)Regular map (graph theory)In mathematics, a regular map is a symmetric tessellation of a closed surface. More precisely, a regular map is a decomposition of a two-dimensional manifold such as a sphere, torus, or Klein bottle into topological disks, such that every flag can be transformed into any other flag by a symmetry...
- Fáry's theoremFáry's theoremIn mathematics, Fáry's theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn...
, which says that a straight line planar embedding of a planar graph is always possible.