Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Extending Partial Representations of Circle Graphs
verfasst von : Steven Chaplick, Radoslav Fulek, Pavel Klavík
Erschienen in: Graph Drawing
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The partial representation extension problem
is a recently introduced generalization of the recognition problem. A
circle graph
is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph
G
and a partial representation
$\mathcal{R'}$
giving some pre-drawn chords that represent an induced subgraph of
G
. The question is whether one can extend
$\mathcal{R'}$
to a representation
$\mathcal{R}$
of the entire
G
, i.e., whether one can draw the remaining chords into a partially pre-drawn representation.
Our main result is a polynomial-time algorithm for partial representation extension of circle graphs. To show this, we describe the structure of all representation a circle graph based on split decomposition. This can be of an independent interest.