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.
Table of Contents
- Definition: Planar Drawing (Embedding)
- Definition: Planar Graph
- Definition: Face, Infinite Face
- Definition: Face Degree
- Lemma: Handshaking Lemma for Planar Graphs
- Theorem: Euler Characteristic for Planar Graphs
- Definition: Dual Planar Graph
- Chapter: Conditions for Planarity and Planarity Testing
- Definition: Pieces of a Graph With Respect to A Cycle
- Definition: Separating and Non-Separating Cycles
- Definition: Interlacing Pieces with Respect to a Cycle, Interlacement Graph
- Definition: Subdivision of a Graph
- Lemma: When is it possible to find a separating cycle in a biconnected graph, given a non-separating cycle?
- Theorem: Characterization of Biconnected Planar Graphs
- Theorem: Characterization of Planar Graphs