Minimal Obstructions for Partial Representations of Interval Graphs

0500501 - ÚI 2019 RIV US eng J - Journal Article
Klavík, P. - Saumell, Maria
Minimal Obstructions for Partial Representations of Interval Graphs.
Electronic Journal of Combinatorics. Roč. 25, č. 4 (2018), č. článku P4.55. ISSN 1077-8926. E-ISSN 1077-8926
R&D Projects: GA ČR GJ16-07822Y; GA ČR GBP202/12/G061
Grant - others:GA MŠk(CZ) LO1506; GA MŠk(CZ) EE2.3.30.0038
Institutional support: RVO:67985807
Keywords : Interval graphs * Partial representation extension * PQ-trees * Certifying algorithm
OECD category: Pure mathematics
Impact factor: 0.762, year: 2018
https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p55

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.
Permanent Link: http://hdl.handle.net/11104/0292562