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).