Simultaneous interval graphs

DOI10.1007/978-3-642-17517-6_20MaRDI QIDQ3060734zbMATH OpenOpenAlexFDO

Authors K. R. Jampani, Anna Lubiw

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.3502

zbMATH Keywords

interval graphsPQ-treesprobe graphsgraph sandwich problemsimultaneous graphs

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: In a recent paper, we introduced the simultaneous representation problem (defined for any graph class 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 cup G_2 cup 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*logn) time algorithm for recognizing simultaneous interval graphs,where n = |G_1 cup 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.

Recommendations

• The simultaneous representation problem for chordal, comparability and permutation graphs
• The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs

Cited in

(15)

• Partial and simultaneous transitive orientations via modular decompositions
• Interval graph representation with given interval and intersection lengths
• Simple algorithms for partial and simultaneous rectangular duals with given contact orientations
• Simultaneous representation of proper and unit interval graphs
• Partial and constrained level planarity
• Simultaneous orthogonal planarity
• Simultaneous representation of proper and unit interval graphs
• Simultaneous visibility representations of plane st-graphs using L-shapes
• Simultaneous visibility representations of plane \(st\)-graphs using L-shapes
• scientific article; zbMATH DE number 2079753 (Why is no real title available?)
• Simultaneous contact representations of planar graphs
• The simultaneous representation problem for chordal, comparability and permutation graphs
• The simultaneous interval number: a new width parameter that measures the similarity to interval graphs
• Interval line graphs
• The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs

This page was built for publication: Simultaneous interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3060734)