# Extending partial representations of circle graphs

Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of circle graphs. Journal of Graph Theory. 91(4), 365–394.

Journal Article | Published | English

Scopus indexed
Author
Chaplick, Steven; Fulek, RadoslavISTA ; Klavík, Pavel
Department
Abstract
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 predrawn chords that represent an induced subgraph of G. The question is whether one can extend R′ to a representation R of the entire graph G, that is, whether one can draw the remaining chords into a partially predrawn representation to obtain a representation of G. Our main result is an O(n3) time algorithm for partial representation extension of circle graphs, where n is the number of vertices. To show this, we describe the structure of all representations of a circle graph using split decomposition. This can be of independent interest.
Publishing Year
Date Published
2019-08-01
Journal Title
Journal of Graph Theory
Volume
91
Issue
4
Page
365-394
ISSN
IST-REx-ID

### Cite this

Chaplick S, Fulek R, Klavík P. Extending partial representations of circle graphs. Journal of Graph Theory. 2019;91(4):365-394. doi:10.1002/jgt.22436
Chaplick, S., Fulek, R., & Klavík, P. (2019). Extending partial representations of circle graphs. Journal of Graph Theory. Wiley. https://doi.org/10.1002/jgt.22436
Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial Representations of Circle Graphs.” Journal of Graph Theory. Wiley, 2019. https://doi.org/10.1002/jgt.22436.
S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of circle graphs,” Journal of Graph Theory, vol. 91, no. 4. Wiley, pp. 365–394, 2019.
Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of circle graphs. Journal of Graph Theory. 91(4), 365–394.
Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.” Journal of Graph Theory, vol. 91, no. 4, Wiley, 2019, pp. 365–94, doi:10.1002/jgt.22436.
All files available under the following license(s):
This Item is protected by copyright and/or related rights. [...]

Access Level
Open Access

### Export

Marked Publications

Open Data ISTA Research Explorer

arXiv 1309.2399