Drawing graphs in the plane
Jiřı́ Matoušek, Jaroslav Nešetřil · 1998
Abstract Often it is advantageous to draw graphs. As you can see, most of the graphs in this book are specified by a picture (instead of a list of vertices and edges, say). But so far we have been studying properties of graphs not related to their drawings, and the role of drawings was purely auxiliary. In this chapter the subject of analysis will be the drawing of graphs itself and we will mainly investigate graphs that can be drawn in the plane without edge crossings. Such graphs are called planar. From the numerous pictures shown so far and from the informal definition given in Section 3.1, the reader might have gained a quite good intuition about what is meant by a drawing of a graph. Such an intuition is usually sufficient if we want to show, say, that some graph is planar-we can simply draw a suitable picture of the graph with no edge crossings. However, if we want to prove, in a strictly logical way, that some graph is not planar, then we cannot do without a mathematical definition of the notion of a drawing, based on other exact mathematical notions. Today’s mathematics is completely built from a few primitive notions and axioms of set theory-or at least the majority of mathematicians try to ensure it is.