Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00259
The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs
Vol. 16, no. 2, pp. 283315, 2012. Regular paper.
Abstract We introduce a notion of simultaneity for any class of graphs with an intersection representation (interval graphs, chordal graphs, etc.) and for comparability graphs, which are represented by transitive orientations.
Let G_{1} and G_{2} be graphs from such a class
C,
sharing some vertices I and the corresponding induced edges. Then
G_{1} and G_{2} are said to be simultaneous C
graphs if there exist representations R_{1} and R_{2} of
G_{1} and G_{2} that are the same
on the shared subgraph.
Simultaneous representation problems arise in any situation where two related graphs
should be represented consistently. A main instance is for temporal relationships, where an old graph and a new graph
share some common parts. Pairs of related graphs arise in many other situations. For example, two social networks that
share some members; two schedules that share some events, overlap graphs of DNA fragments of two similar organisms,
circuit graphs of two adjacent layers on a computer chip, etc.
For comparability graphs and any intersection graph class, we show that the simultaneous representation problem for the graph
class is equivalent to a graph augmentation problem: given graphs G_{1} and G_{2}, sharing vertices I and the corresponding
induced edges, do there exist edges E′ ⊆ V(G_{1})−I ×V(G_{2})−I such that the graph G_{1} ∪G_{2} ∪E′ belongs
to the graph class. This equivalence implies that the
simultaneous representation problem is closely related to some wellstudied classes in the literature, namely, sandwich graphs
and probe graphs.
We give efficient algorithms for solving the simultaneous representation problem for chordal graphs,
comparability graphs and permutation graphs. Further, our algorithms for comparability and permutation graphs solve a
more general version of the problem when there are multiple graphs, any two of which share the same common graph. This
version of the problem also generalizes probe graphs. Finally, we show that the general version of the problem is NPhard for chordal
graphs.

Submitted: November 2011.
Reviewed: February 2012.
Revised: March 2012.
Accepted: March 2012.
Final: March 2012.
Published: March 2012.
Communicated by
Stephen G. Kobourov

Journal Supporters
