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.

Let k,r,s be three integers such that , and . 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 , 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 to any node of 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 . 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 such that the set is composed of at least I=(|W|-(s+1)r)/(2|A|) intervals, whatever the shortest path IRS . 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 in order to have a graph with at most n nodes, and also for the desired range for k: .

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

which is for every .

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 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 tight?
- Is there some function f such that , where 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 edges) and treewidth  [Klo94, Theorem 5.3.2, page 58], and also bounded degree graphs of compactness  (Theorem 17).

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 , we will denote by k- - , and similarly for k- .

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

Next: Random Graphs Up: Specific Class of Graphs Previous: Planar Graphs   Contents

2000-03-21