Glossary

10.4 Planar Graphs and Graph Coloring

6 min read•august 14, 2024

is a fascinating topic in graph theory. It's all about assigning colors to vertices so no two connected ones match. This concept has real-world uses, like scheduling and map coloring.

Planar graphs, which can be drawn without crossing edges, are key to understanding graph coloring. The famous states any can be colored with just four colors. Mind-blowing, right?

Planar graphs and their properties

Definition and representation of planar graphs

Top images from around the web for Definition and representation of planar graphs

  • Dual graph - Wikipedia View original

    Is this image relevant?

  • planar graphs and vertices of degree $5$ - Mathematics Stack Exchange View original

    Is this image relevant?

  • Dual graph - Wikipedia View original

    Is this image relevant?

1 of 3

Top images from around the web for Definition and representation of planar graphs

  • Dual graph - Wikipedia View original

    Is this image relevant?

  • planar graphs and vertices of degree $5$ - Mathematics Stack Exchange View original

    Is this image relevant?

  • Dual graph - Wikipedia View original

    Is this image relevant?

1 of 3
  • A planar graph is a graph that can be drawn on a plane without any edges crossing each other
  • The vertices of a planar graph are represented as points on the plane
  • The edges of a planar graph are represented as curves connecting the vertices on the plane
  • A graph is considered planar if it is possible to find a drawing that satisfies these conditions (no crossings)

Characterization of planar graphs

  • A graph is planar if and only if it does not contain a subdivision of K₅ (complete graph on 5 vertices) or K₃,₃ (complete with 3 vertices in each part) as a subgraph
    • K₅ is a graph with 5 vertices, where each is connected to every other vertex by an edge
    • K₃,₃ is a graph with 6 vertices divided into two sets of 3 vertices each, where each vertex in one set is connected to every vertex in the other set
  • states that a graph is planar if and only if it does not contain a subgraph that is a subdivision of K₅ or K₃,₃
    • A subdivision of a graph is obtained by replacing edges with paths of arbitrary length
    • This theorem provides a necessary and sufficient condition for a graph to be planar

Properties of planar graphs

  • The outer of a planar graph is the unbounded region that surrounds the graph when it is drawn on a plane
    • Every planar graph has a unique outer face
  • A planar graph can be drawn on a plane such that all vertices lie on the outer face, known as an outerplanar graph
    • Outerplanar graphs are a subclass of planar graphs with additional properties
  • Planar graphs have a maximum number of edges determined by the number of vertices
    • For a simple planar graph with nn vertices, the maximum number of edges is 3n−63n-6 (for n≥3n \geq 3)
    • This property can be derived from (discussed in the next section)

Euler's formula for planar graphs

Statement and application of Euler's formula

  • Euler's formula states that for a connected planar graph with vv vertices, ee edges, and ff faces (including the outer face), the equation v−e+f=2v - e + f = 2 holds true
  • This formula relates the number of vertices, edges, and faces in a planar graph
  • Euler's formula can be used to:
    • Determine the number of faces in a planar graph when given the number of vertices and edges
    • Determine the maximum number of edges in a planar graph with a given number of vertices
      • For a simple planar graph with nn vertices, the maximum number of edges is 3n−63n-6 (for n≥3n \geq 3)
    • Prove properties of planar graphs, such as the existence of a vertex with degree at most 5

Variations of Euler's formula

  • For a planar bipartite graph with vv vertices and ee edges, Euler's formula can be modified to v−e+f=1v - e + f = 1
    • Bipartite graphs are graphs whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex from the other set
  • Euler's formula is a necessary condition for a graph to be planar, but not a sufficient one
    • A graph that satisfies Euler's formula may still be non-planar if it contains a subdivision of K₅ or K₃,₃
    • To determine if a graph is planar, one must also check for the absence of these forbidden subgraphs

Graph coloring and its applications

Definition and concepts

  • Graph coloring is the assignment of colors to the vertices of a graph such that no two adjacent vertices share the same color
    • Adjacent vertices are vertices connected by an edge
  • A proper coloring of a graph is a coloring where no two adjacent vertices have the same color
  • The minimum number of colors required to properly color a graph is called its , denoted by χ(G)\chi(G)
    • Determining the chromatic number of a graph is an important problem in graph theory

