Main Classes of Graphs

31 января 2024 г.

This is a short summary of the section on main graph classes in the book Computer Science Guide by William Springer.

There are problems that are difficult to solve for arbitrary graphs but have trivial solutions for certain classes of graphs, and vice versa. Therefore, many problems can be simplified if you can show that they belong to a particular graph class.

Forbidden subgraphs

The concept of forbidden subgraphs is a method that defines a set of structures that must not appear in a graph.

Forbidden substructures can be defined in several ways:

• Graphs: A graph does not contain any subgraph from a (possibly infinite) family.Example: bipartite graphs contain no odd cycles.
• Induced subgraphs: The graph does not contain certain induced subgraphs (a subset of vertices together with all edges between them).Example: chordal graphs contain no induced chordless cycles of length ≥ 4.
• Homeomorphic graphs: One graph can be obtained from another by removing degree-2 vertices (vertices with exactly two edges) and merging edges.
• Graph minors: A subgraph obtained by edge contraction (select two adjacent vertices and merge them into one).

A graph class can have multiple characterizations using different types of forbidden substructures.

Planar graphs

A class of graphs representing maps on a plane (or sphere). A planar graph can be drawn so that its edges intersect only at vertices.

Any planar map can be represented as a planar graph by replacing each region with a vertex and connecting vertices where regions share boundaries.

The Pontryagin–Kuratowski theorem states that a graph is planar if and only if it does not contain subdivisions of the complete graph with five vertices (K₅) or the complete bipartite graph with three vertices in each partition (K₃,₃). In other words, it classifies planar graphs in terms of forbidden subgraphs.

Wagner’s theorem — Planar graphs also do not contain the same structures as minors. This theorem is closely related to the Pontryagin–Kuratowski theorem.

Suppose we have a non-planar graph K₅ — there is no way to draw it on a plane without at least one edge crossing. If we add a vertex in the middle of just one edge, this will not eliminate the crossing, so the new graph will also be non-planar. Therefore, the forbidden structures are any subgraphs that are homeomorphic to K₅ or K₃,₃.

Euler's formula — if a finite connected graph with v vertices, e edges, and f faces can be represented on a plane without edge crossings, then:

v − e + f = 2

Fáry's theorem — essentially, every such graph can be drawn so that all edges are represented as straight line segments.

Planar graphs can be divided into smaller parts by removing O(√n) vertices. This property is useful for designing divide-and-conquer algorithms and for dynamic programming on planar graphs.

Perfect Graphs

In a perfect graph, the chromatic number is exactly equal to the size of its largest clique. This equality must hold not only for the graph itself but also for all of its induced subgraphs.

The chromatic number of a graph is the minimum number of colors required for a proper vertex coloring. If a graph contains a clique of size k, then its chromatic number must be at least k.

If a graph is perfect, then all of its induced subgraphs are also perfect.

The Strong Perfect Graph Theorem characterizes perfect graphs as graphs with no odd holes (induced chordless cycles of odd length) and no odd antiholes (the complements of such cycles).

The Weak Perfect Graph Theorem states that the complement of every perfect graph is also perfect. It follows as a consequence of the proof of the Strong Perfect Graph Theorem.

In a perfect graph, the product of the size of the largest clique and the size of the largest independent set is greater than or equal to the number of vertices in the graph. This property also holds for all of its induced subgraphs.

The following problems can be solved in polynomial time on perfect graphs:

1. Graph coloring
2. Finding the maximum clique
3. Finding the maximum independent set.

Subclasses of perfect graphs:

• Bipartite graphs — their chromatic number is equal to 2.
• Chordal graphs — they contain no induced chordless cycles of length greater than 3.
• Comparability graphs — they represent partially ordered sets.
• Subclasses of these classes, one of which is the class of interval graphs.

Bipartite graph

Graphs whose chromatic number is 2.

How to recognize a bipartite graph

1. Select one vertex from each connected component, assign it the first color, and add it to a queue.
2. Repeatedly remove a vertex from the queue and examine its neighbors. If a neighboring vertex has not yet been colored, assign it the opposite color and add it to the queue..

If a neighboring vertex has already been assigned the same color as the current vertex, the graph is not bipartite. Otherwise, if the process completes without conflicts, the graph is bipartite.

Applications:

• Petri nets
• Other problems, including the stable marriage problem and the assignment problem

Interval graphs

An interval graph can be represented as a set of overlapping intervals placed along a common line. Each interval represents a vertex.

Two vertices are adjacent if their corresponding intervals overlap.

Interval graphs are chordal and contain no asteroidal triples (sets of three vertices such that, for any two of them, there exists a path connecting them that avoids the neighborhood of the third vertex).

Applications:

• Genetic analysis — gene subelements that are likely to be related can be modeled as overlapping intervals, forming a linear structure.
• Resource allocation problems — each interval represents a request for a resource, and graph coloring is used to allocate resources. In this context, the chromatic number of the graph is the minimum number of resource units required.

Circular-arc graphs

Circular-arc graphs are a superset of interval graphs. Every interval graph is also a circular-arc graph, but not every circular-arc graph is an interval graph.

A circular-arc graph can be represented as a set of intersecting arcs on a circle, where each arc represents a vertex.

Two vertices are adjacent if their corresponding arcs intersect.

Interval representation can be obtained by cutting the circle at a point not covered by any arc and straightening it into a line.

In addition to interval graphs, the class of circular-arc graphs also includes imperfect graphs, such as odd chordless cycles.