A circuit board makes graph layout concrete: components become vertices and conductive tracks become edges. Crossed tracks can complicate a layout, just as crossed lines make a flow chart harder to follow. The first question is whether crossings are unavoidable or merely a result of how the graph was drawn. section 15.0 section 15.1
A planar graph is an abstract graph that has at least one planar embedding: a drawing in the plane with no edge crossing or edge passing through an unrelated vertex. The resulting drawing is a plane graph. Vertices occupy points in two-dimensional space; edges may be drawn as suitable curves, not just straight segments. A drawing with crossings therefore does not, by itself, prove that its graph is non-planar. section 15.1.1 section 15.2
To decide what kind of layout to attempt:
- First apply cheap rejection checks. For a simple, connected graph with at least three vertices, planarity requires |E| ≤ 3|V| − 6. If it also has more than three vertices and no triangles, it requires |E| ≤ 2|V| − 4. Failing either check proves non-planarity; passing does not prove planarity. section 15.2.2
- If the checks pass, use a planarity-testing algorithm rather than judging one drawing. Kuratowski’s characterization rules out graphs containing a subdivision of K5 or K3,3, but is less convenient as an implementation strategy. Linear-time algorithms include the edge-addition Boyer–Myrvold method, for which an open-source implementation is available. section 15.1.1 section 15.2.5
- If the graph is non-planar, switch from eliminating crossings to reducing them. Also consider vertex spacing, edge simplicity, and the readability of labels and flow. section 15.3
One graph, different drawings
K5 cannot be drawn without a crossing, yet its layouts need not be equally cluttered: one shown drawing has five crossing points, while another has only one. For K6, the supplied layouts similarly contrast 15 crossing pairs with a three-intersection embedding. Planarity concerns whether zero crossings is possible; the crossing number concerns the minimum when it is not. section 15.2 section 15.3.1
Figure 15.7 A better embedding for K5. In this case we have only one crossing point, indicated by the fat arrow. Notice that there are still infinitely many embeddings equivalent to this one.
Inspect the one-crossing K5 drawing to see how changing an embedding reduces crossings without making a non-planar graph planar. section 15.2
The edge-count checks and efficient planarity tests can run in O(|V|+|E|) time; the checks are only filters, while some full tests also produce a planar embedding. Finding the minimum crossing number for a general non-planar graph is NP-complete, so a useful drawing need not be provably optimal. section 15.2.2 section 15.2.5 section 15.3 section 15.3.1
