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 vv and add an edge to connect vv's neighbor.
  3. Pendant/isolated vertex/loop reduction: Remove a vertex with degree at most 11, remove loops.

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

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

A graph has treewidth 22, 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 ee-avoiding reduction reduce the graph to a single edge ee.

Lemma1

Every simple treewidth 22 graph GG with at least 33 vertices has at least 22 non-adjacent vertices with degree at most 22, or it is a triangle.

Proof

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

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

Theorem2

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

Proof

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

For the other direction, assume ee incident to edge uvuv.

The proof is by induction. The base case where GG is a graph with at most 22 vertices is trivial.

Consider the induction step with a graph GG with at least 33 vertices. Each reduction operation can be expressed as minor operations, thus it results a treewidth 22 graph, hence it has the desired property. Thus we need to show if a graph has treewidth 22, one of the operations can be applied. Indeed, we can always apply a reduction if there is at least 33 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 22, otherwise one of them is not uu or vv and can be removed with series reduction. If the graph is a triangle, then there is a vertex with degree 22 that's not uu and vv. Hence, by the Lemma, the graph can have at most 22 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 22.

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