15 Graph embeddings and planarity: Drawing graphs with minimal edge intersections

Now that we have introduced graphs properly in chapter 14, we are ready to take the next step: drawing a graph. So far we’ve talked about graphs in abstract terms, yet we had to visualize them in a certain way to describe how shortest path algorithms work. In chapter 14 we did it manually and took it for granted, but what about an automated approach to embed these data structures in a Euclidean space, and in particular in the 2-D plane?

This is not always needed for all graph applications, nor it is always possible; there are, however, many applications where the way we lay a graph’s vertices and edges on a surface is crucial. Take, for instance, printed circuits board (PCB) design, shown in figure 15.1. The way electronic components (vertices) and conductive tracks (edges) are positioned on the board is crucial not just to the good functioning of the circuit, but also to optimizing the manufacturing process and reducing the amount of copper used, as well as the overall costs.

15.1 Graph embeddings

15.1.1 Some basic definitions

15.1.2 Complete and bipartite graphs

15.2 Planar graphs

15.2.1 Using Kuratowski’s theorem in practice

15.2.2 Planarity testing

15.2.3 A naïve algorithm for planarity testing

15.2.4 Improving performance

15.2.5 Efficient algorithms

15.3 Non-planar graphs

15.3.1 Finding the crossing number

15.3.2 Rectilinear crossing number

15.4 Edge intersections

15.4.1 Straight-line segments

15.4.2 Polylines

15.4.3 Bézier curves