arXiv:1202.4160v4 [cs.DS] 27 Jun 2016

Interval Routing Schemes for Circular-Arc Graphs
Frank Gurski
University of Düsseldorf
Institute of Computer Science
Algorithmics for Hard Problems Group
D-40225 Düsseldorf
frank.gurski@hhu.de

Patrick Gwydion Poullie∗
University of Zurich
Department of Informatics
Communication Systems Group
CH-8050 Zürich
poullie@ifi.uzh.ch

March 16, 2018

Abstract
Interval routing is a space efficient method to realize a distributed routing function. In this
paper we show that every circular-arc graph allows a shortest path strict 2-interval routing
scheme, i.e., by introducing a global order on the vertices and assigning at most two (strict)
intervals in this order to the ends of every edge allows to depict a routing function that
implies exclusively shortest paths. Since circular-arc graphs do not allow shortest path 1interval routing schemes in general, the result implies that the class of circular-arc graphs
has strict compactness 2, which was a hitherto open question. Additionally, we show that
the constructed 2-interval routing scheme is a 1-interval routing scheme with at most one
additional interval assigned at each vertex and we outline an algorithm to calculate the routing
scheme for circular-arc graphs in O(n2 ) time, where n is the number of vertices.
Keywords: interval routing, compact routing, circular-arc graphs, cyclic permutations

1

Introduction

Routing is an essential task that a network of processors or computers must be able to perform.
Interval routing is a space-efficient solution to this problem. Sets of consecutive destination addresses that use the same output port are grouped into intervals and then assigned to this port. In
this way, the storage space required is greatly reduced compared to the straight forward approach,
in which an output port is stored specifically for every destination address. Of course, the advantage in space efficiency depends heavily on the number of intervals assigned to the output ports,
which, in turn, depends on the address and network topology. Interval routing was first introduced
in [SK82, SK85]; for a discussion of interval routing we refer the reader to [vLT87, FJ88, BvLT91]
and for a detailed survey to [Gav00]. When theoretical aspects of interval routing are discussed,
the network is represented by a directed (symmetric) graph G = (V, A). As with many routing
methods, the problem is that space efficiency and path optimality are conflicting goals [PU89]: as
shown in [GG98], for every n ∈ N, there exists an n-vertex graph Gn such that for every shortest
path interval routing scheme (for short IRS) for Gn the maximal number of intervals per directed
edge is only bounded by Ω(n). Also, it is NP-hard to determine the most space efficient shortest
path IRS for a given graph [EMZ02, Fla97]. Other worst case results can be found in [TL99].
On the other hand, there are many special graph classes [FG98] including random graphs [GP98]
that are known to allow shortest path IRSs with a constantly bounded number of intervals on
all directed edges. If this number is a tight bound, it is denoted the compactness of the graph.
The compactness of undirected graphs is defined as the compactness of their directed symmetric
∗ Corresponding

author.

1

version1 and the compactness of a graph class as the smallest k, such that every graph in this
class has compactness at most k, if such k exists.
In this paper we show that the class of circular-arc graphs has (strict) compactness 2 by presenting an algorithm to construct a corresponding IRS. A different approach to realize space efficient,
shortest path routing in circular-arc graphs can be found in [DL02]. In [GP08] an O(log(|V |))-bit
distance labeling scheme is developed that allows for each pair of vertices in circular-arc graphs
to compute their exact distance in O(1) time. In [DYL06] an O(log2 (|V |))-bit routing labeling
scheme is developed that allows to make a routing decision in O(1) time for every vertex in an
arbitrary circular-arc graph. The resulting routing path has at most two more edges than the
respective shortest path. Nevertheless, our result is interesting, since interval graphs and unit
circular-arc graphs are included in the class of circular-arc graphs and known to have compactness
1 [FG98, NS96], while for the compactness of circular-arc graphs hitherto only a lower bound of 2
was known (cf. the graph in Fig. 1) and the solutions from [FG98] and [NS96] cannot be extended
to the class of circular-arc graphs.
While interval graphs can be represented by intervals on a line, circular-arc graphs can be
represented by arcs on a circle, that is to say, every circular-arc graph is the intersection graph of
a set of arcs on a circle. The first polynomial-time (O(|V |3 )) algorithm to recognize circular-arc
graphs and give a corresponding circular-arc model can be found in [Tuc80]. An algorithm with
linear runtime for the same purpose is given in [McC03]. In circular-arc graphs maximum cliques
can be computed much faster than in arbitrary graphs; an algorithm that determines a maximum
clique in a circular-arc graph in O(|E|+|V |·log(|V |)) time or even in O(|E|) time, if the circular-arc
endpoints are given in sorted order, is presented in [BK97]. A discussion of circular-arc graphs can
be found in [Hsu95]. Circular-arc graphs have, amongst others, applications in cyclic scheduling,
compiler design [Gol04, Tuc75], and genetics [Rob76].
This paper is organized as follows. In Section 2 we define cyclic permutations, circular-arc
graphs, and interval routing schemes. In Section 3 we prove the main result of this paper, namely
that every circular-arc graph allows a shortest path strict 2-interval routing scheme. To this end,
we choose an arbitrary circular-arc graph G = (V, A) and fix a cyclic permutation L on V , in
Section 3.1. In Section 3.2 we fix an arbitrary vertex v and partition V −{v} into the three sets Av ,
Bv , and Cv ; the vertices in these sets appear consecutively in L and are referred to as the vertices
to the right of v, the vertices face-to-face with v, and the vertices to the left of v, respectively. In
Section 3.3 we show that the vertices in the three sets Av , Bv , and Cv can be assigned to the
edges incident to v, such that the conditions of a shortest path strict 2-interval routing scheme
are fulfilled. In Section 4 we show that the upper bound of the number of intervals in a shortest
path strict 2-interval routing scheme constructed in this way is close to the number in an 1-IRS.
In Section 5 we outline how to implement the implied IRS in O(|V |2 ) time.

2
2.1

Preliminaries
Cyclic Permutations

Cyclic permutations are relevant for the two main subjects of this paper, namely circular-arc
graphs and non-linear interval routing schemes. Just like a permutation, a cyclic permutation
implies an order on a set with the only difference being that there is no distinct first, second, . . .,
or n-th element. We also define cyclic permutations on multisets, where we assume that multiple
appearances of an element are distinguishable, i.e., a multiset A = {a1 , . . . , an } on n elements is
identified with A0 = {(1, a1 ), . . . , (n, an )}.
Definition 2.1 (Cyclic Permutation) A cyclic permutation on a (multi-)set A with n elements
is a function C : A → A such that ∀a ∈ A : ∀i ∈ N+ : C i (a) = a ⇔ i mod n = 0.2 We call C (a)
the successor of a (in C ) and we write a C C (a).
1 The directed symmetric version of an undirected graph G = (V, E) is the directed graph G = (V, A) with
u
d
A = {(v, w), (w, v) | {v, w} ∈ E}.
2 If the condition holds for one element in A, it holds for all elements in A.

2

