15 Graph Embeddings and Planarity
Drawing Graphs with Minimal Edge Intersections
This chapter covers
- Embedding graphs on a 2D plane
- Defining graph planarity
- Introducing complete and bipartite complete graphs
- Discussing algorithms to find out if a graph is planar
- Defining minimum crossing number for non-planar graphs
- Implementing algorithms to detect crossing edges
Now that we have introduced graphs properly (in chapter 14), we are ready to take the next step: drawing a graph. So far we 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 structure in a Euclidean space, and in particular in the 2D plane?
This is not always needed for all graphs’ 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 are crucial. Take, for instance, printed circuits boards (PCB) design, shown in figure 15.1: the way electronic components (vertices) and conductive tracks (edges) are positioned over the board is crucial not just to the good functioning of the circuit, but also to optimize the manufacturing process and reduce the amount of copper used, and the overall costs.