<p>There is a <a href="http://cs.anu.edu.au/~bdm/plantri/" rel="nofollow">nice software</a> 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.</p>

<p>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. </p>

<p>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$)</p>

<p>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). </p>

CC BY-SA 3.0
2014-12-07T14:35:33.313Z
2014-12-07T14:35:33.313Z
Saeed
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>There are several tricks one can apply to speed up this, I would suggest looking into:
<a href="http://www.siam.org/meetings/alenex04/abstacts/HBodlaender.pdf" rel="nofollow">http://www.siam.org/meetings/alenex04/abstacts/HBodlaender.pdf</a></p>

CC BY-SA 3.0
2014-12-06T13:30:48.077Z
Won't all the enumerated graphs have bounded *pathwidth* rather than treewidth?
daniello
CC BY-SA 3.0
2014-12-07T14:55:45.590Z
I think you are right. the choice of B' is too limited.
Martin Vatshelle
CC BY-SA 3.0
2014-12-04T22:01:58.600Z
2014-12-07T14:24:41.627Z
2014-12-07T14:24:41.627Z
Martin Vatshelle
<p>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. </p>

<p>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):</p>

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

<p>(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$.</p>

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

<p>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). </p>

<p>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. </p>

CC BY-SA 3.0
2014-11-25T02:12:44.893Z
Are you sure that you want to implement it and test the result? Number of non-isomorphic trees is already exponential.
Saeed
CC BY-SA 3.0
2014-11-25T02:17:56.750Z
@Saeed: sure - for 20 nodes the number of trees is less than a million so I expect this to be feasible at least for $n \leq 15$.
daniello
CC BY-SA 3.0
2014-11-25T03:24:10.773Z
how about starting from $n$-vertex chordal graphs of max clique size $k + 1$, and remove edges to make it planar?
Yixin Cao
CC BY-SA 3.0
2014-11-25T10:13:53.523Z
@Yixin Cao this looks similar to enumerating graphs + tree decompositions of them (I.e the same graph is seen once per tree dec. of it). So far that has been quite slow (but some optimization a could make this approach viable)
daniello
CC BY-SA 3.0
2014-11-25T10:36:38.757Z
@Saeed currently i have a master student doing the coding and naive enumeration gets problematic at 8 nodes already. The idea is to eventually do computer aided reduction rule discovery for kernelization, in the style of arxiv.org/abs/0904.0727 - for this graphs on 15, maybe 20 nodes are exactly what we need.
daniello
CC BY-SA 3.0
2014-11-25T11:01:05.757Z
@daniello, I cannot see why for 8 node it's problemistic, by 3n−6 rule there is at most $2^{18}$ such graphs (assign 0,1 to edges, I counted even disconnected graphs), so there should be absolutely no problem with this (checking planarity is also easy in this small graphs, and even for 12 vertices this should work). I also should note that, I think it's better to edit your question, graph on 15 vertices is already bounded tree width. You are actually looking for planar graphs of small size. I have to say that treewidth of any planar graph with less than 15 vertices is less than 5 (your $k$).->
Saeed
CC BY-SA 3.0
2014-11-25T11:02:33.850Z
If you want to calculate exact treewidth of those graphs as well, then it's better to update your question. P.S: one more thing, maybe the problem is writing on file, which is maybe time consuming (for old hard drives) but then this is not a theoretical question, it's more technical, and you have to filter them to not save all of them.
Saeed
CC BY-SA 3.0
2014-11-25T11:51:46.473Z
@Saeed the problem is the isomorphism testing: while the number of graphs is not that large, filtering out isomorphic copies of the same graph takes a lot of time.
daniello
CC BY-SA 3.0
2014-11-25T12:19:23.847Z
@daniello, I see your point but did you see this application : http://cs.anu.edu.au/~bdm/plantri/, they claim they can generate 1M planar graphs in a second (with respect to isomorphism). (it's not exactly what you want though, for 1-2-3 connected planar graphs it seems to be perfect, there are not many 4-5 connected planar graphs on 15 vertices though).
Saeed
CC BY-SA 3.0
2014-11-25T12:26:39.473Z
@Saeed thanks this link looks very useful!
daniello
CC BY-SA 3.0
2014-12-02T21:23:17.480Z
@Saeed if nothing new pops up in a few days, could you summarize your comments in an answer?
daniello
CC BY-SA 3.0
2014-12-03T13:42:50.600Z
@daniello, The comment that I said treewidth of all such graphs is smaller (equal) to 5 is not very precise (at the moment I wrote a comment I had an idea to prove it but now I see it's not very careful and probably it's wrong), I'll think about it over a weekend and I'll try to prove (or disprove) it then I'll provide an answer (with link to plantri software).
Saeed
<reference-request><graph-theory><graph-algorithms><treewidth>
Enumerating Planar Graphs of Bounded Treewidth
daniello
# Enumerating Planar Graphs of Bounded Treewidth

