Concept

Graph embedding

Summary
In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (homeomorphic images of [0,1]) 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 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. It is well known that any finite graph can be embedded in 3-dimensional Euclidean space \mathbb{R}^3. A planar graph is one that
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.
Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading