Planar Graphs

Definition and Basic Properties

Planar Graph Definition

Planar graph: graph drawable on plane with edges intersecting only at vertices. Embedding: specific planar drawing. Planarity: property of admitting such embedding.

Simple Graphs and Multigraphs

Simple planar graph: no loops or multiple edges. Multigraphs: may be planar if embeddable without edge crossings.

Connectivity and Planarity

Connectivity affects planarity: disconnected graphs planar if components planar. 3-connected planar graphs have unique embeddings (Whitney's theorem).

Euler's Formula and Consequences

Euler's Formula Statement

For connected planar graph with V vertices, E edges, F faces: V - E + F = 2. Applies strictly to planar embeddings.

Corollaries from Euler's Formula

Upper bound on edges: E ≤ 3V - 6 for planar graphs with V ≥ 3. Applied to prove non-planarity of certain graphs.

Faces and Degree Sums

Sum of face degrees equals 2E. Every face bounded by at least 3 edges in simple planar graphs.

Kuratowski's Theorem

Theorem Statement

A graph is planar if and only if it contains no subgraph homeomorphic to K5 (complete graph on 5 vertices) or K3,3 (complete bipartite graph with partitions of size 3).

Homeomorphism in Graphs

Homeomorphic graphs: graphs obtained by subdividing edges. Kuratowski's criterion uses subdivision to detect forbidden minors.

Implications for Planarity Testing

Provides basis for planarity algorithms. Detecting Kuratowski subgraphs confirms non-planarity.

Planar Embedding and Drawings

Plane Graphs

Plane graph: planar graph with fixed embedding on the plane. Distinction: planar graph (abstract) vs plane graph (embedded).

Types of Planar Drawings

Straight-line embedding: edges as straight segments. Fáry's theorem: every planar graph admits straight-line embedding.

Face Boundaries and Cycles

Faces bounded by cycles. Outer face: unbounded region. Internal faces: bounded regions. Important for dual graph construction.

Graph Duality

Definition of Dual Graph

Dual graph G*: vertices correspond to faces of G. Edges cross original edges, connecting dual vertices of adjacent faces.

Properties of Dual Graphs

Dual of dual equals original graph if plane embedding fixed. Duality reverses vertex-face roles.

Applications of Duality

Used in network flow, electrical networks, planar graph algorithms. Bridges connectivity with geometric intuition.

Planar Graph Coloring

Four Color Theorem

Every planar graph's vertices can be colored with ≤4 colors so adjacent vertices differ. Long-standing problem solved in 1976 by Appel and Haken.

Five Color Theorem

Five colors suffice by simpler proof. Useful as intermediate result and in algorithm design.

Chromatic Number and Planarity

Chromatic number χ(G) ≤ 4 for planar graphs. Non-planar graphs may require more colors.

Graph Minors and Wagner's Theorem

Graph Minors Definition

Minor: graph obtained by deleting edges/vertices and contracting edges. Minor-closed properties define classes of graphs.

Wagner's Theorem

Characterizes planar graphs by exclusion of K5 and K3,3 minors. Equivalent to Kuratowski's theorem in minor form.

Role in Graph Structure Theory

Minor theory central in Robertson-Seymour theorem. Provides framework for algorithmic planarity tests.

Algorithms for Planarity Testing

Hopcroft and Tarjan Algorithm

Linear-time planarity test using depth-first search and PQ-trees. Efficient practical implementation.

Path Addition Method

Incremental embedding by adding paths and checking crossings. Conceptually simpler but less efficient.

Planar Embedding Construction

Algorithms construct explicit planar embeddings or certify non-planarity.

Algorithm HopcroftTarjanPlanarity(G): Input: Graph G=(V,E) Output: Planarity boolean, embedding if planar 1. Perform DFS on G, compute lowpoints. 2. Construct PQ-tree to represent possible embeddings. 3. Test for forbidden configurations during embedding. 4. Return planar with embedding or non-planar.

Applications of Planar Graphs

Network Design and Circuit Layout

Planar graphs model circuits avoiding crossings. VLSI design uses planar embeddings to optimize layouts.

Geographical Mapping and GIS

Planar graphs represent maps, regions, and adjacency without overlaps.

Graph Drawing and Visualization

Planarity important for readable visualizations. Algorithms minimize edge crossings.

Extensions and Generalizations

Graphs on Surfaces

Graphs embeddable on torus, sphere, or higher genus surfaces generalize planar graphs. Genus measures non-planarity.

Crossing Number

Minimum number of edge crossings in any drawing. Planar graphs have crossing number zero.

Partial Planarity and Near-Planar Graphs

Graphs close to planar with small forbidden minors or restricted crossings studied for approximate embeddings.

Examples and Non-Examples

Planar Graph Examples

Trees, cycles, outerplanar graphs, planar grids, and polyhedral graphs (e.g., cube, dodecahedron graphs).

Non-Planar Graph Examples

K5 and K3,3, their expansions, and graphs containing these as minors.

Testing Examples

Check edge count bounds and attempt embeddings to verify planarity.

References

• Diestel, R., Graph Theory, 5th Edition, Springer, 2017, pp. 100-140.
• West, D. B., Introduction to Graph Theory, 2nd Edition, Prentice Hall, 2001, pp. 115-160.
• Mohar, B., Thomassen, C., Graphs on Surfaces, Johns Hopkins University Press, 2001, pp. 45-80.
• Kuratowski, K., Sur le problème des courbes gauches en topologie, Fundamenta Mathematicae, Vol. 15, 1930, pp. 271-283.
• Appel, K., Haken, W., Every Planar Map is Four Colorable, Illinois J. Math., Vol. 21, 1977, pp. 429-490.