Publication at Faculty of Mathematics and Physics |
2012
Abstract
Chordal graphs are intersection graphs of subtrees in a tree. We investigate complexity of the partial representation extension problem for chordal graphs.
A partial representation specifies a tree T' and some pre-drawn subtrees. It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (keeps the pre-drawn subtrees unchanged).
We consider four modifications of T' and get vastly different problems. In some cases, the problem is interesting even if just T' is given and no subtree is pre-drawn.
Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization.