The Art Gallery Guardian

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: .