Enumerating Planar Graphs of Bounded Treewidth

Question

I am looking for references for the following problem: given integers $n$ and $k$, enumerate all non-isomorphic planar graphs on $n$ vertices and treewidth $\leq k$. I'm interested both in theoretical and practical results, but mostly practical algorithms that are possible to code and run for as large as possible values of $n$ and $k$ (think $k \leq 5$ and $n \leq 15$). If you already have an answer, ignore the ramblings below.

The following approach works sort of ok for enumerating all non-isomorphic graphs on $n$ vertices and treewidth $\leq k$ (i.e when the planarity constraint is dropped):

(a) Enumerate all non-isomorphic graphs on $n-1$ vertices and treewidth $\leq k$.

(b) For each vertex $G$ on $n-1$ vertices and treewidth $\leq k$, every clique $C$ on $\leq k$ vertices in $G$ and every subset $S$ of edges in $C$, make $G'$ from $G - S$ by adding a new vertex $v$ adjacent to $C$. Add $G'$ to the list ${\cal L}$ of grahs on $n$ vertices and treewidth $\leq k$.

(c) Trim ${\cal L}$ by removing copies of the same graph.

A tempting way to extend this to enumerate planar graphs of treewidth $\leq k$ is to simply filter out the non-planar graphs at every iteration. Unfortunately this fails to generate all planar graphs of treewidth $\leq k$ (for example because it only enumerates $4$-degenerate graphs).

Of course we could enumerate all graphs on $n$ vertices and treewidth $\leq k$ and only then filter out the non-planar ones, but this fails to exploit that most graphs are non-planar and seems very sub-optimal.

Answer 1

There is a nice software which generates small planar graphs with respect to isomorphism which might help. As I see one of the problem was to generate non-isomorphic planar graphs and most of those planar graphs (on less than 15 vertices) are of small treewidth.

For checking whether their treewidth is smaller than given value $k$, one way is to use heuristic algorithms to speed up this calculation, just in the case that exact algorithms are not practical. e.g in a planar graph $G$ first we can find a diameter of $G$ and the corresponding path $P$ of length $d$ (which is a diameter). Then find a vertex $v\in P$ which has shortest longest distance ($l$) to any other vertex $u\in G\setminus P$ among all vertices $w\in P$. The treewidth of $G$ is at most $d+l$, if this is smaller than $k$ then we are done otherwise either apply some other heuristic algorithms or run the exact algorithm.

For less than 3-connected graphs it's also possible to apply heuristics by finding cut vertices and then fixing those vertices and finding the tree width of a remaining graph. But as the number of nodes is small ($15$) if the graph is $4$-connected then the diameter is not big and I think the first heuristic should work there. (I don't know if there is any 5 connected planar graph on at most 15 vertices, but as we know there is no $t$-connected planar graph for $t>5$)

As the size of largest obstruction for tree width $k$ is not known we cannot simply guess the upperbound value of treewidth of a given graph $G$. But it seems that at least for planar graphs it should not be so big (one should give a proof for this).

Answer 2

One can enumerate all pairs $G,B$ where $G$ is a planar graph with treewidth at most $k$, $B$ is a bag of size $k$ such that there exist a tree-decomposition of $G$ with $B$ as a bag.

Now for every pair $G,B$ where $G$ has $n-1$ vertices we build a new graph $G'$ for every subset $S$ of $B$ by adding a vertex $v$ with $S$ as neighbours and let $B'$ be a size $k$ subset of $B \cup v$. Add $G',B'$ if $G'$ is planar and not isomorphic to any pair already found.

An easy upper bound on how many entries one need to store is $n \choose k$ times the number of enumerated graphs but this is a pessimistic bound. For most graphs of treewidth k, most subsets of size k can not b a bag, e.g. a $k \times n$ grid has only $n \cdot 3^{k-1}$ possible bags.

I believe this will perform as well as the algorithm for non planar graphs since for every pair G,B we get a graph by making B a clique, most of these graphs will be non isomorphic.

There are several tricks one can apply to speed up this, I would suggest looking into: http://www.siam.org/meetings/alenex04/abstacts/HBodlaender.pdf