# Extending partial representations of circle graphs

S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory (2018).

Download (ext.)

*Journal Article*|

*Epub ahead of print*|

*English*

Author

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

2018-12-17

Journal Title

Journal of Graph Theory

ISSN

IST-REx-ID

### Cite this

Chaplick S, Fulek R, Klavík P. Extending partial representations of circle graphs.

*Journal of Graph Theory*. 2018. doi:10.1002/jgt.22436Chaplick, S., Fulek, R., & Klavík, P. (2018). Extending partial representations of circle graphs.

*Journal of Graph Theory*. https://doi.org/10.1002/jgt.22436Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial Representations of Circle Graphs.”

*Journal of Graph Theory*, 2018. 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*, 2018.Chaplick S, Fulek R, Klavík P. 2018. Extending partial representations of circle graphs. Journal of Graph Theory.

Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.”

*Journal of Graph Theory*, Wiley, 2018, doi:10.1002/jgt.22436.### Export

Marked PublicationsOpen Data IST Research Explorer

### Sources

arXiv 1309.2399