nLab
planar graph

Contents

Definition

Planar graphs

A planar graph is a graph which may be embedded into a surface of genus 0 (such as a sphere or the Euclidean plane) without crossing edges.

Plane graphs/planar maps

Planarity is usually considered as a property of graphs, rather than as extra structure. When the structure reading is intended, this is sometimes referred to as a “plane graph” or “planar map”: that is, a graph equipped with an embedding into a genus 0 surface. In this sense, a planar graph is just a graph which is isomorphic to the underlying graph of a planar map. In particular, one graph might have multiple non-isomorphic embeddings into the plane, or it may be planar while also admitting embeddings into surfaces of higher genus (e.g., K 4K_4 is planar, but can also be embedded into the torus).

Properties

Existence of embeddings

The existence of an embedding of an arbitrary graph GG into a surface of genus 0 may be tested by various planarity criteria, such as Kuratowski’s theorem (GG is planar iff it does not contain a subgraph that is an edge subdivision of K 5K_5 or K 3,3K_{3,3}, closely related to Wagner’s theorem that this is the case iff K 5,K 3,3K_5, K_{3, 3} are not graph minors of GG) or Mac Lane’s planarity criterion (the cycle space? of GG has a basis such that no edge of GG appears in more than two basis vectors).

Related to the Kuratowski and Mac Lane characterizations is the matroid characterization of Hassler Whitney: a graph is planar iff its graphic matroid is dual to another graphic matroid.

References

Some related Wikipedia articles:

Early articles describing different planarity criteria:

  • Casimir Kuratowski (1930), “Sur le problème des courbes gauches en Topologie”, Fundamenta Mathematicae, 15 (1):271-283. eudml
  • Hassler Whitney (1932), “Non-separable and planar maps”, Transactions of the American Mathematical Society, 34 (2): 339–362. doi
  • Saunders Mac Lane (1937), “A combinatorial condition for planar graphs”, Fundamenta Mathematicae, 28 (1): 22–32. eudml

Last revised on January 23, 2018 at 13:36:23. See the history of this page for a list of all contributions to it.