xviii. Special Graph Classes

Many NP-hard problems become polynomial on structured graphs, and many “is this realisable” questions have closed-form criteria. This note covers cacti, chordal and interval graphs, treewidth (with the treewidth-2 case), degree sequences (Erdős–Gallai, Gale–Ryser, Landau), short cycle counting, and planarity.

Cactus graphs

Every edge lies on at most one simple cycle (edge cactus). A DFS closes every cycle with exactly one back edge. The cactus tree (one node per vertex, one per cycle, joined to the cycle’s vertices; bridges kept as vertex–vertex edges) turns path questions into tree questions: e.g. the number of simple paths between $u$ and $v$ is $2^{(\text{cycle nodes on the tree path})}$, and DP over the tree handles independent sets, matchings and distances (for each cycle, a small DP around it).

struct Cactus {
    int n; bool isCactus = true; vector<vector<int>> cycles, tree; vector<int> cycleOfEdge;
    Cactus(int n, const vector<pair<int, int>>& E) : n(n), cycleOfEdge(sz(E), -1) {   // simple graph
        vector<vector<pair<int, int>>> g(n);
        for (int e = 0; e < sz(E); e++) g[E[e].first].push_back({E[e].second, e}), g[E[e].second].push_back({E[e].first, e});
        vector<int> st(n), par(n, -1), pe(n, -1), it(n);
        for (int s = 0; s < n; s++) {
            if (st[s]) continue;
            vector<int> stk{s}; st[s] = 1;
            while (sz(stk)) {
                int u = stk.back();
                if (it[u] == sz(g[u])) { st[u] = 2; stk.pop_back(); continue; }
                auto [v, e] = g[u][it[u]++];
                if (e == pe[u]) continue;
                if (!st[v]) { st[v] = 1, par[v] = u, pe[v] = e; stk.push_back(v); }
                else if (st[v] == 1) {                         // back edge closes a cycle
                    int k = sz(cycles); vector<int> cyc;
                    for (int x = u; x != v; x = par[x]) { cyc.push_back(x); if (cycleOfEdge[pe[x]] != -1) isCactus = false; cycleOfEdge[pe[x]] = k; }
                    cyc.push_back(v); reverse(all(cyc)); cycleOfEdge[e] = k; cycles.push_back(cyc);
                }
            }
        }
        tree.assign(n + sz(cycles), {});
        for (int k = 0; k < sz(cycles); k++) for (int v : cycles[k]) tree[v].push_back(n + k), tree[n + k].push_back(v);
        for (int e = 0; e < sz(E); e++) if (cycleOfEdge[e] == -1) tree[E[e].first].push_back(E[e].second), tree[E[e].second].push_back(E[e].first);
    }
};

For vertex cacti or general graphs, the block-cut tree plays the same role (Biconnectivity).

Chordal graphs

Every cycle of length $\ge 4$ has a chord. Equivalent: there is a perfect elimination ordering (PEO): each vertex’s later neighbours form a clique. Maximum cardinality search (always visit next the vertex with the most visited neighbours) produces, reversed, a PEO iff the graph is chordal. On chordal graphs: maximum clique, chromatic number (equal), maximum independent set, and the chromatic polynomial ${\prod }_i(x-d_i)$ ($d_i$ = later neighbours) are all linear. Interval graphs and trees are chordal.

