Planarity and Kuratowski’s Theorem
Jonathan L. Gross, Jay Yellen, Mark Anderson · 2018
This chapter focuses on the topological problem of deciding whether a graph can be drawn in the plane or sphere with no edge-crossings. It also provides some precise examples of a surface. What makes the plane and the sphere the simplest surfaces for drawing graphs is the Jordan separation property. A planar drawing of a graph is a drawing of the graph in the plane without edge-crossings. A standard way to construct a planar drawing of a graph is to draw a subgraph in the plane, and then to extend the drawing by adding the remaining parts of the graph. The chapter gives the terminology and some basic results about the planar extensions of a subgraph. These results are helpful in proving Kuratowski&s;s theorem and in specifying a planarity algorithm. One of the landmarks of graph theory is Kuratowski’s characterization of planarity in terms of two forbidden subgraphs.