(Asked by: username_0 on 2014-11-24)

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.

**Tags:** reference-request, graph-theory, graph-algorithms, treewidth
> **Comments:**
> **username_1**: Are you sure that you want to implement it and test the result? Number of non-isomorphic trees is already exponential.  
> **username_0**: @Saeed: sure - for 20 nodes the number of trees is less than a million so I expect this to be feasible at least for $n \leq 15$.  
> **username_2**: how about starting from $n$-vertex chordal graphs of max clique size $k + 1$, and remove edges to make it planar?  
> **username_0**: @Yixin Cao this looks similar to enumerating graphs + tree decompositions of them (I.e the same graph is seen once per tree dec. of it). So far that has been quite slow (but some optimization a could make this approach viable)  
> **username_0**: @Saeed currently i have a master student doing the coding and naive enumeration gets problematic at 8 nodes already. The idea is to eventually do computer aided reduction rule discovery for kernelization, in the style of arxiv.org/abs/0904.0727 - for this graphs on 15, maybe 20 nodes are exactly what we need.  
> **username_1**: @daniello, I cannot see why for 8 node it's problemistic, by 3n−6 rule there is at most $2^{18}$ such graphs (assign 0,1 to edges, I counted even disconnected graphs), so there should be absolutely no problem with this (checking planarity is also easy in this small graphs, and even for 12 vertices this should work). I also should note that, I think it's better to edit your question, graph on 15 vertices is already bounded tree width. You are actually looking for planar graphs of small size. I have to say that treewidth of any planar graph with less than 15 vertices is less than 5 (your $k$).->  
> **username_1**: If you want to calculate exact treewidth of those graphs as well, then it's better to update your question. P.S: one more thing, maybe the problem is writing on file, which is maybe time consuming (for old hard drives) but then this is not a theoretical question, it's more technical, and you have to filter them to not save all of them.  
> **username_0**: @Saeed the problem is the isomorphism testing: while the number of graphs is not that large, filtering out isomorphic copies of the same graph takes a lot of time.  
> **username_1**: @daniello, I see your point but did you see this application : http://cs.anu.edu.au/~bdm/plantri/, they claim they can generate 1M planar graphs in a second (with respect to isomorphism). (it's not exactly what you want though, for 1-2-3 connected planar graphs it seems to be perfect, there are not many 4-5 connected planar graphs on 15 vertices though).  
> **username_0**: @Saeed thanks this link looks very useful!  
> **username_0**: @Saeed if nothing new pops up in a few days, could you summarize your comments in an answer?  
> **username_1**: @daniello, The comment that I said treewidth of all such graphs is smaller (equal) to 5 is not very precise (at the moment I wrote a comment I had an idea to prove it but now I see it's not very careful and probably it's wrong), I'll think about it over a weekend and I'll try to prove (or disprove) it then I'll provide an answer (with link to plantri software).  

---

## 2 answers

### Answer by username_1 on 2014-12-07. Score: 2 | Accepted answer

There is a [nice software](http://cs.anu.edu.au/~bdm/plantri/) 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 by username_3 on 2014-12-04. Score: 1

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>

> **Comments:**
> **username_0**: Won't all the enumerated graphs have bounded *pathwidth* rather than treewidth?  
> **username_3**: I think you are right. the choice of B' is too limited.  

---

