next up previous contents
Next: Random Graphs Up: Specific Class of Graphs Previous: Planar Graphs   Contents


Treewidth Bounded Graphs

The next result confirms the lower bound of Theorem 33, and gives a generalization. Note that graphs of treewidth 1 are trees, and therefore have compactness 1 by Theorem 3.


\begin{theorem}
For every $k$, $2 \leqs k \leqs (n/3)^{1/3}$, there exists an $...
...subdivision of the graph $K_{k,r}$\ with $r = \Theta(\sqrt{kn})$).
\end{theorem}

Let k,r,s be three integers such that $r \geqs k \geqs 2$, and $l \geqs 1$. Consider the graph G obtained by subdividing all the edges in 2l+1 nodes of the bipartite graph Kk,r. G has n = k+r+(2l+1)kr nodes and a treewidth $\min\{k,r\} = k$, see [Klo94, Lemma 2.2.1, page 18]. We consider a node x initially belonging to the k-partition of Kk,r, and a node y initially belonging to the r-partition of Kk,r. Let W be the set of all the nodes at an odd distance of x. A set A of arcs is composed of all the incident arcs from x, all the incident arcs of y, and all the arcs of the directed path going from x to y and whose tail is at an even distance from x.

The nodes of W and the arcs of A constitute a matrix of constraints of G, i.e., the shortest path from the tail of any arc $(a,b) \in A$ to any node of $w \in W$ is unique (see [FvLMS95,GG98] for a formal description of this technique): we put ``1'' in such a boolean matrix if the route from a to w must use the arc (a,b); ``0'' otherwise. The dimension of the matrix is $\vert W\vert \fois \vert A\vert$. We consider the submatrix M obtained by removing the rows corresponding to nodes of W belonging to the subdivision of the induced subgraph K1,r rooted in y. Therefore M has |W| - (s+1)r = (k-1)r(s-1) rows and |A| = k+r+s columns.

Every two rows of M differ by at least one place (note that this is false if we take all of W as the set of nodes). Therefore there exists some arc $(a,b) \in A$ such that the set $\cI(a,b)$ is composed of at least I=(|W|-(s+1)r)/(2|A|) intervals, whatever the shortest path IRS $(\cL,\cI)$. Indeed, the total number of intervals for all the arcs of A is at least (|W|-(s+1)r)/2, the number of 01-sequences for the columns of the matrix under row permutation (each such sequence begins a new interval).

Let r=s. This is possible because in this case n = 2kr2 + (k+1)r+k; so it suffices to choose any integer $r \geqs \sqrt{n/(3k)}$ in order to have a graph with at most n nodes, and also $r \geqs k$ for the desired range for k: $2 \leqs k \leqs (n/3)^{1/3}$.

\begin{displaymath}
I ~=~ \frac{\vert W\vert-(s+1)r}{2\vert A\vert} ~=~ \frac{(k-1)r(s+1)}{2(k+r+s)} ~>~
\frac{(k-1)r^2}{2(k+2r)}.
\end{displaymath}

Since $r \geqs k$, $k+2r \leqs 3r$, and thus I > (k-1)r/6. On the other hand n = 2kr2 + r(k+1)+k < 8(k-1)r2, for every $r \geqs k \geqs 2$. Thus $r > \sqrt{n/(8(k-1))}$. We get finally that

\begin{displaymath}
I ~>~ \frac{k-1}{6} \sqrt{\frac{n}{8(k-1)}} ~=~
\frac{1}{6\sqrt{8}}\sqrt{(k-1)n},
\end{displaymath}

which is $\Omega(\sqrt{kn})$ for every $k \geqs 2$.


\begin{theorem}[\cite{NN96}]\mbox{}
\beginsmall{itemize}
\item $\mbox{\rm SIRS}(...
...x{\rm SIRS}(k\mbox{\rm -trees}) \leqs 2^{k+1}$.
\endsmall{itemize}
\end{theorem}

Clearly the first result does not hold for partial 2-trees (a 2-tree obtained by deleting some edges), because it is well-known that partial 2-trees have treewidth at most 2, and compactness $\Omega(\sqrt{n})$ by Theorem 34. The second result is particularly interesting since, in general, k is a constant in comparison with n, the number of nodes.

In [FL96], there is another study covering 1-IRS on directed series-parallel graphs. They construct a shortest path 1-IRS for the directed case, and gave also a valid 1-ILS for the undirected case, however without explicit bound on the routing path length for the undirected case.

Open question 9    
- Is the bound $\mbox{\rm SIRS}(k\mbox{\rm -trees}) \leqs 2^{k+1}$ tight?
- Is there some function f such that $\mbox{\rm IRS}(\cT_k) \leqs f(k)
\sqrt{n}$, where $\cT_k$ is the class of graphs of treewidth at most k?

Note that even for the class of graphs having O(n) there exists some graphs with 1.18n edges (actually almost every n-node graph with $m \geqs 1.18n$ edges) and treewidth $\Theta(n)$ [Klo94, Theorem 5.3.2, page 58], and also bounded degree graphs of compactness $\Theta(n)$ (Theorem 17).


\begin{conjecture}
Every $n$-node graph of constant treewidth has compactness $o(n)$.
\end{conjecture}

Several works have been done about the trade-off between the dilation and the compactness for the class of multi-globe graphs. A multi-globe graphs is a subdivision of the graph Ka,b in such a way that all the edges of Ka,b are subdivided in the same number of nodes. This class provides a large set of counterexamples (actually used in Theorem 7, and 34) and includes the globe-graphs (used in Theorem 32, and 33).

For convenience, for every class of graphs $\cG$, we will denote by k- $\mbox{\rm dilation}(\cG) = \max_{G \in \cG} k$- $\mbox{\rm dilation}(G)$, and similarly for k- $\mbox{\rm stretch}(\cG)$.


\begin{theorem}\mbox{}
\beginsmall{itemize}
\item~{\bf\cite{TL97b}} $1$-$\mbox{\...
...\rmstretch}(\mbox{\emglobe}) \in [3-O(1/D),3]$.
\endsmall{itemize}
\end{theorem} 5

Note that, in most of the articles cited in Theorem 36, the diameter D of globe or multi-globe graphs is even.


next up previous contents
Next: Random Graphs Up: Specific Class of Graphs Previous: Planar Graphs   Contents

2000-03-21