---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Steven
foaf_name: Chaplick, Steven
foaf_surname: Chaplick
- foaf_Person:
foaf_givenName: Radoslav
foaf_name: Fulek, Radoslav
foaf_surname: Fulek
foaf_workInfoHomepage: http://www.librecat.org/personId=39F3FFE4-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0001-8485-1774
- foaf_Person:
foaf_givenName: Pavel
foaf_name: Klavík, Pavel
foaf_surname: Klavík
bibo_doi: 10.1002/jgt.22436
bibo_issue: '4'
bibo_volume: 91
dct_date: 2019^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/03649024
dct_language: eng
dct_publisher: Wiley@
dct_title: Extending partial representations of circle graphs@
...