# A characterization of treewidth 2 graphs

Consider 3 reduction operations on a graph:

1. Parallel reduction: Remove an parallel edge.
2. Series reduction: Remove a degree 2 vertex $$v$$ and add an edge to connect $$v$$'s neighbor.
3. Pendant/isolated vertex/loop reduction: Remove a vertex with degree at most $$1$$, remove loops.

For an edge $$e$$, a sequence of reduction is called $$e$$-avoiding if none of the reduction delete $$e$$ or the vertices incident to $$e$$.

A reduction sequence is maximal if there is no reduction can be applied or any reduction will decrease the number of vertices to less than $$2$$.

A graph has treewidth $$2$$, if and only if there exist a reduction sequence that reduce the graph to an empty graph.

We can prove a stronger result, such that we can make sure that every maximal $$e$$-avoiding reduction reduce the graph to a single edge $$e$$.

Lemma1

Every simple treewidth $$2$$ graph $$G$$ with at least $$3$$ vertices has at least $$2$$ non-adjacent vertices with degree at most $$2$$, or it is a triangle.

Proof

Consider a tree decomposition. If it has more than $$2$$ bags, then there are $$2$$ leaves. In each leave, there exist a vertex with degree at most $$2$$, since it is not incident to any vertex outside it's bag and there are at most $$2$$ other vertices in the bag. Also, those two vertices are not adjacent to each other.

If it contain only $$1$$ bag, and if there is no $$2$$ non-adjacent vertices wit degree at most $$2$$, then it must be a triangle.

Theorem2

A graph $$G$$ has treewidth 2 if and only if for every edge $$e$$, every maximal sequence of $$e$$-avoiding reduction reduce the graph to the edge $$e$$.

Proof

For one direction, consider any $$e$$-avoiding reduction that reduces the graph to a single edge $$e$$. Apply two more vertex removal to get the empty graph.

For the other direction, assume $$e$$ incident to edge $$uv$$.

The proof is by induction. The base case where $$G$$ is a graph with at most $$2$$ vertices is trivial.

Consider the induction step with a graph $$G$$ with at least $$3$$ vertices. Each reduction operation can be expressed as minor operations, thus it results a treewidth $$2$$ graph, hence it has the desired property. Thus we need to show if a graph has treewidth $$2$$, one of the operations can be applied. Indeed, we can always apply a reduction if there is at least $$3$$ vertices.

If none of the operations can be applied, then the graph has to be simple. There can't be two non-adjacent vertices with degree at most $$2$$, otherwise one of them is not $$u$$ or $$v$$ and can be removed with series reduction. If the graph is a triangle, then there is a vertex with degree $$2$$ that's not $$u$$ and $$v$$. Hence, by the Lemma, the graph can have at most $$2$$ vertices.

Remark

One can apply this to show that the AB-reducible graphs and generalized outerplanar graphs in [1] is exactly the graphs with treewidth $$2$$.

# Acknowledgment

I wish to thank Urvashi Khandelwal and Vivek Madan for helpful discussions.

# Reference

[1] Q. Cheng, F. Chen, W. Xu, S. Wang, Recursive sum–product algorithm for generalized outer-planar graphs, Information Processing Letters. 112 (2012) 449–456 10.1016/j.ipl.2012.03.001.

Posted by Chao Xu on 2015-04-10.
Tags: .