# nLab planar graph

Contents

### Context

#### Graph theory

graph theory

graph

category of simple graphs

# 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_4$ is planar, but can also be embedded into the torus).

## Properties

### Existence of embeddings

The existence of an embedding of an arbitrary graph $G$ into a surface of genus 0 may be tested by various planarity criteria, such as Kuratowski’s theorem ($G$ is planar iff it does not contain a subgraph that is an edge subdivision of $K_5$ or $K_{3,3}$, closely related to Wagner’s theorem that this is the case iff $K_5, K_{3, 3}$ are not graph minors of $G$) or Mac Lane’s planarity criterion (the cycle space? of $G$ has a basis such that no edge of $G$ 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.