struct Chordal {
    int n; vector<vector<int>> g; vector<int> peo, pos;
    Chordal(const vector<vector<int>>& adj) : n(sz(adj)), g(adj), pos(n) {      // maximum cardinality search
        vector<int> label(n), done(n), order; vector<vector<int>> bucket(n + 1); int top = 0;
        for (int v = 0; v < n; v++) bucket[0].push_back(v);
        while (sz(order) < n) {
            while (bucket[top].empty()) top--;
            int u = bucket[top].back(); bucket[top].pop_back();
            if (done[u] || label[u] != top) continue;
            done[u] = 1; order.push_back(u);
            for (int v : g[u]) if (!done[v]) bucket[++label[v]].push_back(v), top = max(top, label[v]);
        }
        peo.assign(order.rbegin(), order.rend());
        for (int i = 0; i < n; i++) pos[peo[i]] = i;
    }
    bool isChordal() const {                                 // the earliest later neighbour must see all other later neighbours
        vector<set<int>> adj(n); for (int u = 0; u < n; u++) adj[u] = set<int>(all(g[u]));
        for (int u = 0; u < n; u++) {
            int best = -1;
            for (int v : g[u]) if (pos[v] > pos[u] && (best < 0 || pos[v] < pos[best])) best = v;
            if (best >= 0) for (int v : g[u]) if (pos[v] > pos[u] && v != best && !adj[best].count(v)) return false;
        }
        return true;
    }
    vector<int> laterDegrees() const { vector<int> d(n); for (int i = 0; i < n; i++) for (int v : g[peo[i]]) d[i] += pos[v] > i; return d; }
    int maxClique() const { int b = n ? 1 : 0; for (int d : laterDegrees()) b = max(b, d + 1); return b; }
    vector<int> coloring() const {                           // optimal on chordal graphs: greedy in reverse PEO
        vector<int> col(n, -1);
        for (int i = n - 1; i >= 0; i--) {
            int u = peo[i]; vector<char> used(sz(g[u]) + 1);
            for (int v : g[u]) if (col[v] >= 0 && col[v] < sz(used)) used[col[v]] = 1;
            int c = 0; while (used[c]) c++; col[u] = c;
        }
        return col;
    }
};

Proof sketch: PEOs, the test, and optimal colouring

PEO ⟹ chordal: in a cycle of length $\ge 4$, the vertex of the cycle that comes first in the PEO has both cycle-neighbours later, so they are adjacent: a chord. Chordal ⟹ PEO exists: every chordal graph has a simplicial vertex (Dirac: a minimal separator in a chordal graph is a clique, and a non-complete chordal graph has two non-adjacent simplicial vertices), and removing it keeps the graph chordal. MCS (Tarjan–Yannakakis) visits vertices so that in a chordal graph the reverse order is a PEO; the check is complete because if every vertex’s earliest later neighbour is adjacent to all of its other later neighbours, induction from the end shows all later-neighbour sets are cliques. Colouring: processing in reverse PEO, a vertex’s already-coloured neighbours are its later neighbours, a clique of size $d$, so greedy uses at most $\max d+1=\omega$ colours, which is optimal. The chromatic polynomial factor $(x-d_i)$ counts colours available to vertex $i$ given its later clique.

Perfect graphs ($\chi =\omega$ for every induced subgraph; chordal, bipartite, comparability, interval graphs and their complements): colouring, clique, independent set are polynomial (via the Lovász theta function in theory; via the class structure in practice). For comparability graphs (orientable as partial orders), max clique = longest chain and max independent set = largest antichain = min chain cover (Dilworth, Matching). Interval graphs: sort by right end, greedy for independent set and colouring (interval partitioning, Intervals).

Treewidth

A tree decomposition is a tree of bags covering every edge, with each vertex’s bags forming a connected subtree; the width is (max bag size) − 1. DP over a decomposition of width $k$ solves independent set / dominating set / colouring / Hamiltonicity in $2^{O(k)}n$ or $k^{O(k)}n$. Trees have width 1; series-parallel graphs (no $K_4$ minor) width $\le 2$; $k\times n$ grids width $k$; planar graphs $O(\sqrt{n})$.

Width $\le 2$: repeatedly eliminate a vertex of degree $\le 2$, joining its two neighbours; the graph has treewidth $\le 2$ iff this empties it. The bag of $v$ is $v$ plus its neighbours at elimination, attached to the bag of its neighbour eliminated first afterwards (Library Checker “Tree Decomposition (Width 2)”).

