Planar Graph

A planar graph is a graph that can be drawn in a plane without graph edges crossing (i.e., it has graph crossing number 0). The numbers of planar simple graphs, counted up to graph isomorphism, with , 2, ... vertices are 1, 2, 4, 11, 33, 142, 822, 6966, 79853, ... (OEIS A005470; Wilson 1975, p. 162), the first few of which are illustrated above.

The corresponding numbers of planar connected graphs are 1, 1, 2, 6, 20, 99, 646, 5974, 71885, ... (OEIS A003094; Steinbach 1990, p. 131).

There appears to be no term in standard use for a graph with graph crossing number 1. In particular, the terms "almost planar" and "1-planar" are used in the literature for other concepts (e.g., Karpov 2013). Therefore, in this work, the term singlecross graph is introduced for such a graph. A graph with graph crossing number (or rectilinear crossing number) 0 is planar by definition, a graph with graph crossing number (or rectilinear crossing number) 1 is said to be singlecross, and a graph with graph crossing number (or rectilinear crossing number) 2 is said to be doublecross (Bienstock and Dean 1993).

A planar graph is defined by the existence of a crossing-free drawing, although another drawing of the same graph may have crossings. The two drawings above both represent the tetrahedral graph. The left drawing is a planar graph embedding, whereas the additional edge intersections in the right drawing prevent it from being an embedding in the topological sense.

A graph together with a planar graph embedding is called a plane graph (Harborth and Möller 1994). The Fáry theorem states that any simple planar graph can be drawn in a planar straight line embedding (Fáry 1948; Bryant 1989; Skiena 1990, pp. 100 and 251; Scheinerman and Wilf 1994). A planar straight line embedding of a planar graph can be made in the Wolfram Language using PlanarGraph[g].

Planarity can be tested in linear time and space using the algorithm of Hopcroft and Tarjan (1974). A graph may be tested for planarity in the Wolfram Language using the command PlanarGraphQ[g].

A graph is planar iff it has a combinatorial dual graph (Harary 1994, p. 115).

If a nonempty finite graph is a planar simple graph, then has at least one vertex degree . If both graph and its graph complement are planar, then has eight or fewer vertices.

Complete graphs are planar only for . The complete bipartite graph is nonplanar. More generally, Kuratowski's theorem (Kuratowski 1930) states that a finite graph is planar iff it does not contain a graph subdivision of or as a subgraph.

There are a number of measures characterizing the degree by which a graph fails to be planar, among these being the graph crossing number, rectilinear crossing number, graph skewness, graph coarseness, and graph thickness.

A graph with graph thickness 1 is planar, while a graph with graph thickness 1 or 2 is said to be biplanar. A nonplanar apex graph is a nonplanar graph possessing at least one vertex whose removal results in a planar graph.

All trees are planar, as is a cycle graph, grid graph, or wheel graph. Every planar graph on nine vertices has a nonplanar complement (Battle et al. 1962; Skiena 1990, p. 250).

The following table gives the numbers of planar graphs having minimum vertex degrees of at least .

	OEIS	, 2, 3, ...
2	A049370	0, 0, 1, 3, 10, 50, 335, ...
3	A049371	0, 0, 0, 1, 2, 9, 46, 386, ...
4	A049372	0, 0, 0, 0, 0, 1, 1, 4, 14, 69, ...
5	A049373	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 5, ...