Planar Graph

A Graph is planar if it can be drawn in a Plane without Edges crossing (i.e., it has Crossing Number 0). Only planar graphs have Duals. If $G$ is planar, then $G$ has Vertex Degree $\leq 5$. Complete Graphs are planar only for $n\leq 4$. The complete Bipartite Graph $K(3,3)$ in nonplanar. More generally, Kuratowski proved in 1930 that a graph is planar Iff it does not contain within it any graph which can be Contracted to the pentagonal graph $K(5)$ or the hexagonal graph $K(3,3)$. $K_5$ can be decomposed into a union of two planar graphs, giving it a ``Depth'' of $E(K_5)=2$. Simple Criteria for determining the depth of graphs are not known. Beineke and Harary (1964, 1965) have shown that if $n\not\equiv 4$ (mod 6), then

$$E(K_n)=\left\lfloor{{\textstyle{1\over 6}}(n+7)}\right\rfloor .$$

The Depths of the graphs $K_n$ for $n=4$, 10, 22, 28, 34, and 40 are 1, 3, 4, 5, 6, and 7 (Meyer 1970).

See also Complete Graph, Fabry Imbedding, Integral Drawing, Planar Straight Line Graph

References

Beineke, L. W. and Harary, F. ``On the Thickness of the Complete Graph.'' Bull. Amer. Math. Soc. 70, 618-620, 1964.

Beineke, L. W. and Harary, F. ``The Thickness of the Complete Graph.'' Canad. J. Math. 17, 850-859, 1965.

Booth, K. S. and Lueker, G. S. ``Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity using PQ-Tree Algorithms.'' J. Comput. System Sci. 13, 335-379, 1976.

Le Lionnais, F. Les nombres remarquables. Paris: Hermann, p. 56, 1983.

Meyer, J. ``L'épaisseur des graphes completes $K_{34}$ et $K_{40}$.'' J. Comp. Th. 9, 1970.