planar graph (original) (raw)

\xyoption

all

Description

A planar graph is a graph which can be drawn on a plane (a flat 2-d surface) or on a sphere, with no edges crossing. When drawn on a sphere, the edges divide its area in a number of regions called faces (or “countries”, in the context of map coloring). When drawn on a plane, there is one outer country taking up all the space outside the drawing. Every graph drawn on a sphere can be drawn on a plane (puncture the sphere in the interior of any one of the countries) and vice versa. Statements on map coloring are often simpler in terms of a spherical map because the outer country is no longer a special case.

The number of faces (countries) equals c+1 where c is the cyclomatic number, c=m-n+k (where m is the number of edges, n the number of vertices, and k the number of connected components of the graph). All this holds equally for planar multigraphs and pseudographs.

No complete graphs above K4 are planar. K4, drawn without crossings, looks like :

Hence it is planar (try this for K5.)

A drawing of a planar graph is a drawing in which each edge is drawn as a line segment. Every planar graph has a drawing. This result was found independently by Wagner, Fáry and Stein. Schnyder improved this further by showing how to draw any planar graph with n vertices on an integer grid of O⁢(n2) area.

Definition

Ideally, this definition would just formalize what was described above. It will not, exactly. It will formalize the notion of a graph with an embedding into the plane.

Definition.

A planar graph is a graph G that has an embedding ι making (G,ι) into a plane graph.

Normally, the only manifolds M that are of interest are two-dimensional.

The most usual question for which this definition finds a use is “can the following graph G be made into a graph on M?”. When M is the plane, this is usually phrased as “Is G a planar graph?”. Wagner’s theorem provides a criterion for answering this question. When M is a torus, the answer changes: the complete bipartite graph K3,3 can be made into a graph on the torus.

A graph on a manifold has a notion of “face” as well as the usual graph notions of vertex and edge.