Extremal Compactness

Because Interval Routing is devoted to implement routing in general
networks, it is natural to wonder what is the compactness of an
*n*-node graph.

The compactness of an *n*-node graph cannot exceed *n*/2, because a
necessary condition to have *k* intervals for a set *I* is to have
,
and clearly the number of intervals of *I* is at most
|I|. The next result proposes a little improvement. The three next
results use randomization.

Theorem 15 is actually a consequence of a deeper result:
for every family
of subsets of
containing at
most *e*^{n/2}/*n* distinct subsets there exists a permutation
of
such that all the subsets of
are composed of at
most
intervals under .
It can be clearly
applied on IRS models where Condition 2a and/or 2b (disjunction of the
arc-labels) are relaxed,
representing the set of arcs, each
subsets representing an arc-label, and the permutation
representing the node-labeling.

Due to the next lower bound, *n*/4 is asymptotically a tight bound.

To a certain extent Interval Routing cannot be efficiently used for
the * t-regional routing problem* posed by Peleg
in [SRS97], that consists in optimal routing up to distance

Note that there exists a constructive proof for a worst-case
compactness of at least *n*/12 [GG98]. A third proof, using
randomization, for a -lower bound is given in [KK96].
They also show that
intervals might be required
simultaneously on
edges.

Against intuition, the next result shows that, in general, the compactness does not depend on the number of edges or on the maximum degree of the graph. It may be quite high even for sparse graphs.

As a corollary, there exists some graph with
edges,
for every
,
and of
compactness
.
Indeed, it suffices to choose a
graph satisfying Theorem 17 with
nodes,
and to connect
nodes of degree 1 to some nodes.
Clearly such a new graph has *n* nodes,
edges, and
compactness
.

A way to prove Theorem 17 is to use the result
of [GP96b] about the *memory requirement* of a graph, which
defines the smallest amount of memory needed to code any shortest path
routing function (see [FG97] for an introduction to Universal
Routing Schemes). In [GP96b] *n*-node graphs of degree bounded by
*d*,
for
,
of local
memory requirement
are constructed. This result,
combined with Theorem 1, implies Theorem 17
(for *d* = 3 with a slightly modification to have a 3-regular graph).

We have also the following isolated results to quickly check whether a graph has compactness 1: