Enumerating Planar Graphs of Bounded Treewidth 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.
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&gt;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).