Linear-time Algorithm for Partial Representation Extension of Interval Graphs.
Pavel Klavík, Jan Kratochvı́l, Yota Otachi, Toshiki Saitoh, Tomáš Vyskočil · arXiv (Cornell University) · 2013
Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition, asks for an input graph $G$ whether it can be represented by closed intervals, i.e., whether G is an interval graph. There are several linear-time algorithms known for recognizing interval graphs. In this paper, we study a generalization of recognition, called partial representation extension. Input of this problem consists of a graph G with a partial representation R' fixing positions of some intervals. The problem asks whether it is possible to place the remaining interval and create an interval representation R of the entire graph G extending R'. We give a linear-time algorithm based on PQ-trees which solves this problem.