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.
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). 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.
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].
Auslander, L. and Parter, S. "On Imbedding Graphs in the Sphere." J. Math. Mechanics10, 517-523, 1961.Battle,
J.; Harary, F.; and Kodama, Y. "Every Planar Graph with Nine Points has a Nonplanar
Complement." Bull. Amer. Math. Soc.68, 569-571, 1962.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.Bryant, V. W. "Straight
Line Representation of Planar Graphs." Elem. Math.44, 64-66,
1989.Cai, J.; Han, X.; and Tarjan, R. "New Solutions to Four Planar
Graph Problems." Technical Report. New York University, 1990.Di
Battista, G.; Eades, P.; Tamassia, R.; and Tollis, I. G. Graph
Drawing: Algorithms for the Visualization of Graphs. Englewood Cliffs, NJ:
Prentice-Hall, 1998.Eades, P. and Tamassia, R. "Algorithms for
Drawing Graphs: An Annotated Bibliography." Technical Report CS-89-09. Department
of Computer Science. Providence, RI: Brown University, Feb. 1989.Eppstein,
D. "Layered Graph Drawing." http://www.ics.uci.edu/~eppstein/junkyard/thickness/.Even,
Algorithms. Rockville, MD: Computer Science Press, 1979.Fáry,
I. "On Straight Line Representations of Planar Graphs." Acta Sci. Math.
(Szeged(11, 229-233, 1948.Gardner, M. The
Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University
of Chicago Press, pp. 91-94, 1984.Harary, F. "Planarity."
Ch. 11 in Graph
Theory. Reading, MA: Addison-Wesley, pp. 102-125, 1994.Harborth,
H. and Möller, M. "Minimum Integral Drawings of the Platonic Graphs."
Math. Mag.67, 355-358, 1994.Hopcroft, J. and Tarjan,
R. "Efficiency Planarity Testing." J. ACM21, 549-568, 1974.Karpov,
D. V. "Upper Bound on the Number of Edges of an Almost Planar Bipartite
Graph." 3 Jul 2013. https://arxiv.org/abs/1307.1013.Kocay,
W. and Pantel, C. "An Algorithm for Finding a Planar Layout of a Graph with
a Regular Polygon as Outer Face." Util. Math.48, 161-178, 1995.Le
Lionnais, F. Les
nombres remarquables. Paris: Hermann, p. 56, 1983.Nishizeki,
T. and Rahman, M. S. Planar
Graph Drawing. Singapore: World Scientific, 2004.Read, R. C.
"A New Method for Drawing a Planar Graph Given the Cyclic Order of the Edges
at Each Vertex." Congr. Numer.56, 31-44, 1987.Scheinerman,
E. and Wilf, H. S. "The Rectilinear Crossing Number of a Complete Graph
and Sylvester's 'Four Point' Problem of Geometric Probability." Amer. Math.
Monthly101, 939-943, 1994.Skiena, S. "Planar Graphs."
§6.5 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, pp. 247-253, 1990.Sloane, N. J. A.
Sequences A003094/M1652, A005470/M1252,
A049372, and A049373
in "The On-Line Encyclopedia of Integer Sequences."Steinbach,
Guide to Simple Graphs. Albuquerque, NM: Design Lab, 1990.Stony
Brook Algorithm Repository. §1.4.12. "Planarity Detection and Embedding."
S. "Coloring Planar Maps and Graphs." Ch. 24 in Mathematica
in Action, 2nd ed. New York: Springer-Verlag, pp. 507-537, 1999.West,
D. B. Introduction
to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 243,
2000.Whitney, H. "Non-Separable and Planar Graphs." Trans.
Amer. Math. Soc.34, 339-362, 1932.Whitney, H. "Planar
Graphs." Fund. Math.21, 73-84, 1933.Wilson, R. J.
to Graph Theory. London: Longman, 1975.