article
Extending partial representations of circle graphs
published
yes
Steven
Chaplick
author
Radoslav
Fulek
author 39F3FFE4-F248-11E8-B48F-1D18A9856A870000-0001-8485-1774
Pavel
Klavík
author
UlWa
department
International IST Postdoc Fellowship Programme
project
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.
Wiley2019
eng
Journal of Graph Theory
03649024
1309.239910.1002/jgt.22436
914365-394
S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of circle graphs,” <i>Journal of Graph Theory</i>, vol. 91, no. 4, pp. 365–394, 2019.
Chaplick S, Fulek R, Klavík P. Extending partial representations of circle graphs. <i>Journal of Graph Theory</i>. 2019;91(4):365-394. doi:<a href="https://doi.org/10.1002/jgt.22436">10.1002/jgt.22436</a>
Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of circle graphs. Journal of Graph Theory. 91(4), 365–394.
Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial Representations of Circle Graphs.” <i>Journal of Graph Theory</i> 91, no. 4 (2019): 365–94. <a href="https://doi.org/10.1002/jgt.22436">https://doi.org/10.1002/jgt.22436</a>.
S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory 91 (2019) 365–394.
Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.” <i>Journal of Graph Theory</i>, vol. 91, no. 4, Wiley, 2019, pp. 365–94, doi:<a href="https://doi.org/10.1002/jgt.22436">10.1002/jgt.22436</a>.
Chaplick, S., Fulek, R., & Klavík, P. (2019). Extending partial representations of circle graphs. <i>Journal of Graph Theory</i>, <i>91</i>(4), 365–394. <a href="https://doi.org/10.1002/jgt.22436">https://doi.org/10.1002/jgt.22436</a>
57902018-12-30T22:59:15Z2020-08-11T10:10:24Z