Graph embedding

From Polytope Wiki
Jump to navigation Jump to search

A graph embedding is a way to draw a graph on a surface without edges intersecting.

Definition[edit | edit source]

The embedding of a graph G  on a connected, manifold consists of two mappings. The first mapping the vertices of G  to points on injectively, that is no two vertices map to the same point. The second mapping, , maps the edges of G  to arcs on the surface of . An arc is a subset of which is homeomorphic to .

The two mappings are required

  • If vertex v  is incident on edge e , then is an endpoint of , that is there is a homeomorphism such that .
  • If vertex v  is not incident on edge e , then .
  • If then and do not intersect anywhere other than their endpoints.

Planar graphs[edit | edit source]

A graph is planar if there is an embedding of it onto the plane.

Dual graphs[edit | edit source]

Two graphs embedded in the plane. The red graph embedding (dotted edges) is the dual of the blue graph embedding (solid edges).

A graph embedding gives rise to a dual embedding. If we have an embedding of a graph G  on a manifold M  then the edges divide M  up into connected components called "faces". The dual embedding places one vertex in each face and an edge between two vertices if and only if their faces share an edge. This dual graph may be a multigraph with self loops, even if G  is simple.

The dual operation is symmetric (up to isotopy), meaning that if A  is the dual of B  then B  is also the dual of A .

The dual is a property of embeddings not graphs. Different embeddings of the same graph may have different duals.

The dual graph is related to the polytope dual. The dual graph of the skeleton of a convex polyhedron is the same as the skeleton of its polytope dual.

See also[edit | edit source]

External links[edit | edit source]