A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs.
In this paper we study the problem of recognizing and representing dynamically changing proper interval graphs. The input to the problem consists of a series of modifications to be performed on a graph, where a modification can be a deletion or an addition of a vertex or an edge. The objective is to maintain a representation of the graph as long as it remains a proper interval graph, and to detect when it ceases to be so. The representation should enable one to efficiently construct a realization of the graph by an inclusion-free family of intervals. This problem has important applications in physical mapping of DNA.We give a near-optimal fully dynamic algorithm for this problem. It operates in O(log n) worst-case time per edge insertion or deletion. We prove a close lower bound of $\Omega(\log n/(\log\log n+\log b))$ amortized time per operation in the cell probe model with word-size b. We also construct optimal incremental and decremental algorithms for the problem, which handle each edge operation in O(1) time. As a byproduct of our algorithm, we solve in O(log n) worst-case time the problem of maintaining connectivity in a dynamically changing proper interval graph.
Introduction
A graph G is called an interval graph if its vertices can be assigned to intervals on the
real line so that two vertices are adjacent in G iff their intervals intersect. The set of
intervals assigned to the vertices of G is called a realization of G. If the set of intervals
can be chosen to be inclusion-free, then G is called a proper interval graph. Proper
interval graphs have been studied extensively in the literature (cf. [7, 13]), and several
linear time algorithms are known for their recognition and realization [2, 3].
This paper deals with the problem of recognizing and representing dynamically
changing proper interval graphs. The input is a series of operations to be performed
on a graph, where an operation is any of the following: Adding a vertex (along with
the edges incident to it), deleting a vertex (and the edges incident to it), adding an
edge and deleting an edge. The objective is to maintain a representation of the dynamic
graph as long as it is a proper interval graph, and to detect when it ceases to be so.
The representation should enable one to efficiently construct a realization of the graph.
In the incremental version of the problem, only addition operations are permitted, i.e.,
the operations include only the addition of a vertex and the addition of an edge. In the
decremental version of the problem only deletion operations are allowed.
The motivation for this problem comes from its application to physical mapping of
DNA [1]. Physical mapping is the process of reconstructing the relative position of DNA
fragments, called clones, along the target DNA molecule, prior to their sequencing,
based on information about their pairwise overlaps. In some biological frameworks
the set of clones is virtually inclusion-free - for example when all clones have a similar
length (this is the case for instance for cosmid clones). In this case, the physical mapping
problem can be modeled using proper interval graphs as follows. A graph G is built
according to the biological data. Each clone is represented by a vertex and two vertices
are adjacent iff their corresponding clones overlap. The physical mapping problem then
translates to the problem of finding a realization of G, or determining that none exists.
Had the overlap information been accurate, the two problems would have been
equivalent. However, some biological techniques may occasionally lead to an incorrect
conclusion about whether two clones intersect, and additional experiments may change
the status of an intersection between two clones. The resulting changes to the corresponding
graph are the deletion of an edge, or the addition of an edge. The set of clones
is also subject to changes, such as adding new clones or deleting 'bad' clones (such as
chimerics [14]). These translate into addition or deletion of vertices in the corresponding
graph. Therefore, we would like to be able to dynamically change our graph, so as
to reflect the changes in the biological data, as long as they allow us to construct a map,
i.e., as long as the graph remains a proper interval graph.
Several authors have studied the problem of dynamically recognizing and representing
certain graph families. Hsu [10] has given an O(m+ n log n)-time incremental
algorithm for recognizing interval graphs. (Throughout, we denote the number of vertices
in the graph by n and the number of edges in it by m.) Deng, Hell and Huang [3]
have given a linear-time incremental algorithm for recognizing and representing connected
proper interval graphs This algorithm requires that the graph will remain connected
throughout the modifications. In both algorithms [10, 3] only vertex increments
are handled. Recently, Ibarra [11] found a fully dynamic algorithm for recognizing
chordal graphs, which handles each edge operation in O(n) time, or alternatively, an
edge deletion in O(n log n) time and an edge insertion in O(n= log n) time.
Our results are as follows: For the general problem of recognizing and representing
proper interval graphs we give a fully dynamic algorithm which handles each operation
in time O(d log n), where d denotes the number of edges involved in the
operation. Thus, in case a vertex is added or deleted, d equals its degree, and in case
an edge is added or deleted, d = 1. Our algorithm builds on the representation of
proper interval graphs given in [3]. We also prove a lower bound for this problem of
\Omega (log n=(log log n+ log b)) amortized time per edge operation in the cell probe model
of computation with word-size b [16]. It follows that our algorithm is nearly optimal
(up to a factor of O(log log n)).
For the incremental and the decremental versions of the problem we give optimal
algorithms (up to a constant factor) which handle each operation in time O(d). For the
incremental problem this generalizes the result of [3] to arbitrary instances.
As a part of our general algorithm we give a fully dynamic procedure for maintaining
connectivity in proper interval graphs. The procedure receives as input a sequence of
operations each of which is a vertex addition or deletion, an edge addition or deletion,
or a query whether two vertices are in the same connected component. It is assumed
that the graph remains proper interval throughout the modifications, since otherwise
our main algorithm detects that the graph is no longer a proper interval graph and halts.
We show how to implement this procedure in O(log n) time per operation. In compar-
ison, the best known algorithms for maintaining connectivity in general graphs require
O(log 2 n) amortized time per operation [9], or O(
n) worst-case (deterministic) time
per operation [4]. We also show that the lower bound of Fredman and Henzinger [5] of
\Omega (log n=(log log n+log b)) amortized time per operation (in the cell probe model with
word-size b) for maintaining connectivity in general graphs, applies to the problem of
maintaining connectivity in proper interval graphs.
The paper is organized as follows: In section 2 we give the basic background and
describe our representation of proper interval graphs and the realization it defines. In
sections 3 and 4 we present the incremental algorithm. In section 5 we extend the incremental
algorithm to a fully dynamic algorithm for proper interval graph recognition
and representation. We also derive an optimal decremental algorithm. In section 6 we
give a fully dynamic algorithm for maintaining connectivity in proper interval graphs.
Finally, in section 7 we prove a lower bound on the amortized time per operation of a
fully dynamic algorithm for recognizing proper interval graphs. For lack of space, some
of the proofs and some of the algorithmic details are omitted.
Preliminaries
E) be a graph. We denote its set V of vertices also by V (G) and its set E
of edges also by E(G). For a vertex
and N [v] := N (v) [ fvg. Let R be an equivalence relation on V defined by uRv iff
Each equivalence class of R is called a block of G. Note that every block
of G is a complete subgraph of G. The size of a block is the number of vertices in it.
Two blocks A and B are neighbors in G if some (and hence all) vertices a 2 A; b 2 B,
are adjacent in G. A straight enumeration of G is a linear ordering \Phi of the blocks in
G, such that for every block, the block and its neighboring blocks are consecutive in \Phi.
l be an ordering of the blocks of G. For any 1 -
we say that is ordered to the left of B j , and that B j is ordered to the right of B i .
A chordless cycle is an induced cycle of length greater than 3. A claw is an induced
K 1;3 . A graph is claw-free if it does not contain an induced claw. For basic definitions
in graph theory see, e.g., [7].
The following are some useful facts about interval and proper interval graphs.
Theorem 1. ([12]) An interval graph contains no chordless cycle.
Theorem 2. ([15]) A graph is a proper interval graph iff it is interval and claw-free.
Theorem 3. ([3]) A graph is a proper interval graph iff it has a straight enumeration.
Lemma 1 ("The umbrella property"). Let \Phi be a straight enumeration of a connected
proper interval graph G. If A; B and C are blocks of G, such that A
and A is adjacent to C, then B is adjacent to A and to C (see figure 1).
Fig. 1. The umbrella property
Let G be a connected proper interval graph and let \Phi be a straight enumeration
of G. It is shown in [3] that a connected proper interval graph has a unique straight
enumeration up to its full reversal. Define the out-degree of a block B w.r.t. \Phi, denoted
by o(B), as the number of neighbors of B which are ordered to its right in \Phi.
We shall use the following representation: For each connected component of the
dynamic graph we maintain a straight enumeration (in fact, for technical reasons we
shall maintain both the enumeration and its reversal). The details of the data structure
containing this information will be described below.
This information implicitly defines a realization of the dynamic graph (cf. [3]) as
follows: Assign to each vertex in block B i the interval
]. The out-degrees
and hence the realization of the graph can be computed from our data structure
in time O(n).
3 An Incremental Algorithm for Vertex Addition
In the following two sections we describe an optimal incremental algorithm for recognizing
and representing proper interval graphs. The algorithm receives as input a
series of addition operations to be performed on a graph. Upon each operation the algorithm
updates its representation of the graph and halts if the current graph is no longer
a proper interval graph. The algorithm handles each operation in time O(d), where d
denotes the number of edges involved in the operation. It is assumed that initially the
graph is empty, or alternatively, that the representation of the initial graph is known.
A contig of a connected proper interval graph G is a straight enumeration of G.
The first and the last blocks of a contig are called end-blocks. The rest of the blocks are
called inner-blocks.
As mentioned above, each component of the dynamic graph has exactly two contigs
(which are full reversals of each other) and both are maintained by the algorithm. Each
operation involves updating the representation. (In the sequel we concentrate on describing
only one of the two contigs for each component. The second contig is updated
in a similar way.)
3.1 The Data Structure
The following data is kept and updated by the algorithm:
1. For each vertex we keep the name of the block to which it belongs.
2. For each block we keep the following:
(a) An end pointer which is null if the block is not an end-block of its contig, and
otherwise points to the other end-block of that contig.
(b) The size of the block.
(c) Left and right near pointers, pointing to nearest neighbor blocks on the left and
on the right respectively.
(d) Left and right far pointers, pointing to farthest neighbor blocks on the left and
on the right respectively.
(e) Left and right self pointers, pointing to the block.
(f) A counter.
In the following we shall omit details about the obvious updates to the name of the
block of a vertex and to the size of a block.
During the execution of the algorithm we may need to update many far pointers
pointing to a certain block, so that they point to another block. In order to be able to
do that in O(1) time we use the technique of nested pointers: We make the far pointers
point to a location whose content is the address of the block to which the far pointers
should point. The role of this special location will be served by our self-pointers. The
value of the left and right self-pointers of B is always the address of B. When we say
that a certain left (right) far pointer points to B, we mean that it points to a left (right)
self-pointer of B. Let A and B be blocks. In order to change all left (right) far pointers
pointing to A so that they point to B, we require that no left (right) far pointer points
to B. If this is the case, we simply exchange the left (right) self-pointer of A with the
left (right) self-pointer of B. This means that: (1) The previous left (right) self-pointer
of A is made to point to B, and the algorithm records it as the new left (right) self-
pointer of B; (2) The previous left (right) self-pointer of B is made to point to A, and
the algorithm records it as the new left (right) self-pointer of A.
We shall use the following notation: For a block B we denote its address in the
memory by &B. When we set a far pointer to point to a left or to a right self-pointer of
B we will abbreviate and set it to &B. We denote the left and right near pointers of B by
l (B) and N r (B) respectively. We denote the left and right far pointers of B by F l (B)
and F r (B) respectively. We denote its end pointer by E(B). In the sequel we often refer
to blocks by their addresses. For example, if A and B are blocks, and N r
sometimes refer to B by N r (A). When it is clear from the context, we also use a name
of a block to denote any vertex in that block. Given a contig \Phi we denote its reversal by
\Phi R . In general when performing an operation, we denote the graph before the operation
is carried out by G, and the graph after the operation is carried out by G 0 .
3.2 The Impact of a New Vertex
In the following we describe the changes made to the representation of the graph in case
G 0 is formed from G by the addition of a new vertex v of degree d. We also give some
necessary and some sufficient conditions for deciding whether G 0 is proper interval.
Let B be a block of G. We say that v is adjacent to B if v is adjacent to some vertex
in B. We say that v is fully adjacent to B if v is adjacent to every vertex in B. We say
that v is partially adjacent to B if v is adjacent to B but not fully adjacent to B.
The following lemmas characterize, assuming that G 0 is proper interval, the adjacencies
of the new vertex.
Lemma 2. If G 0 is a proper interval graph then v can have neighbors in at most two
connected components of G.
Lemma 3. [3] Let C be a connected component of G containing neighbors of v. Let
be a contig of C . Assume that G 0 is proper interval and let 1 - a !
k. Then the following properties are satisfied:
1. If v is adjacent to B a and to B c , then v is fully adjacent to B b .
2. If v is adjacent to B b and not fully adjacent to B a and to B c , then B a is not adjacent
to B c .
3. If is adjacent to B b , then v is fully adjacent to B a or to
One can view a contig \Phi of a connected proper interval graph C as a weak linear
on the vertices of C, where x ! \Phi y iff the block containing x is ordered in
\Phi to the left of the block containing y. We say that \Phi 0 is a refinement of \Phi if for every
a contig can be reversed, we also allow
complete reversal of \Phi).
Lemma 4. If G is a connected induced subgraph of a proper interval graph G 0 , \Phi is a
contig of G and \Phi 0 is a straight enumeration of G 0 , then \Phi 0 is a refinement of \Phi.
Note, that whenever v is partially adjacent to a block B in G, then the addition of v
will cause B to split into two blocks of G 0 , namely B nN (v) and B " N (v). Otherwise,
if B is a block of G to which v is either fully adjacent or not adjacent, then B is also a
block of G 0 .
Corollary 1. If B is a block of G to which v is partially adjacent, then B n N (v) and
occur consecutively in a straight enumeration of G 0 .
Lemma 5. Let C be a connected component of G containing neighbors of v. Let the
set of blocks in C which are adjacent to v be fB g. Assume that in a contig of
. If G 0 is proper interval then the following properties are satisfied:
are consecutive in C.
2. If k - 3 then v is fully adjacent to B
3. If v is adjacent to a single block B 1 in C, then B 1 is an end-block.
4. If v is adjacent to more than one block in C and has neighbors in another compo-
nent, then B 1 is adjacent to B k , and one of B 1 or B k is an end-block to which v is
fully adjacent, while the other is an inner-block.
Proof. Claims 1 and 2 follow directly from part 1 of Lemma 3. Claim 3 follows from
part 3 of Lemma 3. To prove the last part of the lemma let us denote the other component
containing neighbors of v by D. Examine the induced connected subgraph H of G
whose set of vertices is V (D). H is proper interval as an
induced subgraph of G. It is composed of three types of blocks: Blocks whose vertices
are from V (C), which we will call henceforth C-blocks; blocks whose vertices are from
V (D), which we will call henceforth D-blocks; and fvg which is a block of H since
fvg is not connected. All blocks of C remain intact in H, except B 1 and B k which
might split into B j n N (v) and
Surely in a contig of H, C-blocks must be ordered completely before or completely
after D-blocks. Let \Phi denote a contig of H , in which C-blocks are ordered before D-
blocks. Let X denote the rightmost C-block in \Phi. By the umbrella property,
and moreover, X is adjacent to v. By Lemma 4, \Phi is a refinement of a contig of C.
Hence, precisely,
Therefore, one of B 1 or B k is an end-block.
W.l.o.g. . Suppose to the contrary that v is not fully adjacent to B k . Then
by Lemma 4 we have contradicting the
umbrella property. B 1 must be adjacent to B k , or else G 0 contains a claw consisting of
and a vertex from V (D)"N (v). It remains to show that B 1 is an inner-block.
Suppose it is an end block. Since B 1 and B k are adjacent, C contains a single block
contradiction. Thus, claim 4 is proved.
3.3 The Algorithm
In our algorithm we rely on the incremental algorithm of Deng, Hell and Huang [3],
which we call henceforth the DHH algorithm. This algorithm handles the insertion of a
new vertex into a graph in O(d) time, provided that all its neighbors are in the same connected
component, changing the straight enumeration of this component appropriately.
We refer the reader to [3] for more details.
We perform the following upon a request for adding a new vertex v. For each neighbor
u of v we add one to the count of the block containing u. We call a block full if its
counter equals its size, empty if its counter equals zero, and partial otherwise. In order
to find a set of consecutive blocks which contain neighbors of v, we pick arbitrarily a
neighbor of v and march down the enumeration of blocks to the left using the left near
neighbor pointers. We continue till we hit an empty block or till we reach the end of the
contig. We do the same to the right and this way we discover a maximal sequence of
nonempty blocks in that component which contain neighbors of v. We call this maximal
sequence a segment. Only the two extreme blocks of the segment are allowed to be
partial or else we fail (by Lemma 5(2)).
If the segment we found contains all neighbors of v then we can use the DHH
algorithm in order to insert v into G, updating our internal data structure accordingly.
Otherwise, by Lemmas 2 and 5(1) there could be only one more segment which contains
neighbors of v. In that case, exactly one extreme block in each segment is an end-block
to which v is fully adjacent (if the segment contains more than one block), and the two
extreme blocks in each segment are adjacent, or else we fail (by Lemma 5(3,4)).
We proceed as above to find a second segment containing neighbors of v. We can
make sure that the two segments are from two different contigs by checking that their
end-blocks do not point to each other. We also check that conditions 3 and 4 in Lemma 5
are satisfied. If the two segments do not cover all neighbors of v, we fail.
If v is adjacent to vertices in two distinct components C and D, then we should
merge their contigs. Let R be the two contigs of C. Let
l ; \Psi R be the two contigs of D. The way the merge is performed
depends on the blocks to which v is adjacent. If v is adjacent to B k and to B 0
by the umbrella property the two new contigs (up to refinements described below) are
. In the following we describe the necessary
changes to our data structure in case these are the new contigs. The three other cases
are handled similarly.
- Block enumeration: We merge the two enumerations of blocks and put a new block
fvg in-between the two contigs. Let the leftmost block adjacent to v in the new
ordering and let the rightmost block adjacent to v be B 0
. If
is partial we split it into two blocks -
in this order. If B 0
j is partial we split it into two blocks
(v) in this order.
- End pointers: We set E(B 1
l We then nullify the
end pointers of B k and B 0
1 .
Near pointers: We update N l
and N l (B 0
In case B i was split we update N r ( -
are made in case B 0
was split to the near pointers of B 0
j+1 .
- Far pointers: If B i was split we set F l ( -
the left self-pointer of B i with the left self-pointer of -
was split
we set F r ( -
1 and exchange the right self-pointer of
j with the right self-pointer of -
j . In addition, we set all right far pointers of
and all left far pointers of B 0
j to &fvg (in O(d)
time). Finally, we set F l
.
4 An Incremental Algorithm for Edge Addition
In this section we show how to handle the addition of a new edge (u; v) in O(1) time.
We characterize the cases for which G proper interval and show how
to efficiently detect them, and how to update our representation of the graph.
Lemma 6. If u and v are in distinct components in G, then G 0 is proper interval iff u
and v were in end-blocks of their respective contigs.
Proof. To prove the 'only if' part let us examine the graph fug.
H is proper interval as an induced subgraph of G. If G 0 is proper interval, then by
Lemma must be in an end-block of its contig, since u is not adjacent to any other
vertex in the component containing v. The same argument applies to u.
To prove the 'if' part we give a straight enumeration of the new connected component
containing u and v in G 0 . Denote by C and D the components containing u
and v respectively. Let be a contig of C , such that
l be a contig of D, such that
l is a straight enumeration of the new component.
We can check in O(1) time if u and v are in end-blocks of distinct contigs. If this
is the case, we update our data structure according to the straight enumeration given in
the proof of Lemma 6 in O(1) time.
It remains to handle the case where u and v were in the same connected component
C in G. If N then by the umbrella property it follows that C contains only
three blocks which are merged into a single block in G 0 . In this case G 0 is proper interval
and updates to the internal data structure are trivial. The following lemma analyses the
case where N (u) 6= N (v).
Lemma 7. Let be a contig of C , such that
k. Assume that N (u) 6= N (v). Then G 0 is proper interval iff
G.
Proof. To prove the 'only if' part assume that G 0 is proper interval. Since B i and B j
are not adjacent, F r (B i . Suppose to the contrary that
. If in addition F l (B
is a strict containment). As v and z are in distinct blocks, there exists a vertex b 2 N [v]n
N [z]. But then, v; b; z; u induce a claw in G 0 , a contradiction. Hence, F l (B
and so F r (B are in
distinct blocks, either (u; y) 62 E(G) or there is a vertex a 2 N [u] n N [x] (or both).
In the first case, v; u; x; y and the vertices of the shortest path from y to v induce a
chordless cycle in G 0 . In the second case u; a; x; v induce a claw in G 0 . Hence, in both
cases we arrive at a contradiction. The proof that F l (B
To prove the 'if' part we shall provide a straight enumeration of C [ fu; vg. If
we move v from B j to contained only v, F l (B
move u from B i to B i+1 . If u
was not moved and B i oe fug, we split B i into B i n fug; fug in this order. If v was not
moved and B j oe fvg, we split B j into fvg; B j n fvg in this order. It is easy to see that
the result is a straight enumeration of C [ fu; vg.
We can check in O(1) time if the condition in Lemma 7 holds. If this is the case,
we change our data structure so as to reflect the new straight enumeration given in the
proof of Lemma 7. This can be done in O(1) time, in a similar fashion to the update
technique described in Section 3.3. The details are omitted here. The following theorem
summarizes the results of Sections 3 and 4.
Theorem 4. The incremental proper interval graph representation problem is solvable
in O(1) time per added edge.
5 The Fully Dynamic Algorithm
In this section we give a fully dynamic algorithm for recognizing and representing
proper interval graphs. The algorithm performs each operation in O(d log n) time,
where d denotes the number of edges involved in the operation. It supports four types
of operations: Adding a vertex, adding an edge, deleting a vertex and deleting an edge.
It is based on the same ideas used in the incremental algorithm. The main difficulty in
extending the incremental algorithm to handle all types of operations, is updating the
end pointers of blocks when deletions are allowed. To bypass this problem we do not
keep end pointers at all. Instead, we maintain the connected components of G, and use
this information in our algorithm. In the next section we show how to maintain the connected
components of G in O(log n) time per operation. We describe below how each
operation is handled by the algorithm.
5.1 The Addition of a Vertex or an Edge
These operations are handled in essentially the same way as done by the incremental
algorithm. However, in order to check if the end-blocks of two segments are in distinct
components, we query our data structure of connected components (in O(log n) time).
Similarly, in order to check if the endpoints of an added edge are in distinct components,
we check if their corresponding blocks are in distinct components (in O(log n) time).
5.2 The Deletion of a Vertex
We show next how to update the contigs of G after deleting a vertex v of degree d. Note
that G 0 is proper interval as an induced subgraph of G. Denote by X the block containing
v. If X oe fvg, then the only change needed is to delete v. We hence concentrate on
the case that fvg. We can find in O(d) time the segment of blocks which includes
X and all its neighbors. Let the contig containing X be and let the
blocks of the segment be
We make the following updates:
l, we check whether B i can be merged with B i\Gamma1 .
If F l (B them by
moving all vertices from B i to B i\Gamma1 (in O(d) time) and deleting B i . If l
we act similarly w.r.t. B j and B j+1 . Finally, we delete B l . If
are non-adjacent, then by the umbrella property they are no longer in
the same connected component, and the contig should be split into two contigs, one
ending at B l\Gamma1 and one beginning at B l+1 .
were merged, we update N r (B
updates should be made w.r.t. in
case were merged. If the contig is split, we nullify N r (B l\Gamma1 ) and
l (B l+1 ). Otherwise, we update N r (B
were merged, we exchange the right self-pointer of B i
with the right self-pointer of B i\Gamma1 . Similar changes should be made w.r.t. B j and
. We also set all right far pointers previously pointing to B l , to &B
all left far pointers previously pointing to B l , to &B l+1 (in O(d) time).
Note that these updates take O(d) time and require no knowledge about the connected
components of G.
5.3 The Deletion of an Edge
Let (u; v) be an edge of G to be deleted. Let C denote the connected component of G
containing u and v, and let be a contig of C. If
into resulting in a straight enumeration of G 0 . Updates are
trivial in this case. If N then one can show that G is a proper
interval graph iff C was a clique, so again k = 1. We assume henceforth that k ? 1 and
W.l.o.g. were far neighbors of
each other, then we should split the contig into two contigs, one ending at B i and the
other beginning at B j . Otherwise, updates to the straight enumeration are derived from
the following lemma.
Lemma 8. Let be a contig of C, such that
k. Assume that N (u) 6= N (v). Then G 0 is proper interval iff F r (B i
and F l (B G.
Proof. Assume that G 0 is proper interval. We will show that F r (B i . The proof
that F l (B are adjacent in G, F r (B i
Suppose to the contrary that F r (B are in distinct
blocks, either there is a vertex a 2 N [v] n N [x] or there is a vertex b 2 N [x] n N [v] (or
both). In the first case, by the umbrella property (a; u) 2 E(G) and therefore u; x; v; a
induce a chordless cycle in G 0 . In the second case, x; b; u; v induce a claw in G 0 . Hence,
in both cases we arrive at a contradiction.
To prove the opposite direction we give a straight enumeration of C n f(u; v)g. If
we move u into B i\Gamma1 . If B i contained only u, F r (B j+1
. If u was not moved and
fug in this order. If v was not moved and
fvg in this order. The result is a contig of
v)g.
If the conditions of Lemma 8 are fulfilled, one has to update the data structure
according to its proof. These updates require no knowledge about the connected components
of G, and it can be shown that they take O(1) time. Hence, from Sections 5.2
and 5.3 we obtain the following result:
Theorem 5. The decremental proper interval graph representation problem is solvable
in O(1) time per removed edge.
6 Maintaining the Connected Components
In this section we describe a fully dynamic algorithm for maintaining connectivity in
a proper interval graph G in O(logn) time per operation. The algorithm receives as
input a series of operations to be performed on a graph, which can be any of the follow-
ing: Adding a vertex, adding an edge, deleting a vertex, deleting an edge or querying
if two blocks are in the same connected component. The algorithm depends on a data
structure which includes the blocks and the contigs of the graph. It hence interacts with
the proper interval graph representation algorithm. In response to an update request,
changes are made to the representation of the graph based on the structure of its connected
components prior to the update. Only then are the connected components of the
graph updated.
Let us denote by B(G) the block graph of G, that is, a graph in which each vertex
corresponds to a block of G and two vertices are adjacent iff their corresponding blocks
are adjacent in G. The algorithm maintains a spanning forest F of B(G). In order to
decide if two blocks are in the same connected component, the algorithm checks if they
belong to the same tree in F .
The key idea is to design F so that it can be efficiently updated upon a modification
in G. We define the edges of F as follows: For every two vertices u and v in B(G),
corresponding blocks are consecutive in a contig of G. Conse-
quently, each tree in F is a path representing a contig. The crucial observation about F
is that an addition or a deletion of a vertex or an edge in G induces O(1) modifications
to the vertices and edges of F . This can be seen by noting that each modification of G
induces O(1) updates to near pointers in our representation of G.
It remains to show how to implement a spanning forest in which trees may be cut
when an edge is deleted from F , linked when an edge is inserted to F , and which allows
to query for each vertex to which tree does it belong. All these operations are supported
by the ET-tree data structure of [8] in O(log n) time per operation.
We are now ready to state our main result:
Theorem 6. The fully dynamic proper interval graph representation problem is solvable
in O(d log n) time per modification involving d edges.
7 The Lower Bound
In this section we prove a lower bound
of\Omega (log n=(log log n log b)) amortized time
per edge operation for fully dynamic proper interval graph recognition in the cell probe
model of computation with word-size b [16].
Fredman and Saks [6] proved a lower bound
amortized
time per operation for the following parity prefix sum (PPS) problem: Given an
array of integers execute an arbitrary sequence
of Add(t) and Sum(t) operations, where an Add(t) increases A[t] by 1, and Sum(t)
returns (
2. Fredman and Henzinger [5] showed that the same lower
bound applies to the problem of maintaining connectivity in general graphs, by showing
a reduction from a modified PPS problem, called helpful parity prefix sum, for which
they proved the same lower bound. A slight change to their reduction yields the same
lower bound for the problem of maintaining connectivity in proper interval graphs, as
the graph built in the reduction is a union of two paths and therefore proper interval.
Using a similar construction we can prove the following result:
Theorem 7. Fully dynamic proper interval recognition
takes\Omega (log n=(log log n
log b)) amortized time per edge operation in the cell probe model with word-size b.

Acknowledgments

The first author gratefully acknowledges support from NSERC. The second author was
supported in part by a grant from the Ministry of Science, Israel. The third author was
supported by Eshkol scholarship from the Ministry of Science, Israel.



--R

Establishing the order of human chromosome-specific DNA fragments
Simple linear time recognition of unit interval graphs.
Recognition and representation of proper circular arc graphs.
SIAM Journal on Computing

Lower bounds for fully dynamic connectivity problems in graphs.
The cell probe complexity of dynamic data structures.
Algorithmic Graph Theory and Perfect Graphs.
Randomized dynamic graph algorithms with polylogarithmic time per operation.

A simple test for interval graphs.
Fully dynamic algorithms for chordal graphs.
Representation of a finite graph by a set of intervals on the real line.
Indifference graphs.
Recombinant DNA.
Eigenschaften der Nerven homologisch einfacher Familien in R n
Should tables be sorted.
--TR

--CTR
Ron Shamir , Roded Sharan, A fully dynamic algorithm for modular decomposition and recognition of cographs, Discrete Applied Mathematics, v.136 n.2-3, p.329-340, 15 February 2004
C. Crespelle , C. Paul, Fully dynamic recognition algorithm and certificate for directed cograph, Discrete Applied Mathematics, v.154 n.12, p.1722-1741, 15 July 2006
Derek G. Corneil, A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs, Discrete Applied Mathematics, v.138 n.3, p.371-379, 15 April 2004
Jrgen Bang-Jensen , Jing Huang , Louis Ibarra, Recognizing and representing proper interval graphs in parallel using merging and sorting, Discrete Applied Mathematics, v.155 n.4, p.442-456, February, 2007
proper interval graphs;lower bounds;graph algorithms;fully dynamic algorithms