Minimal obstructions for partial representations of interval graphs
Summary: \textit{Interval graphs} are intersection graphs of closed intervals. A generalization of recognition called \textit{partial representation extension} was introduced recently. The input gives an interval graph with a \textit{partial representation} specifying some pre-drawn intervals. We ask whether the remaining intervals can be added to create an \textit{extending representation}. Two linear-time algorithms are known for solving this problem. In this paper, we characterize the \textit{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.
- Minimal obstructions for partial representations of interval graphs
- On representing an interval graph using the minimum number of interval lengths
- On interval representations of graphs
- On computing graph minor obstruction sets
- Bounded representations of interval and proper interval graphs
- Interval minors of complete bipartite graphs
- A characterization of uniquely representable interval graphs
- A Kuratowski-type theorem for planarity of partially embedded graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Bounded representations of interval and proper 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
- Completing orientations of partially oriented graphs
- Contact representations of planar graphs: extending a partial representation is hard
- Counting Interval Graphs
- Extending partial representations of circle graphs
- Extending partial representations of function graphs and permutation graphs
- Extending partial representations of subclasses of chordal graphs
- Extending partial representations of trapezoid 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
- Interval graphs and interval orders
- Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
- Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
- Mapping the genome
- Minimal obstructions for partial representations of interval graphs
- ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
- On the classes of interval graphs of limited nesting and count of lengths
- Realizing Interval Graphs with Size and Distance Constraints
- 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
- The LBFS structure and recognition of interval graphs
- The node-deletion problem for hereditary properties is NP-complete
- The obstructions of a minor-closed set of graphs defined by a context-free grammar
- Minimal obstructions to ( , k )-polarity in cographs
- Sparse obstructions for minor-covering parameters
- Minimal obstructions for partial representations of interval graphs
- Obstructions for local tournament orientation completions with cut-vertices
- Structural parameterizations of simultaneous planarity
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 Q668026)
