7.4 Planar Graphs and Coloring

Planar graphs can be drawn without edge crossings and have unique properties like Euler's formula. They're crucial in circuit design, network topology, and map coloring. Understanding planarity helps solve real-world problems efficiently.

Graph coloring assigns colors to vertices so adjacent ones differ. It's used in scheduling, register allocation, and frequency assignment. The Four Color Theorem states any planar graph can be colored with just four colors.

Graph Planarity and its Implications

Planar Graphs and their Properties

Top images from around the web for Planar Graphs and their Properties

• 

  Euler's formula - Wikipedia View original

  Is this image relevant?

• 

  Math Gems View original

  Is this image relevant?

• 

  Euler's formula - Wikipedia View original

  Is this image relevant?

• 

  Math Gems View original

  Is this image relevant?

1 of 2

Top images from around the web for Planar Graphs and their Properties

• 

  Euler's formula - Wikipedia View original

  Is this image relevant?

• 

  Math Gems View original

  Is this image relevant?

• 

  Euler's formula - Wikipedia View original

  Is this image relevant?

• 

  Math Gems View original

  Is this image relevant?

1 of 2

• A planar graph can be drawn on a plane without any edges crossing
• Euler's formula relates the number of vertices (v), edges (e), and faces (f) in a connected planar graph: $v - e + f = 2$
• Planar graphs have at most $3n - 6$ edges, where $n$ is the number of vertices (for $n \geq 3$)
• The complete graph $K_5$ and the complete bipartite graph $K_{3,3}$ are examples of non-planar graphs

Applications of Planar Graphs

• Planar graphs have practical applications in circuit design, network topology, and map coloring
  • In circuit design, planar graphs help minimize the number of crossings between connections, reducing interference and simplifying manufacturing
  • Network topology benefits from planar graphs by allowing efficient routing and minimizing the need for complex wiring or overlapping connections
  • Map coloring problems, such as assigning colors to countries or regions on a map, can be modeled using planar graphs to ensure adjacent regions have different colors

Testing for Graph Planarity

Kuratowski's Theorem and its Implications

• Kuratowski's theorem states that a graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_5$ or $K_{3,3}$
  • A subdivision of a graph is obtained by replacing edges with paths of one or more edges
  • The planarity testing algorithm based on Kuratowski's theorem has a time complexity of $O(n^2)$
• The Wagner theorem is an alternative characterization of planar graphs, stating that a graph is planar if and only if it does not have $K_5$ or $K_{3,3}$ as a minor

Other Planarity Testing Algorithms

• The Fraysseix-Rosenstiehl algorithm tests for graph planarity by incrementally building a planar embedding of the graph
  • It maintains a data structure called a "combinatorial map" to represent the embedding and updates it as vertices and edges are added
  • The algorithm has a linear time complexity of $O(n)$
• The Boyer-Myrvold algorithm is another linear-time planarity testing algorithm
  • It uses a depth-first search approach to identify and contract certain subgraphs called "ears"
  • The algorithm simplifies the graph while maintaining its planarity, allowing for efficient testing

Graph Coloring and Applications

Graph Coloring Basics

• Graph coloring assigns colors to the vertices of a graph such that no two adjacent vertices have the same color
• The minimum number of colors needed to color a graph is called its chromatic number, denoted by $\chi(G)$
• Greedy coloring algorithms, such as the Welsh-Powell algorithm, provide upper bounds on the chromatic number
  • The Welsh-Powell algorithm orders vertices by decreasing degree and assigns the smallest available color to each vertex in turn
  • While not always optimal, it guarantees a coloring using at most $\Delta + 1$ colors, where $\Delta$ is the maximum degree of the graph

Applications of Graph Coloring

• Graph coloring has applications in scheduling problems, register allocation, and frequency assignment in wireless networks
  • In scheduling problems, colors can represent time slots, and adjacent vertices represent tasks that cannot be performed simultaneously
  • Register allocation in compilers uses graph coloring to assign variables to a limited number of registers, minimizing the need for expensive memory accesses
  • Frequency assignment in wireless networks models the problem of assigning frequencies to transmitters as a graph coloring problem, ensuring that nearby transmitters use different frequencies to avoid interference

Chromatic Number vs Planarity

Bounds on Chromatic Number

• For any graph $G$ with maximum degree $\Delta$, $\chi(G) \leq \Delta + 1$ (Brooks' theorem)
• The chromatic number of a complete graph $K_n$ is $n$, as all vertices are adjacent to each other
• The chromatic number of a bipartite graph is at most 2, as the vertices can be partitioned into two sets with no edges between vertices in the same set

Chromatic Number and Planarity

• The Four Color Theorem states that any planar graph can be colored using at most four colors
  • This implies that the chromatic number of a planar graph is at most 4
  • The theorem was first proven by Appel and Haken in 1976 using computer assistance, and a simpler proof was given by Robertson, Sanders, Seymour, and Thomas in 1997
• Determining the chromatic number of an arbitrary graph is an NP-hard problem
  • This means that there is no known polynomial-time algorithm for finding the exact chromatic number of a graph
  • However, approximation algorithms and heuristics can be used to find good colorings in practice
• The chromatic polynomial of a graph counts the number of ways to color the graph using a given number of colors
  • It is a polynomial in the number of colors and can be used to analyze the colorability of a graph
  • The chromatic polynomial is related to the Tutte polynomial, a more general graph polynomial that encodes various properties of a graph