Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Graph embedding
Summary
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 with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that:
the endpoints of the arc associated with an edge are the points associated with 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 -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 . A planar graph is one that 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".
This article deals only with the strict definition of graph embedding. The weaker definition is discussed in the articles "graph drawing" and "crossing number".
If a graph is embedded on a closed surface , the complement of the union of the points and arcs associated with
the vertices and edges of is a family of regions (or faces). 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 is the minimal integer such that the graph can be embedded in a surface of genus . In particular, a planar graph has genus , because it can be drawn on a sphere without self-crossing. A graph that can be embedded on a torus is called a toroidal graph.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.