Extending Partial Representations of Circle Graphs

Abstrakt

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.

Klíčová slova

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