Bounded representations of interval and proper interval graphs

DOI10.1007/978-3-642-45030-3_50MaRDI QIDQ2872117zbMATH OpenOpenAlexWikidataFDO

Authors Martin Balko, Pavel Klavík, Yota Otachi

Publication date 14 January 2014

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

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

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Klavik et al. [arXiv:1207.6960] recently introduced a generalization of recognition called the bounded representation problem which we study for the classes of interval and proper interval graphs. The input gives a graph G and in addition for each vertex v two intervals L_v and R_v called bounds. We ask whether there exists a bounded representation in which each interval I_v has its left endpoint in L_v and its right endpoint in R_v. We show that the problem can be solved in linear time for interval graphs and in quadratic time for proper interval graphs. Robert's Theorem states that the classes of proper interval graphs and unit interval graphs are equal. Surprisingly the bounded representation problem is polynomially solvable for proper interval graphs and NP-complete for unit interval graphs [Klav'{i}k et al., arxiv:1207.6960]. So unless P = NP, the proper and unit interval representations behave very differently. The bounded representation problem belongs to a wider class of restricted representation problems. These problems are generalizations of the well-understood recognition problem, and they ask whether there exists a representation of G satisfying some additional constraints. The bounded representation problems generalize many of these problems.

Recommendations

• The Roberts characterization of proper and unit interval graphs
• A new representation of proper interval graphs with an application to clique-width

Cited in

(15)

• On the classes of interval graphs of limited nesting and count of lengths
• Extending partial representations of subclasses of chordal graphs
• On the thinness and proper thinness of a graph
• The Roberts characterization of proper and unit interval graphs
• A matrix characterization of interval and proper interval graphs
• A new representation of proper interval graphs with an application to clique-width
• Minimal obstructions for partial representations of interval graphs
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. II: Algorithms
• On Restrictions of Balanced 2-Interval Graphs
• Interval Graphs with Containment Restrictions
• scientific article; zbMATH DE number 701114 (Why is no real title available?)
• On the classes of interval graphs of limited nesting and count of lengths
• Interval graph representation with given interval and intersection lengths
• Minimal obstructions for partial representations of interval graphs

This page was built for publication: Bounded representations of interval and proper interval graphs

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