Graph Theory Unit 10 ReviewPlanar Graphs and Graph Coloring

Key Concepts and Definitions

• Planar graph is a graph that can be drawn on a plane without any edges crossing
• Non-planar graph contains edge crossings when drawn on a plane
• Graph embedding maps a graph onto a surface (plane, sphere, torus) without edge crossings
• Euler's formula relates the number of vertices ($v$), edges ($e$), and faces ($f$) in a connected planar graph: $v - e + f = 2$
  • Applies to connected planar graphs
  • Helps determine if a graph is planar
• Graph coloring assigns colors to vertices such that no adjacent vertices share the same color
• Chromatic number ($\chi(G)$) represents the minimum number of colors needed to color a graph $G$
  • Finding the chromatic number is an NP-hard problem
• Four Color Theorem states that any planar graph can be colored using at most four colors

Planar Graph Fundamentals

• Planar graphs can be drawn on a plane without edge crossings
  • Edges may intersect at vertices but not at any other point
• Planar graphs have practical applications (circuit board design, geographic map coloring)
• Subgraphs of a planar graph are also planar
• Planar graphs have a maximum number of edges based on the number of vertices
  • For a simple connected planar graph with $n$ vertices, the maximum number of edges is $3n - 6$
• Kuratowski's Theorem characterizes non-planar graphs
  • A graph is planar if and only if it does not contain a subdivision of $K_5$ (complete graph on 5 vertices) or $K_{3,3}$ (complete bipartite graph with 3 vertices in each part)
• Planar graphs can be represented using different data structures (adjacency matrix, adjacency list)

Graph Drawing and Embedding

• Graph drawing aims to create a visual representation of a graph on a plane or other surface
• Embedding a graph on a surface requires mapping vertices to distinct points and edges to non-intersecting curves
• Planar embedding is a drawing of a planar graph on a plane without edge crossings
  • Planar graphs can have multiple planar embeddings
• Graphs can be embedded on higher genus surfaces (torus, double torus) if they are not planar
• Straight-line embedding draws edges as straight-line segments
  • Every planar graph has a straight-line embedding (Fáry's Theorem)
• Orthogonal embedding uses only horizontal and vertical line segments for edges
  • Useful for applications like VLSI circuit design
• Embedding algorithms (Tutte's barycentric method, Schnyder's realizer) can compute planar embeddings of graphs

Euler's Formula and Its Applications

• Euler's formula ($v - e + f = 2$) relates the number of vertices ($v$), edges ($e$), and faces ($f$) in a connected planar graph
• Helps determine if a graph is planar by checking if the formula holds
• Can be used to derive upper bounds on the number of edges in a planar graph
  • For a simple connected planar graph with $n$ vertices, $e \leq 3n - 6$
  • For a simple bipartite planar graph with $n$ vertices, $e \leq 2n - 4$
• Euler's formula has extensions for graphs on other surfaces (sphere, torus)
  • For a connected graph embedded on a sphere, $v - e + f = 2$
  • For a connected graph embedded on a torus, $v - e + f = 0$
• Useful in solving problems related to planar graph properties and constraints

Planarity Testing Algorithms

• Planarity testing determines if a given graph is planar or non-planar
• Kuratowski's Theorem provides a characterization of non-planar graphs
  • A graph is planar if and only if it does not contain a subdivision of $K_5$ or $K_{3,3}$
• Planarity testing algorithms have polynomial time complexity
  • Hopcroft-Tarjan algorithm runs in $O(n)$ time using a depth-first search approach
  • Boyer-Myrvold algorithm is a simplified $O(n)$ planarity testing algorithm
• Planarity testing is a key step in many graph drawing and embedding algorithms
• Identifying non-planar subgraphs can help in finding planar embeddings or graph decomposition
• Efficient planarity testing is crucial for large-scale graph applications

Graph Coloring Basics

• Graph coloring assigns colors to vertices such that no adjacent vertices share the same color
• Proper coloring uses the minimum number of colors needed to color the graph
• Chromatic number ($\chi(G)$) is the minimum number of colors required for a proper coloring of graph $G$
  • Planar graphs have $\chi(G) \leq 4$ (Four Color Theorem)
• Graph coloring has various applications (scheduling, register allocation, frequency assignment)
• Different types of graph coloring include vertex coloring, edge coloring, and face coloring
  • Vertex coloring assigns colors to vertices
  • Edge coloring assigns colors to edges such that no two adjacent edges have the same color
  • Face coloring assigns colors to the faces of a planar embedding
• Graph coloring is an NP-hard problem in general
  • Polynomial-time algorithms exist for special cases (bipartite graphs, planar graphs)

Chromatic Number and Coloring Algorithms

• Chromatic number ($\chi(G)$) represents the minimum number of colors needed for a proper coloring of graph $G$
• Finding the chromatic number is an NP-hard problem
  • Approximation algorithms and heuristics are used for large graphs
• Greedy coloring algorithm assigns the first available color to each vertex in some order
  • Does not always produce an optimal coloring but provides an upper bound on $\chi(G)$
• Welsh-Powell algorithm orders vertices by decreasing degree and applies greedy coloring
  • Guarantees using no more than $\Delta(G) + 1$ colors, where $\Delta(G)$ is the maximum degree of the graph
• Exact algorithms for finding the chromatic number (branch-and-bound, integer programming) have exponential worst-case time complexity
• Four Color Theorem states that every planar graph has $\chi(G) \leq 4$
  • Proved using computer-assisted methods (Appel and Haken, 1976)
• Graph coloring algorithms have practical applications (timetabling, compiler optimization)

Applications and Real-World Examples

• Map coloring assigns colors to regions of a map such that no adjacent regions have the same color
  • Four colors are sufficient for any planar map (Four Color Theorem)
• Scheduling problems can be modeled as graph coloring
  • Vertices represent tasks, edges represent conflicts, colors represent time slots or resources
  • University exam scheduling, aircraft scheduling
• Register allocation in compilers
  • Variables are assigned to a limited number of registers
  • Interference graph represents conflicts between variables
  • Graph coloring finds a valid register assignment
• Frequency assignment in wireless networks
  • Assign frequencies to transmitters to avoid interference
  • Vertices represent transmitters, edges represent potential interference
  • Graph coloring finds a valid frequency assignment
• Sudoku puzzles can be modeled as a graph coloring problem
  • Each cell is a vertex, edges connect cells that cannot have the same number
  • 9-coloring of the graph represents a valid Sudoku solution
• Traffic light sequencing at intersections
  • Vertices represent traffic flows, edges represent conflicts
  • Graph coloring determines a safe and efficient traffic light sequence