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