Lesson 3

Why planar graphs?

• Expensive crossings.  When designing printed circuit boards, it's important that wires do not intersect (otherwise they must be routed in 3D space, which is much more costly).
  

  



• Many graphs are planar.  Many real-world graphs naturally turn out to be planar—for example, road maps: in the corresponding graphs, vertices are intersections, and if two roads cross somewhere, that crossing is a vertex.
  

  

  
  Another example—maps (neighboring regions are connected by an edge).
  

  

  
  That's why it's important to understand the properties of planar graphs and the algorithms for them. Can we, for example, always color them with a small number of colors? Can we find shortest paths in planar graphs faster than in the general case?


• Visualization.  When drawing diagrams and schematics, we generally want to avoid crossing edges—this improves readability.