Minimal obstructions for partial representations of interval graphs

zbMath1409.05140MaRDI QIDQ668026

Pavel Klavík, Maria Saumell

Publication date: 5 March 2019

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p55

zbMATH Keywords

interval graphsPQ-treescertifying algorithmpartial representation extension

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Extending partial representations of proper and unit interval graphs
• The partial visibility representation extension problem
• Interval graphs and interval orders
• A characterization of uniquely representable interval graphs
• The node-deletion problem for hereditary properties is NP-complete
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Extending partial representations of trapezoid graphs
• A Kuratowski-type theorem for planarity of partially embedded graphs
• Extending partial representations of subclasses of chordal graphs
• Incidence matrices and interval graphs
• Extending partial representations of interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• Extending Partial Representations of Circle Graphs
• Bounded Representations of Interval and Proper Interval Graphs
• Extending Partial Representations of Function Graphs and Permutation Graphs
• Minimal Obstructions for Partial Representations of Interval Graphs
• Contact Representations of Planar Graphs: Extending a Partial Representation is Hard
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms
• The LBFS Structure and Recognition of Interval Graphs
• Representation of a finite graph by a set of intervals on the real line
• Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
• Counting Interval Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Realizing Interval Graphs with Size and Distance Constraints
• On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
• Completing orientations of partially oriented graphs
• Testing Planarity of Partially Embedded Graphs
• Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
• Mapping the genome
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING