Extending Partial Representations of Graphs
Presented by Mr. Pavel KLAVIK
Type: Oral presentation
Track: Graph Theory
The partial representation extension problem is a recently introduced generalization of the recognition problem. In this problem, aside a graph a part of a representation is given. The question is whether this partial representations can be extended to a representation of the entire graph. For example in the case of interval graphs, a part of intervals is pre-drawn and the question is whether the remaining intervals can be added. The partial representation extension problem clearly generalizes the recognition problem; an input of the recognition problem corresponds to an input of the partial representation problem in which the partial representation is empty. Therefore, we study complexity of this problem for classes for which recognition is solvable in polynomial time. It is surprising that in most of these cases, the partial representation extension problem is also polynomially solvable. In this talk, we review results of last few years concerning these problems, together with their connections to other types of problems dealing with restricted representations. We discuss interval graphs, proper and unit interval graphs, chordal graphs, permutation and function graphs, circle graphs and other graph classes.