Simultaneous Interval Graphs

In a recent paper, we introduced the simultaneous representation problem (defined for any graph class

$\cal C$

) and studied the problem for chordal, comparability and permutation graphs. For interval graphs, the problem is defined as follows. Two interval graphs

G

1

and

G

2

, sharing some vertices

I

(and the corresponding induced edges), are said to be “simultaneous interval graphs” if there exist interval representations

R

1

and

R

2

of

G

1

and

G

2

, such that any vertex of

I

is mapped to the same interval in both

R

1

and

R

2

. Equivalently,

G

1

and

G

2

are simultaneous interval graphs if there exist edges

E

′ between

G

1

 − 

I

and

G

2

 − 

I

such that

G

1

 ∪ 

G

2

 ∪ 

E

′ is an interval graph.

Simultaneous representation problems are related to simultaneous planar embeddings, and have applications in any situation where it is desirable to consistently represent two related graphs, for example: interval graphs capturing overlaps of DNA fragments of two similar organisms; or graphs connected in time, where one is an updated version of the other.

In this paper we give an

O

(

n

2

log

n

) time algorithm for recognizing simultaneous interval graphs, where

n

 = |

G

1

 ∪ 

G

2

|. This result complements the polynomial time algorithms for recognizing probe interval graphs and provides an efficient algorithm for the interval graph sandwich problem for the special case where the set of optional edges induce a complete bipartite graph.