"RIV/00216208:11320/14:10288454!RIV15-MSM-11320___" . . "29461" . . "0302-9743" . "Klav\u00EDk, Pavel" . "RIV/00216208:11320/14:10288454" . . "Saumell, Maria" . . "Minimal Obstructions for Partial Representations of Interval Graphs"@en . "Minimal Obstructions for Partial Representations of Interval Graphs" . "Algorithms and Computation" . "978-3-319-13074-3" . "[EBA7E2ED7F1F]" . "13"^^ . "Minimal Obstructions for Partial Representations of Interval Graphs"@en . "Springer International Publishing" . "11320" . "http://link.springer.com/chapter/10.1007%2F978-3-319-13075-0_32" . . "minimal obstruction; partial representation; interval graph"@en . "10.1007/978-3-319-13075-0_32" . "2"^^ . "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. In this paper, we characterize the minimal obstructions which make a partial representation non-extendible. This generalizes Lekkerkerker and Boland's characterization of 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 the first polynomial-time certifying algorithm for partial representation extension of intersection graphs."@en . "Jeonju, South Korea" . . "1"^^ . . "Minimal Obstructions for Partial Representations of Interval Graphs" . . . . . "Switzerland" . "2014-12-15+01:00"^^ . "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. In this paper, we characterize the minimal obstructions which make a partial representation non-extendible. This generalizes Lekkerkerker and Boland's characterization of 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 the first polynomial-time certifying algorithm for partial representation extension of intersection graphs." . . "P(GBP202/12/G061), S" . . . . . .