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.
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., is planar, but can also be embedded into the torus).
The existence of an embedding of an arbitrary graph into a surface of genus 0 may be tested by various planarity criteria, such as Kuratowski’s theorem ( is planar iff it does not contain a subgraph that is an edge subdivision of or , closely related to Wagner’s theorem that this is the case iff are not graph minors of ) or Mac Lane’s planarity criterion (the cycle space? of has a basis such that no edge of 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.
Some related Wikipedia articles:
Early articles describing different planarity criteria:
Last revised on January 23, 2018 at 18:36:23. See the history of this page for a list of all contributions to it.