HOME

TheInfoList



OR:

In topological graph theory, an embedding (also spelled imbedding) of a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...
G on a
surface A surface, as the term is most generally used, is the outermost or uppermost layer of a physical object or space. It is the portion or region of the object that can first be perceived by an observer using the senses of sight and touch, and is ...
\Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (
homeomorphic In mathematics and more specifically in topology, a homeomorphism ( from Greek roots meaning "similar shape", named by Henri Poincaré), also called topological isomorphism, or bicontinuous function, is a bijective and continuous function betw ...
images of ,1/math>) are associated with edges in such a way that: * the endpoints of the arc associated with an edge e are the points associated with the end vertices of e, * 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 connected 2-
manifold In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a N ...
. 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 \mathbb^3.. A
planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
is one that can be embedded in 2-dimensional Euclidean space \mathbb^2. Often, an embedding is regarded as an equivalence class (under homeomorphisms of \Sigma) 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 is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such ...
" and " crossing number".


Terminology

If a graph G is embedded on a closed surface \Sigma, the complement of the union of the points and arcs associated with the vertices and edges of G is a family of regions (or
face The face is the front of the head that features the eyes, nose and mouth, and through which animals express many of their emotions. The face is crucial for human identity, and damage such as scarring or developmental deformities may affect th ...
s).. A 2-cell embedding, cellular 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 may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...
is the minimal integer n such that the graph can be embedded in a surface of
genus Genus (; : genera ) is a taxonomic rank above species and below family (taxonomy), family as used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In bino ...
n. In particular, a
planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), 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. A graph that can be embedded on a
torus In geometry, a torus (: tori or toruses) is a surface of revolution generated by revolving a circle in three-dimensional space one full revolution about an axis that is coplanarity, coplanar with the circle. The main types of toruses inclu ...
is called a toroidal graph. The non-orientable genus of a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...
is the minimal integer n such that the graph can be embedded in a non-orientable surface of (non-orientable) genus n. 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 Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...
is the maximal integer n such that the graph can be 2-cell embedded in an orientable surface of
genus Genus (; : genera ) is a taxonomic rank above species and below family (taxonomy), family as used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In bino ...
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". 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. 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.


Computational complexity

The problem of finding the graph genus is
NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
(the problem of determining whether an n-vertex graph has genus g is
NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
). At the same time, the graph genus problem is fixed-parameter tractable, i.e.,
polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
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 In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
''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. However, Wendy Myrvold and William Kocay proved in 2011 that the algorithm given by Filotti, Miller and Reif was incorrect. In 1999 it was reported that the fixed-genus case can be solved in time
linear In mathematics, the term ''linear'' is used in two distinct senses for two different properties: * linearity of a '' function'' (or '' mapping''); * linearity of a '' polynomial''. An example of a linear function is the function defined by f(x) ...
in the graph size and doubly exponential in the genus.


Embeddings of graphs into higher-dimensional spaces

It is known that any finite 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 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 A metaphor is a figure of speech that, for rhetorical effect, directly refers to one thing by mentioning another. It may provide, or obscure, clarity or identify hidden similarities between two different ideas. Metaphors are usually meant to cr ...
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.


Gallery

File:Petersen-graph.png, The
Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph i ...
and associated map embedded in the projective plane. Opposite points on the circle are identified yielding a closed surface of non-orientable genus 1. File:Pappus-graph-on-torus.png, The Pappus graph and associated map embedded in the torus. File:Klein-map.png, The degree 7 Klein graph and associated map embedded in an orientable surface of genus 3.


See also

*
Embedding In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group (mathematics), group that is a subgroup. When some object X is said to be embedded in another object Y ...
, for other kinds of embeddings * Book thickness * Graph thickness * Doubly connected edge list, a data structure to represent a graph embedding in the plane *
Regular map (graph theory) In mathematics, a regular map is a symmetric tessellation of a closed surface (topology), surface. More precisely, a regular map is a Manifold decomposition, decomposition of a two-dimensional manifold (such as a sphere, torus, or real project ...
*
Fáry's theorem In the mathematical field of graph theory, Fáry's theorem states that any simple graph, simple, planar graph can be Graph drawing, drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as ...
, which says that a straight line planar embedding of a planar graph is always possible. *
Triangulation (geometry) In geometry, a triangulation is a subdivision of a plane (geometry), planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplex, simplices. Triangulations of a three-dimensional volume would ...


References

{{reflist Topological graph theory Graph algorithms