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