Applications of graph coloring

  • Graph coloring has various real-world applications, such as:
    • Scheduling problems: Assigning time slots or resources to tasks or events while avoiding conflicts
    • Map coloring: Coloring regions on a map so that no two adjacent regions have the same color (e.g., coloring countries on a world map)
    • Frequency assignment in wireless networks: Assigning frequencies to wireless devices to avoid interference between adjacent devices
    • Register allocation in compiler optimization: Assigning variables to a limited number of registers in a way that minimizes the number of register spills and reloads
  • The Four Color Theorem states that any planar graph can be colored using at most four colors
    • This theorem was first proven by Kenneth Appel and Wolfgang Haken in 1976 using a computer-assisted proof
    • The proof was later simplified and verified by other mathematicians
  • The Five Color Theorem, which is easier to prove than the Four Color Theorem, states that any planar graph can be colored using at most five colors
    • This theorem provides an upper bound on the chromatic number of planar graphs
    • The proof of the Five Color Theorem is constructive and can be used to create a five-coloring of any planar graph

Chromatic number and graph coloring algorithms

Chromatic number of special graphs

  • The chromatic number of a graph is the minimum number of colors required to color the graph such that no two adjacent vertices have the same color
  • Finding the chromatic number of a graph is an NP-hard problem, meaning that there is no known polynomial-time algorithm to solve it for all graphs
    • However, for certain classes of graphs, the chromatic number can be determined efficiently
  • The chromatic number of a complete graph with nn vertices, denoted as KnK_n, is equal to nn
    • In a complete graph, every vertex is adjacent to every other vertex, so each vertex must have a different color
  • The chromatic number of a bipartite graph is always less than or equal to 2
    • Bipartite graphs can be colored using two colors by assigning one color to vertices in one set and the other color to vertices in the other set
    • Examples of bipartite graphs include trees, even cycles, and complete bipartite graphs (Km,nK_{m,n})

Graph coloring algorithms

  • is a heuristic algorithm that colors the vertices of a graph in a specific order, assigning each vertex the smallest available color that has not been used by its neighbors
    • The order in which the vertices are colored can affect the number of colors used
    • Common ordering strategies include coloring vertices in descending order of degree or using a random order
  • The Welsh-Powell algorithm is another heuristic method that orders the vertices by decreasing degree and then applies the greedy coloring algorithm
    • This algorithm guarantees an upper bound on the number of colors used based on the maximum degree of the graph
  • Brelaz's algorithm, also known as the saturation degree algorithm, is a more sophisticated graph coloring heuristic that takes into account the number of different colors used by the neighbors of each uncolored vertex
    • The saturation degree of an uncolored vertex is the number of different colors used by its already-colored neighbors
    • The algorithm selects the vertex with the highest saturation degree to color next, breaking ties by choosing the vertex with the highest degree
    • Brelaz's algorithm often produces better colorings than the greedy or Welsh-Powell algorithms, but it has a higher time complexity

Key Terms to Review (19)

