Extending Partial Representations of Interval Graphs

• Published in: Algorithmica 2017-07, Vol.78 (3), p.945-967
• Main Authors: Klavík, Pavel, Kratochvíl, Jan, Otachi, Yota, Saitoh, Toshiki, Vyskočil, Tomáš
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Decision trees; Graphical representations; Graphs; Intervals; Mathematics of Computing; Recognition; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-016-0186-z

Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition , asks whether an input graph G 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, the oldest one is by Booth and Lueker (J Comput Syst Sci 13:335–379, 1976 ) based on PQ-trees. In this paper, we study a generalization of recognition, called partial representation extension . The input of this problem consists of a graph G with a partial representation R ′ fixing the 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 generalize the characterization of interval graphs by Fulkerson and Gross (Pac J Math 15:835–855, 1965 ) to extendible partial representations. Using it, we give a linear-time algorithm for partial representation extension based on a reordering problem of PQ-trees.