struct Treewidth2 {
    bool ok = false; vector<vector<int>> bags; vector<pair<int, int>> treeEdges;
    Treewidth2(int n, const vector<pair<int, int>>& E) {
        vector<set<int>> adj(n); for (auto [u, v] : E) if (u != v) adj[u].insert(v), adj[v].insert(u);
        vector<int> order, pos(n, -1), st; vector<vector<int>> nb(n);
        for (int v = 0; v < n; v++) if (sz(adj[v]) <= 2) st.push_back(v);
        while (sz(st)) {
            int v = st.back(); st.pop_back();
            if (pos[v] != -1 || sz(adj[v]) > 2) continue;
            pos[v] = sz(order); order.push_back(v); nb[v].assign(all(adj[v]));
            for (int u : nb[v]) adj[u].erase(v);
            if (sz(nb[v]) == 2) adj[nb[v][0]].insert(nb[v][1]), adj[nb[v][1]].insert(nb[v][0]);
            for (int u : nb[v]) if (sz(adj[u]) <= 2) st.push_back(u);
            adj[v].clear();
        }
        if (sz(order) < n) return;
        ok = true; bags.resize(n); int lastRoot = -1;
        for (int t = 0; t < n; t++) {
            int v = order[t]; bags[t] = {v}; bags[t].insert(bags[t].end(), all(nb[v]));
            int parent = -1; for (int u : nb[v]) if (parent < 0 || pos[u] < parent) parent = pos[u];
            if (parent >= 0) treeEdges.push_back({t, parent});
            else { if (lastRoot >= 0) treeEdges.push_back({lastRoot, t}); lastRoot = t; }
        }
    }
};

Proof sketch: elimination of degree $\le 2$ vertices

Treewidth $\le 2$ is closed under taking minors, and eliminating a degree-2 vertex $v$ (deleting it and joining its neighbours) produces a minor, while eliminating degree $\le 1$ vertices is deletion; so if the process gets stuck, the remaining graph is a minor with minimum degree $\ge 3$, which contains a $K_4$ minor (every graph with minimum degree 3 does), hence treewidth $\ge 3$. Conversely the elimination ordering defines bags $\{v\}\cup N_{\text{at elimination}}(v)$ of size $\le 3$; each edge is in the bag of whichever endpoint is eliminated first, and the neighbours of $v$ at elimination are adjacent at that time, so they appear together in later bags, which gives the running-intersection property when each bag hangs below the bag of its earliest-eliminated neighbour.

Degree sequences

Question	Criterion
simple graph with degrees $d_1\ge \cdots \ge d_n$ (Erdős–Gallai)	$\sum d$ even and ${\sum }_{i\le k}{d}_i\le k(k-1)+{\sum }_{i>k}\min (d_i,k)$ for all $k$
construct one (Havel–Hakimi)	repeatedly join the largest-degree vertex to the next largest ones
bipartite with sides $a$, $b$ (Gale–Ryser)	$\sum a=\sum b$ and for all $k$: (sum of the $k$ largest $a_i$) $\le {\sum }_j\min (b_j,k)$
tournament score sequence (Landau)	sorted ascending: ${\sum }_{i\le k}{s}_i\ge \left(\genfrac{}{}{0ex}{}{k}{2}\right)$ with equality at $k=n$
tree with degrees $d_i\ge 1$	$\sum d_i=2(n-1)$ (build via Prüfer codes)
connected simple graph	graphical and $\sum d_i\ge 2(n-1)$ with all $d_i\ge 1$

Tournament graphs (a complete graph with every edge given one direction) always have a king: a vertex that reaches every other vertex in at most 2 steps, and a Hamiltonian path always exists.

Proof: every tournament has a king