Adjacency list: An adjacency list is a data structure used to represent a graph, where each vertex (or node) has a list of all the vertices it is directly connected to by edges. This representation is efficient in terms of space and is particularly useful for sparse graphs, as it only stores the edges that exist. By organizing the graph in this way, it becomes easier to traverse and manipulate the graph for algorithms related to connectivity and pathfinding.
Backtracking algorithm: A backtracking algorithm is a problem-solving technique that incrementally builds candidates for solutions and abandons a candidate as soon as it is determined that it cannot lead to a valid solution. This method is particularly useful for solving combinatorial problems, as it explores all potential options while systematically eliminating those that are not feasible. By employing a depth-first search strategy, it can effectively find solutions to complex problems such as graph coloring and the Hamiltonian path problem.
Bipartite graph: A bipartite graph is a type of graph where the set of vertices can be divided into two distinct groups such that no two vertices within the same group are adjacent. This structure allows for the modeling of relationships between two different classes of entities, making it useful in various applications such as matching problems and network flow analysis.
Chromatic number: The chromatic number of a graph is the smallest number of colors needed to color the vertices of the graph such that no two adjacent vertices share the same color. This concept is crucial in graph theory, particularly in understanding how to efficiently organize and represent relationships in various applications, including scheduling problems and map coloring.
Combinatorial Design: Combinatorial design refers to a branch of combinatorics that focuses on the arrangement of elements into specific structures to achieve particular properties. This concept often plays a key role in constructing experiments, organizing data, or solving problems related to graph theory and coloring. Combinatorial designs help in creating balanced and efficient setups, especially when examining relationships within a set of items or when visualizing connections in a planar graph.
Connectedness: Connectedness refers to a property of a graph where there is a path between every pair of vertices. This concept is important as it allows for the understanding of how different parts of a graph relate to each other. When considering connectedness, one can also explore different components of a graph, such as whether a graph is connected or disconnected, which impacts properties like the existence of spanning trees and the efficiency of traversing the graph.
Dual graph: A dual graph is a graph that represents the relationship between the faces of a planar graph. Each vertex in the dual graph corresponds to a face in the original graph, and edges in the dual graph are drawn to connect vertices whose corresponding faces share a common edge. This concept is essential for understanding various properties of planar graphs, including graph coloring and the relationships between regions formed by the graph's edges.
Edge: An edge is a fundamental component of a graph that connects two vertices, representing a relationship or link between them. Edges can be directed or undirected, indicating whether the relationship has a specific direction or is bidirectional. Understanding edges is crucial because they help to illustrate various types of relationships and structures within mathematical and real-world contexts, such as networks, trees, and more complex systems.
Euler's Formula: Euler's Formula states that for any planar graph, the relationship between the number of vertices (V), edges (E), and faces (F) can be expressed as $$ V - E + F = 2 $$. This fundamental equation illustrates the inherent structure of planar graphs and serves as a bridge between geometry and topology, showing how these elements interact in a two-dimensional space.
Face: In the context of planar graphs, a face refers to any of the regions that are enclosed by edges in a graph. Each face is a distinct area, and when considering a planar representation of a graph, the outer infinite region is also counted as a face. Understanding faces is crucial for graph coloring and for applying Euler's formula, which connects vertices, edges, and faces in a planar graph.
Four Color Theorem: The Four Color Theorem states that any planar graph can be colored using no more than four colors in such a way that no two adjacent regions share the same color. This theorem has profound implications in the study of planar graphs and graph coloring, highlighting the relationship between geography, mathematics, and combinatorial optimization. The theorem was first conjectured in 1852 and was proved in 1976 using computer-assisted techniques, making it one of the first major theorems to rely heavily on computational methods for its proof.
Georgy Voronoi: Georgy Voronoi was a Russian mathematician known for his contributions to number theory and geometry, particularly for the development of Voronoi diagrams. These diagrams partition a plane into regions based on the distance to a specific set of points, which is essential in understanding spatial relationships in planar graphs and graph coloring. Voronoi's work is foundational for many applications in computer science, geographic information systems, and optimization problems.
Graph coloring: Graph coloring is the assignment of labels, or colors, to the vertices of a graph such that no two adjacent vertices share the same color. This concept is crucial for solving problems in scheduling, resource allocation, and optimizing networks. Different types of graph coloring techniques exist, depending on the properties of the graph, including planar graphs, where specific constraints apply due to their unique structure.
Greedy coloring: Greedy coloring is a method used to assign colors to the vertices of a graph such that no two adjacent vertices share the same color, using the fewest number of colors possible. This approach follows a straightforward algorithm where each vertex is colored with the smallest available color that hasn't been used by its adjacent vertices, which can be particularly effective for certain types of graphs, especially planar graphs.
Incidence Matrix: An incidence matrix is a mathematical representation of a graph, showing the relationship between vertices and edges. In this matrix, rows represent vertices while columns represent edges, indicating which vertex is connected to which edge. This structure is useful for analyzing various properties of graphs, such as connectivity and colorability, by providing a clear visual representation of how different components of the graph interact with each other.
Kuratowski's Theorem: Kuratowski's Theorem is a fundamental result in graph theory that characterizes planar graphs by stating that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of the complete graph K5 or the complete bipartite graph K3,3. This theorem connects the concept of planarity to specific forbidden structures, providing a clear criterion to determine whether a graph can be drawn on a plane without edges crossing.
Leonhard Euler: Leonhard Euler was an influential Swiss mathematician and physicist, renowned for his contributions across various fields of mathematics, including graph theory and combinatorics. His work laid foundational concepts that remain central to modern mathematical theories, such as the study of planar graphs and coloring techniques, as well as the formulation of Stirling and Bell numbers that deal with partitioning sets. Euler's pioneering approach in these areas has had a lasting impact on both pure and applied mathematics.
Planar graph: A planar graph is a graph that can be drawn on a flat surface without any edges crossing each other. This property allows planar graphs to be visually represented in a way that makes it easy to analyze their structure and relationships. The concept of planarity is essential in various fields, including computer graphics and geographical mapping, as it helps simplify complex networks.
Vertex: A vertex is a fundamental component in graph theory, representing a point where edges meet or intersect. It serves as a node in a graph, helping to define the structure and relationships within the graph. Understanding vertices is crucial for analyzing properties such as connectivity, paths, and cycles, which are essential for various applications in mathematics, computer science, and operations research.
© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.
Back
Practice QuizGlossary
Practice QuizGlossary
Next guide