Part: Planar Graphs

Graphs, that can be drawn in the plane without edges being crossed are called planar graphs. Planar graphs occur in many practical problems, for instance in the design of printed circuit boards, on which conducting strings may not cross, since it would lead to undesirable electrical contact at crossing points.

In this part, we will study the properties of planar graphs and investigate, under which circumstances a given graph is planar or not planar. Moreover, we will explain the term dual graph and describe its properties.

  1. Definition: Planar Drawing (Embedding)
  2. Definition: Planar Graph
  3. Definition: Face, Infinite Face
  4. Definition: Face Degree
  5. Lemma: Handshaking Lemma for Planar Graphs
  6. Theorem: Euler Characteristic for Planar Graphs
  7. Definition: Dual Planar Graph
  8. Chapter: Conditions for Planarity and Planarity Testing
  9. Definition: Pieces of a Graph With Respect to A Cycle
  10. Definition: Separating and Non-Separating Cycles
  11. Definition: Interlacing Pieces with Respect to a Cycle, Interlacement Graph
  12. Definition: Subdivision of a Graph
  13. Lemma: When is it possible to find a separating cycle in a biconnected graph, given a non-separating cycle?
  14. Theorem: Characterization of Biconnected Planar Graphs
  15. Theorem: Characterization of Planar Graphs

Thank you to the contributors under CC BY-SA 4.0!