9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you sure that you want to implement it and test the result? Number of non-isomorphic trees is already exponential. $\endgroup$ – Saeed Nov 25 '14 at 2:12
  • $\begingroup$ @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$. $\endgroup$ – daniello Nov 25 '14 at 2:17
  • 1
    $\begingroup$ how about starting from $n$-vertex chordal graphs of max clique size $k + 1$, and remove edges to make it planar? $\endgroup$ – Yixin Cao Nov 25 '14 at 3:24
  • $\begingroup$ @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) $\endgroup$ – daniello Nov 25 '14 at 10:13
  • 2
    $\begingroup$ @daniello, I see your point but did you see this application : 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). $\endgroup$ – Saeed Nov 25 '14 at 12:19
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Won't all the enumerated graphs have bounded pathwidth rather than treewidth? $\endgroup$ – daniello Dec 6 '14 at 13:30
  • $\begingroup$ I think you are right. the choice of B' is too limited. $\endgroup$ – Martin Vatshelle Dec 7 '14 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.