[{"status":"public","type":"journal_article","arxiv":1,"author":[{"last_name":"Chaplick","full_name":"Chaplick, Steven","first_name":"Steven"},{"full_name":"Fulek, Radoslav","first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774"},{"full_name":"Klavík, Pavel","first_name":"Pavel","last_name":"Klavík"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1309.2399"}],"oa_version":"Preprint","day":"01","publication_identifier":{"issn":["03649024"]},"month":"08","language":[{"iso":"eng"}],"publication":"Journal of Graph Theory","title":"Extending partial representations of circle graphs","issue":"4","article_processing_charge":"No","oa":1,"date_updated":"2023-08-24T14:30:43Z","scopus_import":"1","intvolume":"        91","isi":1,"project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"volume":91,"quality_controlled":"1","page":"365-394","department":[{"_id":"UlWa"}],"date_published":"2019-08-01T00:00:00Z","publisher":"Wiley","publication_status":"published","abstract":[{"lang":"eng","text":"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."}],"external_id":{"arxiv":["1309.2399"],"isi":["000485392800004"]},"article_type":"original","_id":"5790","doi":"10.1002/jgt.22436","date_created":"2018-12-30T22:59:15Z","citation":{"ama":"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>","ieee":"S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of circle graphs,” <i>Journal of Graph Theory</i>, vol. 91, no. 4. Wiley, pp. 365–394, 2019.","short":"S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory 91 (2019) 365–394.","ista":"Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of circle graphs. Journal of Graph Theory. 91(4), 365–394.","mla":"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>.","chicago":"Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial Representations of Circle Graphs.” <i>Journal of Graph Theory</i>. Wiley, 2019. <a href=\"https://doi.org/10.1002/jgt.22436\">https://doi.org/10.1002/jgt.22436</a>.","apa":"Chaplick, S., Fulek, R., &#38; Klavík, P. (2019). Extending partial representations of circle graphs. <i>Journal of Graph Theory</i>. Wiley. <a href=\"https://doi.org/10.1002/jgt.22436\">https://doi.org/10.1002/jgt.22436</a>"},"year":"2019","ec_funded":1}]