Take $v$ with maximum out-degree, and suppose some $u$ is not reached by $v$ within 2 steps. Then $v$ does not beat $u$ directly, so (tournament: every pair has exactly one direction) $u$ beats $v$; and $u$ beats none of $v$‘s out-neighbours either, since any out-neighbour $w$ of $v$ with $u\to w$ would give the path $v\to w\to u$, a 2-step route — excluded by assumption. So every out-neighbour $w$ of $v$ beats $u$, meaning $u$ beats $v$ and every one of $v$‘s ${\mathrm{deg}}^{+}(v)$ out-neighbours, so ${\mathrm{deg}}^{+}(u)\ge {\mathrm{deg}}^{+}(v)+1$, contradicting $v$‘s maximality. Hence every vertex is reached by $v$ within 2 steps: $v$ is a king. For the Hamiltonian path, induct on $n$: given a Hamiltonian path $p_1\to p_2\to \cdots \to p_{n-1}$ on the other $n-1$ vertices and a new vertex $x$, either $x\to p_1$ (prepend $x$), $p_{n-1}\to x$ (append $x$), or — since neither extreme case holds — scanning the path there is some $i$ with $p_i\to x$ and $x\to p_{i+1}$ (the direction between $x$ and $p_1$ is “loses”, and between $x$ and $p_{n-1}$ is “wins”, so it flips somewhere along the path), and inserting $x$ there extends the path by one vertex. $■$

bool isGraphical(vector<ll> d) {                            // Erdős–Gallai, O(n log n)
    int n = sz(d); sort(all(d), greater<>()); ll tot = 0;
    for (ll x : d) { if (x < 0 || x > n - 1) return false; tot += x; }
    if (tot % 2) return false;
    vector<ll> suf(n + 1); for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] + d[i];
    ll left = 0;
    for (int k = 1; k <= n; k++) {
        left += d[k - 1];
        int lo = k, hi = n; while (lo < hi) { int m = (lo + hi) / 2; if (d[m] < k) hi = m; else lo = m + 1; }   // first index >= k with d < k
        if (left > (ll)k * (k - 1) + (ll)(lo - k) * k + suf[lo]) return false;
    }
    return true;
}
pair<bool, vector<pair<int, int>>> havelHakimi(const vector<ll>& d) {
    priority_queue<pair<ll, int>> pq; vector<pair<int, int>> E;
    for (int i = 0; i < sz(d); i++) { if (d[i] < 0) return {false, {}}; if (d[i]) pq.push({d[i], i}); }
    while (sz(pq)) {
        auto [k, v] = pq.top(); pq.pop(); vector<pair<ll, int>> take;
        for (ll j = 0; j < k; j++) { if (pq.empty()) return {false, {}}; take.push_back(pq.top()); pq.pop(); }
        for (auto [c, u] : take) { E.push_back({v, u}); if (c > 1) pq.push({c - 1, u}); }
    }
    return {true, E};
}
bool isTournamentScore(vector<ll> s) {
    sort(all(s)); ll sum = 0; int n = sz(s);
    for (int k = 1; k <= n; k++) { sum += s[k - 1]; if (sum < (ll)k * (k - 1) / 2) return false; }
    return sum == (ll)n * (n - 1) / 2;
}

Proof: Havel–Hakimi and the necessity of Erdős–Gallai

Havel–Hakimi: if $d$ is graphical, some realisation has the max-degree vertex $v$ adjacent to the $d_v$ next-largest vertices: if $v\sim x$ and $v\nsim y$ with $d_y\ge d_x$, then $y$ has a neighbour $z\nsim x$ (since $y$ has at least as many neighbours as $x$ and $x$‘s neighbour $v$ isn’t $y$‘s), and the swap $vx,yz\to vy,xz$ preserves degrees and moves $v$‘s neighbourhood towards larger degrees. So removing $v$ and decrementing those vertices preserves graphicality, and the greedy succeeds iff $d$ is graphical. Erdős–Gallai necessity: the $k$ largest-degree vertices have degree sum at most $k(k-1)$ (edges among themselves, counted twice) plus, for each other vertex $i$, at most $\min (d_i,k)$ edges to them. (Sufficiency follows from Havel–Hakimi by an exchange argument.)

Counting short cycles

• Triangles: orient each edge from the lower $(\mathrm{deg},\text{id})$ endpoint to the higher; each vertex has $O(\sqrt{m})$ out-neighbours, and every triangle is found once from its lowest vertex: $O(m\sqrt{m})$ (Sqrt).
• 4-cycles: for each vertex $a$ as the highest-ranked vertex of the cycle, count paths $a-b-c$ with $b,c$ ranked lower than $a$; two such paths to the same $c$ close a 4-cycle: $O(m\sqrt{m})$.

