Advanced Algorithms and Data Structures

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

This chapter covers

• Embedding graphs on a 2-D 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’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 ...