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