Extending Partial Representations of Circle Graphs

Chaplick, Steven and Fulek, Radoslav and Klavík, Pavel (2013) Extending Partial Representations of Circle Graphs. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 131-142(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_12).

Full text not available from this repository.


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 R′ giving some pre-drawn chords that represent an induced subgraph of G. The question is whether one can extend R′ to a representation 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.

Item Type: Conference Paper
Classifications: Z Theory > Z.250 Geometry
Z Theory > Z.500 Representations
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1367

Actions (login required)

View Item View Item