Every cyclic permutation is a bijective mapping. Let C be a cyclic permutation on a (multi)set A = {a1 , a2 , . . . , an }. One could imagine C as an arrangement of A on a clock face, for an
n-hour clock. To go through C beginning at ai ∈ A means to consider the elements in A as they
appear in C , beginning at ai . Next we define subsets of A that appear consecutively in C .
Definition 2.2 (Ring-Interval, Ring-Sequence) For a cyclic permutation C on a (multi-)set
A and a, b ∈ A, we recursively define the ring-interval from a to b (in C ) as
(
{a}
if a = b
[a, b]C :=
{a} ∪ [C (a), b]C else.
By ]a, b]C we indicate that the left endpoint is excluded, by [a, b[C that the right endpoint is excluded,
and by ]a, b[C that both endpoints are excluded. Therefore we have ]a, a], [a, a[, ]a, a[= ∅
The ring-sequence from a to b (in C ), denoted by S[a, b]C = (a, . . . , b), is the order in which
elements of [a, b]C appear when going through C beginning at a.
Construction 2.3 Let C be a cyclic permutation on a (multi-)set A and a, b, c, d ∈ A. If [a, b]C ∩
[c, d]C = ∅ and b C c, we have [a, b]C ∪ [c, d]C = [a, d]C .

2.2

Circular-Arc Graphs

We assume that the reader is familiar with basic graph theoretical definitions. The intersection
graph of a family of sets is the graph where the vertices are the sets, and the edges are the pairs
of sets that intersect. Every graph is the intersection graph of some family of sets. A graph is
an interval graph if it is the intersection graph of a finite set of intervals (line segments) on a line
and a unit interval graph if these intervals have unit length. A graph G is a circular-arc graph
if it is the intersection graph of a finite set of arcs on a circle; the latter we call an arc model of
G. Since an interval graph is a special case of a circular-arc graph, namely a circular-arc graph
that can be represented with a set of arcs that do not cover the entire circle, we define the set of
strict circular-arc graphs as the set of circular-arc graphs that are not interval graphs. Every strict
circular-arc graph is connected. A unit circular-arc graph is a circular-arc graph that has an arc
model in which the arcs have unit length. For a survey on circular-arc graphs see [LS09] and for
the definition of further special graph classes see [BLS99]. Fig. 1 illustrates a strict circular-arc
graph.

12

12

1

1

11
10

11

3

8

2

9

4

10

5

3

8

2

9

5

7
6
(a) Arc model

4

7
6

(b) Correspondence

(c) Graph representation

Figure 1: A (strict) circular-arc graph
A difference between interval graphs and circular-arc graphs, that is worth mentioning, is that
the maximal cliques of interval graphs can be associated to points of the “interval model” and
therefore an interval graph can have no more maximal cliques than vertices. In contrast, circulararc graphs may contain maximal cliques that do not correspond to points of some arc model
3

[LS09]. In fact, just as in arbitrary graphs, the number of maximal cliques in circular-arc graphs
can grow exponentially in the size of the graph [Tuc80]. For the special case that there is an arc
model where no three arcs cover the whole circle the number of maximal cliques is bounded by the
number of vertices of the graph [CFZ08]. Also maximal cliques may occur several times within
some arc model, which is addressed by multisets in this paper.
The following definition and the subsequent corollary formalize important graph-theoretic properties of circular-arc graphs.
Definition 2.4 (Clique-Cycle, Left Clique α(v), and Right Clique β(v)) Let G = (V, E)
be a circular-arc graph, MG be an arc model of G, and C be the circle of MG . To each point
p on C corresponds a clique that contains the vertices whose corresponding arcs contain p. Let
multiset Y contain all cliques that correspond to points on C and define X ⊆ Y as the multiset
of cliques we obtain, when we remove all cliques from Y that are not maximal with respect to
inclusion among the cliques in Y and all but one cliques that are equal. Pair (X, C ), where C is
the cyclic permutation on X that is implied by ordering the elements in X as their corresponding
points appear (clockwise) on C, is called a clique-cycle for G. For every vertex v ∈ V , there exist
two cliques a, b ∈ X such that a clique x ∈ X contains v if and only if x ∈ [a, b]C . We call a the
left clique of v, denoted by α(v), and b the right clique of v, denoted by β(v).
When circular-arc graphs are discussed in this paper, the argumentation is based on one of
their clique-cycles deduced from some arc model.
A frequently used notation in our paper is that of a dominating vertex, which is a vertex
adjacent to all other vertices of the graph. The set of all dominating vertices of graph G is
denoted by D(G). Since a dominating vertex d is adjacent to all the vertices, all the maximal
cliques contain it, wherefore d’s left and right clique form a cyclic interval that covers the entire
clique cycle.
Corollary 2.5 Let (X, C ) be a clique-cycle for a circular-arc graph G = (V, E) and d ∈ D(G) a
dominating vertex. The left clique α(d) and the right clique β(d) of d are not unique, but can be
chosen arbitrarily with β(d) C α(d) being the only constraint.
Consider the arc model of a circular-arc graph and two intersecting arcs v, w. The arcs v and
w can intersect in the following two ways: 1. The intersection of v and w constitutes another arc.
This is the case, (a) if v is included in w or vice versa, (b) if v and w are congruent, i.e., cover the
exact same part of the cycle, or (c) if exactly one endpoint of v lies in w and vice versa. 2. The
intersection of v and w constitutes two arcs (the corresponding vertices will be defined as counter
vertices in the subsequent definition). This is the case, if v and w jointly cover the circle and meet
at both ends.
Definition 2.6 (Counter Vertex C(v)) Let (X, C ) be a clique-cycle for a circular-arc graph G =
(V, E). We call w ∈ V a counter vertex of v ∈ V , if α(v), β(v) ∈ [α(w), β(w)]C and α(w), β(w) ∈
[α(v), β(v)]C and α(v) 6= α(w) (or, equivalently, β(v) 6= β(w)). We call (v, w) a pair of counter
vertices and denote the set of all counter vertices of v by C(v).3
The next corollary follows directly from the arc model of a circular-arc graph.
Corollary 2.7 Let G = (V, E) be a circular-arc graph and v ∈ V be a vertex with C(v) 6= ∅. Then
every vertex in V is adjacent to v or to every vertex in C(v), in other words, v and any of its
counter vertices constitute a dominating set.
Definition 2.8 (Reaching to the Left/Right) Let (X, C ) be a clique-cycle for a circular-arc
graph G = (V, E), v, w two adjacent vertices with v ∈
/ C(w) and x ∈ X a clique with v, w ∈ x.
We say, w reaches at least as far to the right as v if [x, β(v)]C ⊆ [x, β(w)]C , and w reaches
further to the right than v if [x, β(v)]C ⊂ [x, β(w)]C . Analogously, we define w reaches at least
as far to the left as v by [α(v), x]C ⊆ [α(w), x]C and w reaches further to the left than v by
[α(v), x]C ⊂ [α(w), x]C .
3 Note

that, w ∈ C(v) ⇔ v ∈ C(w).

4

Although the arcs corresponding to counter vertices cover very different areas of the circle, it
is impossible to say which of the two arcs “reaches further to the left or right”, when the point of
view is the middle of the circle.

2.3

Interval Routing Schemes

We assume that the reader is familiar with basic concepts of interval routing and refer to [Gav00]
for an exhaustive introduction and survey. If an IRS assigns at most k intervals to each (directed)
edge and only implies shortest paths, we denote it by k-IRS. If this k-IRS is furthermore strict,
which means that for every vertex v ∈ V no interval assigned to the outgoing edges of v contains v’s
number, it is denoted by k-SIRS. Definition 2.9 is needed for Definition 2.10, which is an alternative
definition for shortest path strict interval routing schemes that is equivalent to definitions in
literature but better suited for our purposes. To apply Definition 2.10 to an undirected graph (as
for example a circular-arc graph), the graph is converted to its directed, symmetric version. While
directed edges are often called arcs, we choose the former term to avoid confusion with the arcs
of a graph’s arc model.
Definition 2.9 (First Vertex F(u, w)) Let G = (V, A) be a directed graph and u, v, w ∈ V .
Vertex v ∈ V is a first vertex from u to w, if there exists a shortest directed path (u, v, . . . , w),
i.e., there is a shortest directed path from u to w, that first traverses v. The set of first vertices
from u to w is denoted by
F(u, w) = {v ∈ V | v is a first vertex from u to w}.
Definition 2.10 (Shortest Path Strict Interval Routing Scheme) Let G = (V, E) be a
directed graph. A shortest path strict interval routing scheme for G is a pair R = (L , I), where
L is a cyclic permutation on V , called the vertex order, and I, called the directed-edge-labeling,
maps every directed edge to a set of ring-intervals in L such that for every vertex v ∈ V ,
1. I maps the outgoing directed edges of v to a set of ring-intervals in L , such that the intervals
assigned to different directed edges never intersect,
2. for every vertex u 6= v one of these these ring-intervals contains u (vertex v must not appear
in one of these intervals), and
3. if u is contained in a ring-interval in I((v, w)), then w is a first vertex from v to u.
Let F be a vertex order. We say that v ∈ V given F suffices a shortest path k-SIRS, if
there exists a directed edge-labeling for G that maps every outgoing directed edge of v to at most
k ring-intervals in F , such that v satisfies the three constraints above.
Corollary 2.11 A directed graph G = (V, A) supports a shortest path k-SIRS, if a vertex order
F exists, such that every vertex v ∈ V given F suffices a shortest path k-SIRS.

3

Main result

The compactness of the class of circular-arc graphs has not been determined until now, which is
somehow surprising, since the class of circular-arc graphs is closely related to the class of interval
graphs and unit circular-arc graphs and both classes are known to have strict compactness 1
[NS96, FG98]. However, for the compactness of the class of circular-arc graphs only a lower bound
of 2 was known. In particular, circular-arc graphs exist that do not allow for optimal 1 interval
routing schemes, as, for example, a wheel graph, i.e., a cycle together with a dominating vertex,
with six outer vertices [FG98]. Also the circular-arc graph shown in Fig. 1 does not allow optimal
1 interval routing schemes. In this section we prove the main result of this paper, which is given
by the following theorem and shows that the lower bound of 2 for the compactness of circular-arc
graphs is indeed sharp.
5

Theorem 3.1 (Main Theorem) The class of circular-arc graphs has strict compactness 2.
Since every non-strict circular-arc graph G is an interval graph and therefore has strict compactness 1 [NS96], we only need to consider strict circular-arc graphs in the proof. For the rest of
this section let (X, C ) be a clique-cycle for an arbitrary strict circular-arc graph Gu = (V, E) and
G = (V, A) be the directed symmetric version of Gu .
Outline of the proof To show that there exists a shortest path 2-SIRS for G and thus Theorem
3.1 holds, we proceed as follows. In Section 3.1 we construct a cyclic permutation L on V . In
Section 3.2 we choose an arbitrary vertex v ∈ V and partition the vertices in V − {v} in three
disjoint ring-intervals Av , Bv , Cv in L in dependency on v. In order to show that v given L suffices
a shortest path 2-SIRS, we show how to define an directed edge-labeling Iv for the outgoing directed
edges of v that satisfies the corresponding constraints given in Definition 2.10. We consider each
of the three ring-intervals Av , Bv , Cv in Section 3.3.1 and 3.3.2 and show how the vertices in the
respective ring-interval can be sufficiently mapped to by Iv . Since we have chosen v arbitrarily, it
follows that every vertex in V suffices a shortest path 2-SIRS given L and therefore, by Corollary
2.11, G supports a shortest path 2-SIRS. Since Gu is an arbitrary strict circular-arc graph, this
proves Theorem 3.1.
The following notations are straight forward but may be formalized for convenience. Let
(v, w) ∈ E be a directed edge with Iv ((v, w)) = S, where S is a set of ring-intervals in L , and R be
a ring-interval in L . Assigning R to directed edge (v, w) means to define Iv : (v, w) 7→ S ∪ {R}. Of
course, when we start constructing Iv , every directed edge is mapped to the empty set. Let [a, b]L
and [c, d]L be two ring-intervals that can be joined to one ring-interval [a, d]L by Construction
2.3. If [a, b]L and [c, d]L are assigned to the same directed edge (v, w), we can redefine
Iv : (v, w) 7→ {[a, b]L , [c, d]L } by Iv : (v, w) 7→ {[a, d]L }
and therefore save one ring-interval on directed edge (v, w). This redefinition is called compressing
the (two) ring-intervals on directed edge (v, w) (to one ring-interval). Let V 0 ⊆ V be a set of
vertices. To distribute V 0 (over the outgoing directed edges of v) means to partition V 0 into
ring-intervals and assign these to outgoing directed edges of v (sufficiently). For convenience, we
sometimes refer to ring-intervals as intervals.

3.1

Definition of the Vertex Order

In this section we consider a circular-arc graph G = (V, E) together with a clique-cycle (X, C )
and show how to construct a cyclic permutation L on V that serves as the given vertex order.
The ordering is obtained by sorting the arcs using their left cliques as primary sort key and right
cliques as secondary sort key, making the first arc the successor of the last. A pseudocode for this
purpose is presented in Listing 1 and its idea is explained next.
By Corollary 2.5 the left and right clique of a dominating vertex are not unique. Since it
simplifies the proof, if all dominating vertices have the same left and thus also the same right
clique, these cliques are unified in Line 1. For a fixed z in Line 1, the generated cyclic permutation
is fully deterministic, except for the ordering of true twins.4 The dummy vertex introduced in
Line 4 is needed to close the cyclic order once all vertices are integrated in L . The loop in Line
6 runs once through all cliques in X (beginning at f, that is arbitrarily chosen in Line 2) in the
order defined by C (Line 13). For every visited clique n the loop in Line 8 integrates every vertex,
whose left clique is n, in L . By Line 9, vertices with the same left clique are ordered with respect
to their right clique. An example for the defined vertex ordering can be found in Fig. 1.
1 Fix z ∈ X arbitrarily and choose α(d) := C (z) and β(d) := z for all d ∈ D(G)
2 Choose f ∈ X arbitrarily
3 n := f
4 Two

vertices in a graph are called true twins if they are adjacent to the same set of vertices and to each other.

6

4
5
6
7
8
9
10
11
12
13
14
15
16
17

V := V ∪ {t} /∗ add dummy vertex t ∗/
p := t
do
A := {v ∈ V | α(v) = n}
while(A 6= ∅)
Choose a ∈ A such that every vertex in A reaches at least as far to the right as a.
L (p) := a
p := a
A := A − {a}
n := C (n)
while(n 6= f)
L (p) := L (t)
V = V − {t} /∗ remove dummy vertex t ∗/
return L
Listing 1: Definition of a cyclic order L on V that serves as the given vertex order.
The following observations are crucial for the rest of this paper.
Remark 3.2
1. The vertices are ordered primarily by their left clique, that is to say, vertices
having the same left clique appear consecutively in L .
2. Vertices with the same left clique are ordered in ascending order by their right clique.
3. For two vertices v, w ∈ V with v L w, we know that v and w are adjacent and either
(a) α(v) = α(w) and w reaches at least as far to the right as v, or
(b) α(v) C α(w), in other words, v reaches one clique further to the left than w.5
The next definition is based on Assertion 1 of the preceding remark, that is to say, on the fact
that, since vertices having the same left clique appear consecutively in L , for a given clique c ∈ X,
two vertices v, w ∈ c exist, such that the vertices in ring-interval [v, w]L are exactly those with
left clique c.
Definition 3.3 (Head Vertex H(c) and Tail Vertex T (c)) Let (X, C ) be a clique-cycle for
some circular-arc graph G = (V, E), L given by Listing 1, c ∈ X, and v, w ∈ c the unique
vertices such that [v, w]L = {x ∈ V | α(x) = c} (v and w are not necessarily distinct). We call v
the head vertex of c and w the tail vertex of c and denote them by H(c) and T (c), respectively.
Corollary 3.4 Let (X, C ) be a clique-cycle for a circular-arc graph G = (V, E), L given by Listing
1, and c ∈ X. The successor (in L ) of the tail vertex of c is the head vertex of the successor (in
C ) of c, i.e., L (T (c)) = H(C (c)).

3.2

Partition of the Vertex Order

The cyclic permutation L on V allows to state further definitions. We now fix v ∈ V arbitrarily
for the rest of the proof and show that v given L suffices a shortest path 2-SIRS. If v is a
dominating vertex, we can define Iv : (v, w) 7→ [w, w]L for every vertex w ∈ V − {v} and have
thereby shown that v given L suffices a shortest path 1-SIRS. Therefore, we now assume that v
is not a dominating vertex. Fig. 2a illustrates the subsequent Definition.
Definition 3.5 (Left Vertex lv ) Let (X, C ) be a clique-cycle for some circular-arc graph G =
(V, E), L given by Listing 1, and v ∈ V not a dominating vertex. Let L ⊂ V be the union of the
following two vertex sets. (i) The set of vertices that are adjacent to v and reach further to the
5 Because the relation “reaching to the right” is not defined, if v and w are counter vertices, we intuitively extend
Definition 2.8 to this case by fixing x = α(w).

7

v

v

mv

lv

(a) The green vertices are in set L of Definition 3.5.
The left vertex of v, which is also in L, is colored in
light green and the middle vertex of v in red.

(b) The green vertices are to the left of v, the red
vertices are to the right of v, and the black vertices
are face-to-face with v.

Figure 2: Two examples for the Definitions made in this section The fixed vertex v is colored blue.
The yellow line connects the vertices as they appear in vertex order L as generated by Listing 1.
left than v but are neither counter vertices of v nor dominating vertices. (ii) The set of vertices
in [H(α(v)), v[L .6 If L 6= ∅, we define the left vertex of v, denoted by lv , as the unique vertex in
L such that
∀w ∈ L : [w, v[L ⊆ [lv , v[L (or, equivalently, L ⊆ [lv , v[L ).
(1)
Theorem 3.6 Let (X, C ) be a clique-cycle for a circular-arc graph G = (V, E), L given by Listing
1, v ∈ V not a dominating vertex, lv the left vertex of v, and u 6= lv be a vertex that is adjacent
to v and reaches further to the left than v but is neither a dominating vertex nor a counter vertex
of v. Then lv reaches at least as far to the left as u.
Proof Assume u reaches further to the left than lv . Then by Definition 2.8 we know that
[α(lv ), α(v)]C ⊂ [α(u), α(v)]C , which implies that
S[α(u), α(v)]C = (α(u), . . . , α(lv ), . . . , α(v)).
Since L is primary ordered by the left cliques of the vertices, it follows
u L . . . L lv L . . . L v
and therefore [lv , v]L ⊂ [u, v]L . This contradicts (1) in Definition 3.5, since u ∈ L reaches further
to the left than v and is neither a dominating vertex nor a counter vertex of v.

In Definition 3.8 we partition the vertices in V − {v} into three ring-intervals in L . The
following argumentation gives the idea behind this partitioning and also proves Theorem 3.9.
Consider we go through L beginning at v. Since the vertices in L are primary ordered by their
left cliques, the left clique of the vertices first considered is α(v) (or C (α(v)), if v is the tail vertex
of clique α(v)). The next vertices traversed have left clique C (α(v)), followed by vertices with left
clique C 2 (α(v)), and so on. We eventually reach the set of vertices with left clique β(v). The last
vertex we come across in this set is T (β(v)) and fixed in Definition 3.7. The vertices we came
across so far (excluding v, including T (β(v))) will be defined as the “vertices to the right of v” in
Definition 3.8 and are adjacent to v, as v was contained in their left clique.
6 We

have D(G) ∩ [H(α(v)), v[L = ∅ and C(v) ∩ [H(α(v)), v[L = ∅.

8

Definition 3.7 (Middle Vertex mv ) Let (X, C ) be a clique-cycle for a circular-arc graph G =
(V, E), L given by Listing 1, and v ∈ V not a dominating vertex. We define the middle vertex of
v, denoted by mv = T (β(v)), as the tail vertex of the right clique of v.
When we continue visiting the vertices after mv in the same manner, the next vertex u we
come across that is not a dominating vertex but adjacent to v has to be lv , as we could find a
contradiction in the same manner as in the proof of Theorem 3.6, if we had u 6= lv . These vertices
after mv and before lv are defined as the “vertices face-to-face with v” in Definition 3.8. When
we continue to go through L , we eventually reach v again. These vertices from lv to v (excluding
v) are defined as the “vertices to the left of v” in Definition 3.8, which is illustrated in Fig. 2b.
Definition 3.8 (Av , Bv , Cv ) Let (X, C ) be a clique-cycle for a circular-arc graph G = (V, E),
L given by Listing 1, v ∈ V not a dominating vertex, lv the left vertex of v, if lv exists, and mv
the middle vertex of v. We define
1. the vertices to the right of v as Av =]v, mv ]L , and
2. the vertices face-to-face with v
(a) as Bv =]mv , v[L , if lv does not exist, or else
(b) as Bv =]mv , lv [L , and
3. the vertices to the left of v
(a) as Cv = [lv , v[L , if lv exists, or else
(b) as Cv = ∅.7
The next theorem follows from the argumentation between Theorem 3.6 and Definition 3.8.
Theorem 3.9 Let (X, C ) be a clique-cycle for a circular-arc graph G = (V, E), L given by Listing
1, and v ∈ V but not a dominating vertex.
1. Every vertex to the right of v is adjacent to v.
2. Every vertex face-to-face with v that is not a dominating vertex is not adjacent to v.

3.3

Definition of the Directed Edge-labeling

Next we show that v given L suffices a shortest path 2-SIRS by constructing a mapping Iv from
the set of outgoing directed edges of v to at most two ring-intervals in L , according to Definition
2.10. We investigate the vertices to the left of v and the vertices to the right of v in Section 3.3.1
and the vertices face-to-face with v in Section 3.3.2. For every vertex u in the respective interval,
we determine a first vertex w from v to u such that u and every vertex that is hitherto assigned
to directed edge (v, w) can be embraced by at most two ring-intervals in L . This is a simple task
for the vertices in Av and Cv and even for the vertices in Bv the approach is straight forward, if
there is a dominating vertex or a counter vertex of v. In fact, it only gets tricky, if there are no
dominating vertices and no counter vertices.
3.3.1

Vertices to the Left and Right

By the first assertion of Theorem 3.9 every vertex to the right of v is adjacent to v, wherefore these
vertices can be distributed by assigning [w, w]L to directed edge (v, w), for every vertex w ∈ Av .
Assume that we have Cv 6= ∅. In general, not every vertex in Cv is adjacent to v. Although lv is
adjacent to all vertices in Cv , it is generally not possible to assign Cv to directed edge (v, lv ), since
Cv may contain vertices that are adjacent to v (other than lv ), and therefore must be assigned to
7

We have Cv = L from Definition 3.5.

9

“their own directed edge”. Let vi ∈ Cv be a vertex that is adjacent to v and assume we start at vi
to go through L until we come across the next vertex that is adjacent to v or v itself. Denote this
vertex vj . We can show that vi is adjacent to every in ]vi , vj ]L , wherefore we can assign [vi , vj [L
to directed edge (v, vi ). Therefore the vertices to the left of v can be distributed by assigning
every vertex w ∈ Cv to directed edge (v, w), if w is adjacent to v, and else to directed edge (v, w0 ),
where w0 is the first vertex that precedes w in L and is adjacent to v. Theorem 3.10 proves the
outlined idea formally. When distributing the vertices in sets Av and Cv as just outlined, every
outgoing directed edge of v (except for edges incident to dominating vertices face-to-face with v,
which are not yet labeled) gets one ring-interval assigned.
Theorem 3.10 Let (X, C ) be a clique-cycle for a circular-arc graph G = (V, E), L given by
Listing 1, v ∈ V but not a dominating vertex, and lv the left vertex of v (then the vertices in
[lv , v[L are the vertices to the left of v). Let S[lv , v]L = (lv = v1 , v2 , . . . , vn = v) be the sequence
of vertices that we obtain, when we order the vertices in [lv , v[L that are adjacent to v as they
appear in ring-sequence S[lv , v[L and append v. For 1 ≤ i < n and x ∈ [vi , vi+1 [L , vertex vi is a
first vertex from v to x.
Proof For some i, 1 ≤ i < n, let x ∈ [vi , vi+1 [L . Clearly the theorem holds if x = vi . If
x 6= vi , x does not appear in (v1 , v2 , . . . , vn ) and therefore is not adjacent to v. Since the vertices
in L are primary ordered by their left clique and vi appears before x in S[lv , v]L , it follows that
the left clique of x is in [α(vi ), α(v)]C . Since vi is adjacent to v, vi is contained in every clique
in [α(vi ), α(v)]C . This implies that vi is contained in the left clique of x and thus vi and x are
adjacent. Therefore (v, vi , x) is a shortest path between v and x and vi is a first vertex from v to
x.

3.3.2

Vertices Face-to-Face

This section discusses the distribution of vertices face-to-face with v. It is probably the common case, that neither counter nor dominating vertices exist, since only then path lengths are
unbounded. Thus, this case is discussed in the next paragraph and the subsequent paragraph
discusses the remaining cases.
3.3.2.1 Neither Dominating nor Counter Vertices exist In this case, lv always reaches
further to the left than v and there is at least one vertex adjacent to v that reaches further to the
right. Let w ∈ V be a vertex that is not adjacent to v, L be the set of vertices adjacent to v that
reach farthest to the left and R be the set of vertices adjacent to v that reach farthest to the right
(L and R might intersect). As evident from the arc model of G, every vertex in L or every vertex
in R is a first vertex from v to w (cf. Corollary 3.13). Since we have lv ∈ L, we now fix a vertex
adjacent to v that reaches farthest to the right.
Definition 3.11 (Right Vertex rv ) Let (X, C ) be a clique-cycle for a strict circular-arc graph
G = (V, E) without dominating vertices and without counter vertices, L given by Listing 1, v ∈ V ,
lv the left vertex of v, mv the middle vertex of v, and R ⊂ V be the set of vertices that are adjacent
to v and reach farthest to the right. We define the right vertex of v, denoted by rv , as lv , if lv ∈ R,
or as mv , if mv ∈ R, or else as an arbitrary vertex in R.
In order to show that v suffices a shortest path 2-SIRS given L , we could choose rv arbitrarily
in R even if lv ∈ R or mv ∈ R. However, we will show that v given L suffices a shortest path
1-SIRS, if lv ∈ R or mv ∈ R. The next definition redefines the notation of the left and right vertex
as a function, in order to allow recursive usage to easily determine a first vertex from v to every
vertex. The subsequent corollary is clear when illustrated.
Definition 3.12 (l(v), r(v) and Lv (u), Rv (u)) Let (X, C ) be a clique-cycle for a strict circulararc graph G = (V, E) without dominating vertices and without counter vertices, cyclic permutation

10

L given by Listing 1, and v ∈ V . We define l(v) as the left vertex of v and r(v) as the right
vertex of v.8 For u ∈ V , we define Lv (u) as the smallest i such that u is adjacent to li (v) and
Rv (u) as the smallest i such that u is adjacent to ri (v).
Corollary 3.13 Let (X, C ) be a clique-cycle for a strict circular-arc graph G = (V, E) without
dominating vertices and without counter vertices, cyclic permutation L given by Listing 1, and
v ∈ V . The following three assertions hold for every vertex u ∈ V that is not adjacent to v.
1. If Lv (u) < Rv (u), then lv is a first vertex from v to u.
2. If Lv (u) > Rv (u), then rv is a first vertex from v to u.
3. If Lv (u) = Rv (u), then lv and rv are first vertices from v to u.
Since no vertex in Bv is adjacent to v, the corollary implies that lv or rv is a first vertex from
v to every vertex in Bv . Since sequence r1 (v), r2 (v), . . . “runs” through the clique-cycle as implied
by C and sequence l1 (v), l2 (v), . . . “runs” through the clique-cycle as implied by C −1 , that is to
say, in the other direction, there exists an i ∈ N such that li (v) and ri (v) “meet”, or more formally,
are adjacent or equal. This number is fixed in the following definition.
Definition 3.14 (Apex Number) Let (X, C ) be a clique-cycle for a strict circular-arc graph
G = (V, E) without dominating vertices and without counter vertices, L given by Listing 1, and
v ∈ V . If we have α(l1 (v)) = β(r1 (v)) or [α(v), β(v)]C ⊂ [β(r1 (v)), α(l1 (v))]C we set i = 1,
otherwise we define i as the smallest number greater than 1 such that li (v) and ri (v) are adjacent
or equal. We call integer i the apex number of v.
The separate treatment for apex number i = 1 in Definition 3.14 ensures that the arcs of
li (v) and ri (v) intersect/meet adverse to v on the circle and therefore the arcs of l1 (v), . . . , li (v),
r1 (v), . . . , ri (v), and v to cover the entire circle. In particular, if lv and rv intersect in v’s arc they
cannot cover the entire cycle, since they are not counter vertices, but the apex number would be
defined as 1, if only the second part of the case distinction were in place.
By the definition, for apex number i > 2 vertices ri (v) and li−1 (v) are adjacent if and only
i
if l (v) and ri−1 (v) are adjacent. Furthermore, for 2 ≤ j, k < i vertices rj (v) and lk (v) are not
adjacent.
The following Theorem 3.15 shows that there exists a vertex sv ∈ Bv with li (v), ri (v) ∈ α(sv ),
where i is the appex number of v, such that rv is a first vertex from v to every vertex in Br =
]mv , sv ]L and vertex lv is a first vertex from v to every vertex in Bl =]sv , lv ]L . Since Theorem
3.15 implies that the vertices in Bv can be distributed by assigning Bl to directed edge (v, lv ) and
Br to directed edge (v, rv ), the main theorem (Theorem 3.1) follows for the case in which neither
dominating vertices nor counter vertices exist.
Theorem 3.15 Let (X, C ) be a clique-cycle for a strict circular-arc graph G = (V, E) without
dominating vertices and without counter vertices, L given by Listing 1, v ∈ V , lv the left vertex of
v, mv the middle vertex of v, and rv the right vertex of v. There exists a vertex sv ∈ ]mv , lv [L such
that, for every vertex w ∈ ]mv , sv ]L , we have rv ∈ F(v, w), and for every vertex w0 ∈ ]sv , lv ]L ,
we have lv ∈ F(v, w0 ).
Proof Let i the apex number of v.
If i = 1 the theorem holds for sv = L −1 (lv ), since every vertex in ]mv , lv [L is adjacent to rv .
If i > 1 and li (v) = ri (v), we have
∀w ∈ ]mv , T (β(ri−1 (v)))]L : Rv (w) ≤ i − 1 ≤ Lv (w)
and
∀w ∈ ]T (β(ri−1 (v))), lv [L : Lv (w) ≤ Rv (w),
wherefore, by Corollary 3.13, Theorem 3.15 holds for sv = T (β(ri−1 (v))).
11

C

l

i−1

i−2

(v)

(v)
u

{
{

l

B

i

r (v)

A
i−2

r (v)
i−1

r (v)

Figure 3: This picture illustrates the proof of Theorem 3.15 and partially shows a circular-arc
graph, where the lines represent arcs. A line ends with a triangle, if it may reach not further to
left or right, respectively. The upper two lines with a dotted end illustrate that an arc, that has
its right end in the interval depicted by the rotated curly bracket, may reach no further to the
left than the triangle of the respective line. We begin to search for u at the right end of the lower
curly bracket. The rotated square brackets on top mark the areas of the left cliques of the vertices
in sets A, B, C. The case in which li−1 (v) = u looks similar.
The following argumentation is partially illustrated in Fig. 3.
If i > 1 and li (v) 6= ri (v), let
A =]mv , T (β(ri−1 (v)))]L ,
and a ∈ A. We have Rv (a) ≤ i − 1, because a is adjacent to a vertex in {r1 (v), r2 (v), . . . , ri−1 (v)}.
When lv reaches further to the right than v, a might appear in a clique in ]β(v), β(lv )]C and,
therefore, be adjacent to lv , which implies Lv (a) = 1. However, in this case, we also have Rv (a) =
1. Therefore, we could only have Lv (a) < Rv (a), when a reaches so far to the right, such that it is
adjacent to li−2 (v). However, in this case a would reach further to the left than li−1 (v), because a
is adjacent to ri−1 (v) and li−1 (v) is “at most” adjacent to ri (v). Because li−1 (v) is the left vertex
of li−2 (v) this contradicts Theorem 3.6. Thus, Corollary 3.13 implies
∀a ∈ A : rv ∈ F(v, a).

(2)

Now we go through L beginning at L (T (β(ri−1 (v))) = H(C (β(ri−1 (v)))),9 in other words,
we begin at the first vertex after the “last” vertex in A, until we eventually come across a vertex
u that either is li−1 (v) or adjacent to li−1 (v).10 We define
B =]T (β(ri−1 (v))), u[L
i.e. B is the set of vertices after T (β(ri−1 (v))) and before u in L . Note that, by the choice of u,
no vertex in B is adjacent to li−1 (v).
Assume there is a vertex x ∈ B that is not adjacent to ri (v). When we go through C beginning
at α(ri−1 (v)) we eventually come across β(ri−1 (v)) (since ri (v) and ri−1 (v) are adjacent, we have
α(ri (v)) ∈ [α(ri−1 (v)), β(ri−1 (v))]C ). Before we come across α(x), we come across β(ri (v)),
since otherwise x and ri (v) would be adjacent. We do not come across α(li−1 (v)) until we came
across β(x), since otherwise x and li−1 (v) would be adjacent. It follows that li−1 (v) and ri (v)
are not adjacent and, because li (v) is adjacent to li−1 (v) and ri (v), it follows that li (v) reaches
further to the right than ri (v). Because li (v) and ri (v) are adjacent, α(li (v)) must appear in
[α(ri (v)), β(ri (v))]C . It cannot appear in [α(ri (v)), β(ri−1 (v))]C , because then li (v) is adjacent to
ri−1 (v), which contradicts Definition 3.11, since li (v) reaches further to the right than ri (v) and
8 It follows that l2 (v) is the left vertex of the left vertex of v and r 2 (v) is the right vertex of the right vertex of
v, etc.
9 This equality holds by Corollary 3.4.
10 This vertex u may be li (v). Also there may be vertices in A that are adjacent to li−1 (v), in other words, we
may have “passed by” a vertex that is adjacent to li−1 (v) already.

12

ri (v) is the right vertex of ri−1 (v). Therefore, we have α(li (v)) ∈ ]β(ri−1 (v)), β(ri (v))]C . Because
we came across β(ri (v)) before α(x), we have ]β(ri−1 (v)), β(ri (v))]C ⊂ ]β(ri−1 (v)), α(x)[C and,
therefore,
α(li (v)) ∈ ]β(ri−1 (v)), α(x)[C .
(3)
Since the vertices in L are primary ordered by their left clique, Inclusion (3) implies
li (v) ∈ [H(C (β(ri−1 (v)))), x]L .

(4)

Remember that we began at H(C (β(ri−1 (v)))) to go through L until we found a vertex u that is
adjacent to li−1 (v). Inclusion (4) implies that we must have come across li (v) before x. But then
we have u = li (v). Since
x∈
/ [H(C (β(ri−1 (v)))), li (v)[L = [L (T (β(ri−1 (v)))), u[L = B
contradicts the initial assumption, every vertex in B is adjacent to ri (v).
Since by the choice of u no vertex in B is adjacent to li−1 (v), we have
∀b ∈ B : Lv (b) ≥ i = Rv (b),
which, by Corollary 3.13, implies
∀b ∈ B : rv ∈ F(v, b).

(5)

We define sv = L −1 (u). Since the ring-intervals A and B appear consecutively in L , by Construction 2.3, we have
A ∪ B = ]mv , u[L = ]mv , sv ]L .
(6)
From (2), (5), and (6) it follows
∀w ∈]mv , sv ] : rv ∈ F(v, w).

(7)

Since the vertices in L are primary ordered by their left cliques, no vertex
w ∈ [H(C (β(ri−1 (v)))), li−1 (v)]L
is adjacent to ri−1 (v) and therefore we have Rv (w) ≥ i. We define
C =]sv , li−1 (v)[L
i.e. C is the set of vertices after sv and before li−1 (v) in L . Note that
B, C ⊆ [H(C (β(ri−1 (v)))), li−1 (v)]L .
We have
∀c ∈ [α(L (sv )), α(li−1 (v))]C : li (v) ∈ c

(8)

since otherwise u = L (sv ) would reach further to the left than l (v) although both are adjacent
to li−1 (v) and li (v) is the left vertex of li−1 (v). This would contradict Theorem 3.6. It follows
i

∀c ∈ C : Lv (c) ≤ i ≤ Rv (c),
which, by Corollary 3.13, implies
∀c ∈ C : lv ∈ F(v, c).

(9)

∀w ∈ [li−1 (v), lv [L : lv ∈ F(v, w).

(10)

Obviously we have
By Construction 2.3, we have C ∪ [l

i−1

(v), lv [L =]sv , lv [L and therefore (9) and (10) imply

∀w ∈]sv , lv [L : lv ∈ F(v, w).
13

(11)

The statement follows from (7) and (11).



In Section 3.3.1 we assigned [lv , x]L to directed edge (v, lv ) for some vertex x to the left of
v. If ]sv , lv [L is assigned to directed edge (v, lv ) additionally (as implied by Theorem 3.15) the
intervals on directed edge (v, lv ) can be compressed. Therefore, if neither dominating vertices nor
counter vertices exist, v given L suffices a shortest path 2-SIRS, but only (v, rv ) is assigned two
ring-intervals.
Below Definition 3.11 we stated that v given L suffices a shortest path 1-SIRS, if we can
choose rv = lv or rv = mv . This is the case because then the ring-intervals assigned to directed
edge (v, rv ) can be compressed as well.
Theorem 3.16 covers a further case where v given L suffices a shortest path 1-SIRS. Since
Theorem 3.16 is not essential for the proof of Theorem 3.1, we leave the proof to the interested
reader.
Theorem 3.16 Let (X, C ) be a clique-cycle for a circular-arc graph G = (V, E), L given by
Listing 1, v ∈ V not a dominating vertex, lv the left vertex of v, and mv the middle vertex of v.
If mv is adjacent to every vertex face-to-face with v that lv is not adjacent to, v suffices a shortest
path 1-SIRS.
3.3.2.2 Dominating Vertices or Counter Vertices exist In the foregoing section the existence of dominating and counter vertices was excluded and is therefore discussed in this section.
The vertices to be distributed are those face-to-face with v, i.e., the vertices in Bv . By Theorem
3.9, the only vertices in Bv that are adjacent to v are dominating vertices; this case is considered
first. Next, the case where dominating vertices not face-to-face with v or counter vertices of v
exist is addressed. Finally, the case where a pair of counter vertices exists (but v has no counter
vertex) is discussed.
Dominating Face-to-Face Vertices exist Listing 1 ensures that all dominating vertices
appear consecutively in L , wherefore we can find two dominating vertices dl and dr such that
[dl , dr ]L = D(G). Let x ∈ V such that ]mv , x]L = Bv . Since by Theorem 3.9, D(G) are the only
vertices in Bv that are adjacent to v, we can assign ]mv , dl ]L to directed edge (v, dl ), [dr , x]L to
directed edge (v, dr ), and for the remaining dominating vertices di ∈ ]dl , dr [, [di , di ]L to directed
edge (v, di ). It follows that v given L suffices a shortest path 1-SIRS.
Dominating Face-to-Face Vertices do not exist If there are no dominating vertices in
Bv , Theorem 3.9 implies that no vertex in Bv is adjacent to v. Therefore, by Corollary 2.7, every
vertex that is a counter vertex of v is adjacent to every vertex in Bv . Let u ∈ C(v) ∪ D(G) and
w ∈ Bv . Then u is a first vertex from v to w, wherefore we can assign ring-interval Bv to directed
edge (v, u), which had hitherto one ring-interval assigned. Thus, v given L suffices a shortest
path 2-SIRS, wherein only directed edge (v, u) has two ring-intervals assigned. By Theorem 3.16,
v given L suffices a shortest path 1-SIRS, if mv ∈ C(v) ∪ D(G).
Pairs of Counter Vertices Exist but v is in none of them Assume G does not contain
dominating vertices and the considered vertex v has no counter vertices but there exists at least
one pair (w, cw ) of counter vertices. We have Bv = ]mv , lv [L and no vertex in Bv is adjacent to
v. We make a distinction of cases for whether v is adjacent to one or to both counter vertices.
Assume v is adjacent to w as well as cw . There is a clique c ∈ X that contains v, w, and cw .
When we begin at c to go through C , we eventually reach a clique d that contains only one of w
or cw and not the other. Without loss of generality, let w be contained in d and let e be the first
clique that contains cw again. e is the left clique of cw and contains lv (we might have cw = lv ),
as otherwise, cw would reach further to the left than lv , which contradicts Theorem 3.6. Since
w and cw are counter vertices, all cliques we came across contained w. Since the vertices in L
are primary ordered by their left cliques and we also must have traversed β(v), which contains
mv , every vertex in Bv = ]mv , lv [L appeared in at least one of the cliques we came across.
14

Therefore, w is adjacent to every vertex in Bv . Since Iv hitherto maps directed edge (v, w) to one
ring-interval, we can assign Bv to directed edge (v, w). Thus, v given L suffices a shortest path
2-SIRS, wherein only directed edge (v, w) is actually mapped to two ring-intervals.
Now assume v is adjacent to one of the counter vertices and not to the other. Without loss of
generality, let this vertex be w. Let r be a vertex adjacent to v that, similar to Definition 3.11,
reaches farthest to the right. Since, by Theorem 3.6, lv is one of the vertices adjacent to v that
reaches farthest to the left, lv as well as r are adjacent to cw . In fact, we might have w = lv or
w = r. Let mr be the middle vertex of r and Ar = ]r, mr ]L the set of vertices to the right of r. Ar
is not empty, since otherwise G would be an interval graph. Also mv is contained in Ar , if r 6= mv .
By Theorem 3.9, every vertex in Ar is adjacent to r. Consider we go through L beginning at
L (mv ) until we reach mr or lv . If we have lv = mr , we consider it as reaching lv . If we first reach
lv , we exactly traversed the vertices in ]mv , lv ]L ⊆ Bv . It follows that we have Bv ⊆ Ar and thus
assign Bv =]mv , lv [L to directed edge (v, r). Now assume we first reach mr . By Theorem 3.9,
every vertex in ]mv , mr ]L ⊆ Ar is adjacent to r, wherefore we can assign ]mv , mr ]L to directed
edge (v, r). If L (mr ) = lv , all vertices in Bv are distributed. Otherwise let X =]mr , lv [L ⊂ Bv be
the vertices left to be distributed. Since, by Theorem 3.6, lv is a vertex adjacent to v that reaches
farthest to the left and lv is adjacent to cw , for every vertex u ∈ X either (v, lv , u) or (v, lv , cw , u)
is a shortest path. Thus, we can assign X to directed edge (v, lv ) (and compress the two intervals
on this edge), wherefore all vertices are distributed and only directed edge (v, r) is assigned two
ring intervals.

4

Improving the Space Requirement

This section shows that although circular-arc graphs do not allow shortest path 1-IRSs in general,
the number of intervals in a shortest path 2-SIRS for a circular-arc graph is bounded close to the
number of intervals in an 1-IRS. Let Gd = (V, A) be the directed symmetric version of a strict
circular-arc graph. A shortest path 2-SIRS for Gd can be obtained by ordering the vertices of Gd
according to Listing 1 and then labeling the outgoing directed edges of every vertex according to
Section 3.3.1 and 3.3.2. As pointed out in these sections, there is at most one outgoing edge per
vertex that is assigned two intervals. We have |V | ≤ |A|/2, since G is a strict circular-arc graph,
and |V | = |A|/2 only holds when G is a ring in which case our labeling yields a shortest path 1SIRS. Therefore, the number of intervals in the constructed 2-SIRS is less than |A|+|V | = 1.5·|A|,
while already a 1-IRS for Gd permits up to |A| intervals.

5

Implementation

This section outlines how the interval routing scheme implied by the proof of Theorem 3.1 can
be implemented. Let G = (V, E) be a circular-arc graph with |V | = n and |E| = m and (X, C )
be a clique-cycle for G with |X| = c maximal cliques (X does not need to contain sets of vertices;
plain elements representing the cliques are sufficient). We discuss how the vertex order L and
the critical vertices lv , mv , rv , sv for every vertex v ∈ V can be determined in O(c + n2 ) time. We
assume that every vertex v ∈ V has a pointer α(v) to its left clique and a pointer β(v) to its right
clique in X.
We define broadness of a vertex v as the number of cliques in X that contain v. By numbering
the elements in X as they appear in C , beginning at an arbitrary element, we construct a bijective
mapping N : X → {1, 2, . . . , |X|}, which allows to compute the broadness of a vertex in O(1) time.
Sorting the vertices ascending by their broadness requires O(n · log(n)) time. We introduce a list
Q(c) for every clique c ∈ X. Next the vertices are traversed in the sorted order and every vertex
v is added to list Q(α(v)). By concatenating the lists as their respective cliques appear in C we
obtain the vertex order L in O(n · log(n)) time. The left vertex lv of a given vertex v ∈ V can
be determined as follows: we inspect all vertices that are adjacent to v and store the vertex w
that reaches farthest to the left (for two adjacent vertices w, w0 , we can determine in constant

15

time which one reaches further to the left, by considering N (α(w)) and N (α(w0 ))) and appears
first in Q(α(w)) (this can also be decided in constant time, by numbering the elements in each
list consecutively). Vertex w must be lv . It follows that the set of left vertices can be computed
in O(m) time. The set of right vertices can be computed in similarly. Determining the set of
middle vertices is simpler and can be accomplished in O(n). For a given vertex v, li (v) and ri (v)
can be determined by traversing the sequences l1 (v), l2 (v), . . . and r1 (v), r2 (v), . . . synchronously;
then the determination of sv is a simple task and can be done in O(n) for a specific vertex and in
O(n2 ) for all vertices.
Since the algorithm includes constant time operations on the elements in X and |X| = c is linear
within the number of vertices, the overall runtime is O(c + n2 + m) = O(n2 ). The algorithm can
be extended to handle the existence of dominating and counter vertices without exceeding this
time bound.

6

Conclusions

We showed that the class of circular-arc graphs has strict compactness 2. Throughout the proof
special cases of strict circular-arc graphs that allow 1-SIRSs were highlighted (not all cases were
pointed out for the sake of brevity), which is in particular interesting, since the class of circular-arc
graphs is a super-class of the class of interval and unit circular-arc graphs, which always allow
1-SIRSs. We showed that the constructed 2-SIRS requires a number of intervals that is closer
to the maximal number of intervals in an 1-IRS than in a 2-IRS. An open question is, if strict
circular-arc graphs exist that allow 1-SIRS but the vertex ordering generated by Listing 1 does
not allow these.

References
[BK97]

Binay K. Bhattacharya and Damon Kaller. An O(m + n · log(n)) algorithm for the
maximum-clique problem in circular-arc graphs. Journal of Algorithms, 25(2):336–358,
1997.

[BLS99]

Andreas Brandstädt, Van Bang Le, and Jereny P. Spinrad. Graph Classes: A Survey.
Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 1999.

[BvLT91] Erwin M. Bakker, Jan van Leeuwen, and Richard B. Tan. Linear interval routing. The
Computer Journal, 30:298–307, 1991.
[CFZ08]

Gabrio Caimi, Martin Fuchsberger, and Rico Zenklusen. About maximal cliques in a
certain class of circular-arc graphs. Working paper, Institut für Operations Research,
ETH Zurich, CH-8092 Zürich, 2008.

[DL02]

Feodor F. Dragan and Irina Lomonosov. New routing schemes for interval, circular-arc,
and permutation graphs. In IASTED PDCS’02, pages 78–83, 2002.

[DYL06] Feodor F. Dragan, Chenyu Yan, and Irina Lomonosov. Collective tree spanners of
graphs. SIAM Journal on Discrete Mathematics, 20(1):241–260, 2006.
[EMZ02] Tamar Eilam, Shlomo Moran, and Shmuel Zaks. The complexity of the characterization
of networks supporting shortest-path interval routing. Theor. Comput. Sci., 289:85–104,
2002.
[FG98]

Pierre Fraigniaud and Cyril Gavoille. Interval routing schemes. Algorithmica, 21(2):155–
182, 1998.

[FJ88]

Greg N. Frederickson and Ravi Janardan. Designing networks with compact routing
tables. Algorithmica, 3:171–190, 1988.

16

[Fla97]

Michele Flammini. On the hardness of devising interval routing schemes. Parallel
Process. Lett, 7(1):39–47, 1997.

[Gav00]

Cyril Gavoille. A survey on interval routing. Theoretical Computer Science, 245:785–
796, 2000.

[GG98]

Eric Guevremont and Cyril Gavoille. Worst case bounds for shortest path interval
routing. Journal of Algorithms, 27:1–25, 1998.

[Gol04]

Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs (Annals of
Discrete Mathematics, Vol 57). North-Holland Publishing Co., Amsterdam, The Netherlands, 2004.

[GP98]

Cyril Gavoille and David Peleg. The compactness of interval routing for almost all
graphs. In Proceedings of Internat. Symp. on Distributed Computing (DISC), volume
1499 of Lecture Notes in Computer Science, pages 161–174. Springer Verlag, 1998.

[GP08]

Cyril Gavoille and Christophe Paul. Optimal distance labeling for interval graphs and
related graph families. SIAM Journal on Discrete Mathematics, 22(3):1239–1258, 2008.

[Hsu95]

Wen-Lian Hsu. O(m · n) algorithms for the recognition and isomorphism problems on
circular-arc graphs. SIAM Journal of Computing, 24:411–439, 1995.

[LS09]

Min Chih Lin and Jayme L. Szwarcfiter. Characterizations and recognition of circulararc graphs and subclasses: A survey. Discrete Mathematics, 309(18):5618–5635, 2009.

[McC03] Ross M. McConnell. Linear-time recognition of circular-arc graphs. Algorithmica, 37:93–
147, 2003.
[NS96]

Lata Narayanan and Sunil Shende. Characterizations of networks supporting shortestpath interval labeling schemes. 3rd Internat. Coll. on Structural Information and Communication Complexity (SIROCCO), pages 73–87, 1996.

[PU89]

David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables.
Journal of the ACM, 36(3):510–530, 1989.

[Rob76]

Fred S. Roberts. Discrete mathematical models, with applications to social, biological,
and environmental problems. Prentice-Hall, Englewood Cliffs, N.J., 1976.

[SK82]

Nicola Santoro and Ramez Khatib. Routing without routing tables. Technical Report
SCS-TR-6 School of Computer Science, Carleton University, Ottawa, 1982.

[SK85]

Nicola Santoro and Ramez Khatib. Labelling and implicit routing in networks. The
Computer Journal, 28(1):5–8, 1985.

[TL99]

Savio S.H. Tse and Francis C.M. Lau. On the space requirement of interval routing.
IEEE Transactions on Computers, 48:752–757, 1999.

[Tuc75]

Alan Tucker. Coloring a family of circular arcs. SIAM Journal on Applied Mathematics,
29(3):493–502, 1975.

[Tuc80]

Alan Tucker. An efficient test for circular-arc graphs. SIAM Journal of Computing,
9:1–25, 1980.

[vLT87]

Jan van Leeuwen and Richard B. Tan. Interval routing. The Computer Journal,
30(4):298–307, 1987.

17

