Geodesic
The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs
Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 283-315.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 G1 and G2 be graphs from such a class C, sharing some vertices I and the corresponding induced edges. Then G1 and G2 are said to be simultaneous C graphs if there exist representations R1 and R2 of G1 and G2 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 G1 and G2, sharing vertices I and the corresponding induced edges, do there exist edges E′ ⊆ V(G1)−I ×V(G2)−I such that the graph G1 ∪G2 ∪E′ belongs to the graph class. This equivalence implies that the simultaneous representation problem is closely related to some well-studied 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 NP-hard for chordal graphs.
DOI : 10.7155/jgaa.00259
Keywords: simultaneous graphs, sandwich graphs, chordal graphs, comparability graphs, permutation graphs 
@article{JGAA_2012_16_2_a6,
     author = {Krishnam Raju Jampani and Anna Lubiw},
     title = {The {Simultaneous} {Representation} {Problem} for {Chordal,} {Comparability} and {Permutation} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {283--315},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2012},
     doi = {10.7155/jgaa.00259},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00259/}
}
TY  - JOUR
AU  - Krishnam Raju Jampani
AU  - Anna Lubiw
TI  - The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 283
EP  - 315
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00259/
DO  - 10.7155/jgaa.00259
LA  - en
ID  - JGAA_2012_16_2_a6
ER  - 
%0 Journal Article
%A Krishnam Raju Jampani
%A Anna Lubiw
%T The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs
%J Journal of Graph Algorithms and Applications
%D 2012
%P 283-315
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00259/
%R 10.7155/jgaa.00259
%G en
%F JGAA_2012_16_2_a6
Krishnam Raju Jampani; Anna Lubiw. The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs. Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 283-315. doi : 10.7155/jgaa.00259. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00259/

Cité par Sources :