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.

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

15.4.4    Intersections Between Quadratic Bézier Curves

15.4.5    Vertex-Vertex and Edge-Vertex Intersections

15.5  Summary