Minimal obstructions for partial representations of interval graphs

DOI10.1007/978-3-319-13075-0_32MaRDI QIDQ2942647zbMATH OpenOpenAlexFDO

Authors Pavel Klavík, Maria Saumell

Publication date 11 September 2015

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

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

zbMATH Keywords

extending representationminimal obstructionspartial representation extension

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently. The input gives an interval graph with a partial representation specifying some pre-drawn intervals. We ask whether the remaining intervals can be added to create an extending representation. Two linear-time algorithms are known for solving this problem. In this paper, we characterize the minimal obstructions which make partial representations non-extendible. This generalizes Lekkerkerker and Boland's characterization of the minimal forbidden induced subgraphs of interval graphs. Each minimal obstruction consists of a forbidden induced subgraph together with at most four pre-drawn intervals. A Helly-type result follows: A partial representation is extendible if and only if every quadruple of pre-drawn intervals is extendible by itself. Our characterization leads to a linear-time certifying algorithm for partial representation extension.

Recommendations

• Minimal obstructions for partial representations of interval graphs

Cites work

• A Kuratowski-type theorem for planarity of partially embedded graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Bounded representations of interval and proper interval graphs
• Chronological orderings of interval graphs
• Contact representations of planar graphs: extending a partial representation is hard
• Extending partial representations of circle graphs
• Extending partial representations of function graphs and permutation graphs
• Extending Partial Representations of Subclasses of Chordal Graphs
• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Representation of a finite graph by a set of intervals on the real line
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Testing planarity of partially embedded graphs

Cited in

(6)

• The obstructions of a minor-closed set of graphs defined by a context-free grammar
• On the classes of interval graphs of limited nesting and count of lengths
• Minimal obstructions to ( , k )-polarity in cographs
• Sparse obstructions for minor-covering parameters
• Extending partial representations of subclasses of chordal graphs
• Minimal obstructions for partial representations of interval graphs

This page was built for publication: Minimal obstructions for partial representations of interval graphs

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