Extending partial representations of circle graphs
Chaplick, Steven
Fulek, Radoslav
Klavík, Pavel
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.
Wiley
2019
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.app.ist.ac.at/record/5790
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>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1002/jgt.22436
info:eu-repo/semantics/altIdentifier/issn/03649024
info:eu-repo/semantics/altIdentifier/arxiv/1309.2399
info:eu-repo/grantAgreement/EC/FP7/291734
info:eu-repo/semantics/openAccess