Extending Partial Representations of Circle Graphs

Abstract

We give a polynomial-time algorithm for extending partial representations of circle graphs. Our result is based on a generalization of split decomposition which captures all representations of a given circle graph.

Keywords

• partial representations
• recognition
• circle graphs
• split decomposition
• all representations