ll countFourCycles(int n, const vector<pair<int, int>>& E) {   // simple graph, cycles as edge sets
    vector<vector<int>> g(n); vector<int> deg(n);
    for (auto [u, v] : E) g[u].push_back(v), g[v].push_back(u), deg[u]++, deg[v]++;
    auto lower = [&](int a, int b) { return pair(deg[a], a) < pair(deg[b], b); };
    vector<ll> cnt(n); ll res = 0;
    for (int a = 0; a < n; a++) {
        for (int b : g[a]) if (lower(b, a)) for (int c : g[b]) if (lower(c, a)) res += cnt[c]++;
        for (int b : g[a]) if (lower(b, a)) for (int c : g[b]) cnt[c] = 0;
    }
    return res;
}

Proof: each 4-cycle counted once, in $O(m\sqrt{m})$

In a 4-cycle $a,b,c,b^{\prime }$ let $a$ be the highest-ranked vertex; then $b,b^{\prime }\sim a$ and the opposite vertex $c$ are all lower. The cycle corresponds to exactly one unordered pair of distinct paths $a-b-c$, $a-b^{\prime }-c$, which the running count cnt[c] adds exactly once (when the second path is seen). No other choice of top vertex counts it. Work: each edge $(a,b)$ with $b$ lower costs $\mathrm{deg}b=\min (\mathrm{deg}a,\mathrm{deg}b)$. Charging the edge to its lower endpoint $v$: $v$ has at most $\min (\mathrm{deg}v,2m/\mathrm{deg}v)\le \sqrt{2m}$ neighbours of degree $\ge \mathrm{deg}v$, so the total is ${\sum }_v\mathrm{deg}v\cdot \sqrt{2m}=O(m\sqrt{m})$.

Planar graphs

• $E\le 3V-6$ (simple, $V\ge 3$; $E\le 2V-4$ if triangle-free), a vertex of degree $\le 5$, 4-colourable (Appel–Haken; 5-colourable constructively in linear time by Kempe chains), $O(\sqrt{V})$ separators (Lipton–Tarjan), treewidth $O(\sqrt{V})$.
• Kuratowski / Wagner: planar iff no subdivision (no minor) of $K_5$ or $K_{3,3}$ — testing this directly is hopeless, so every practical algorithm takes a structural route instead.
• Exploiting planarity: dual graphs (min $s$–$t$ cut = shortest path in the dual for $s,t$ on the outer face), face enumeration (Planar Faces), counting perfect matchings by Pfaffians (FKT, Determinants), $2^{O(\sqrt{V})}$ exact algorithms for many NP-hard problems via the separator.
• 3-colourability of planar graphs is still NP-complete; deciding 4-colourability is trivial (always yes, by Appel–Haken).

Testing planarity in $O(V)$

All of these need a biconnected decomposition first (Biconnectivity) and are substantial to implement from scratch:

Method	Adds	Aux. structure	Produces an embedding?	Extracts Kuratowski subgraph?
Hopcroft–Tarjan (path addition, 1974, the original)	paths	a conflict stack	yes	hard
Lempel–Even–Cederbaum + PQ-trees	vertices (st-numbering)	PQ-tree	yes	hard
Boyer–Myrvold (edge addition, 2004)	edges	bicomp lists with $O(1)$ lazy flipping	yes	built in, for free
de Fraysseix–Rosenstiehl (left-right criterion)	—	—	yes	moderate

If you actually need to implement this

Use Boyer–Myrvold or the left-right criterion, not Hopcroft–Tarjan — both are substantially easier (Hopcroft–Tarjan’s original presentation is notoriously terse), and Boyer–Myrvold additionally extracts an explicit $K_5$/$K_{3,3}$ subdivision on failure, which constructive problems often want. These are the algorithms Boost Graph Library and networkx actually ship.

Where planarity shows up in contests: rarely as an explicit test — more often you’re told the graph is planar and expected to exploit $E=O(V)$, the $O(\sqrt{V})$ separator, or the dual-graph min-cut/shortest-path correspondence, rather than to run a planarity tester yourself.