Planar Graph

A graph is planar if it can be drawn in a plane without graph edges crossing (i.e., it has graph crossing number 0). The number of planar graphs with , 2, ... nodes 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, 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. Therfore, in this work, the term singlecross graph is introduced for such a graph. A graph with crossing (or rectilinear crossing) number 0 is planar by definition, a graph with crossing (or rectilinear crossing) number 1 is said to be singlecross, and a graph with crossing (or rectilinear crossing) number 2 is said to be doublecross.

Note that while graph planarity is an inherent property of a graph, it is still sometimes possible to draw nonplanar embeddings of planar graphs. For example, the two embeddings above both correspond to the planar tetrahedral graph, but while the left embedding is planar, the right embedding is not.

A planar embedding of a planar graph is sometimes called a planar embedding or plane graph (Harborth and Möller 1994). A planar straight line embedding of a graph can be made in the Wolfram Language using PlanarGraph[g].

There are a number of efficient algorithms for planarity testing, most of which are based on the algorithm of Auslander and Parter (1961; Skiena 1990, p. 247). 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). Any planar graph has a graph embedding as a planar straight line embedding where edges do not intersect (Fáry 1948; Bryant 1989; Skiena 1990, pp. 100 and 251; Scheinerman and Wilf 1994).

Only planar graphs have duals. If a finite simple graph is planar, 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 proved in 1930 that a graph is planar iff it does not contain within it any graph that is a graph expansion of the complete graph or .

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 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 minimal 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, ...

Planar Graph

Wolfram Web Resources