Extending partial representations of circle graphs

DOI10.1002/JGT.22436zbMATH Open1417.05201arXiv1309.2399OpenAlexW2907472296WikidataQ128737566 ScholiaQ128737566MaRDI QIDQ5229540FDOQ5229540

Authors: Steven Chaplick, Radoslav Fulek, Pavel Klavík 

Publication date: 15 August 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

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 $cal{R}^{\prime }$ giving some pre-drawn chords that represent an induced subgraph of $G$. The question is whether one can extend $cal{R}^{\prime }$ to a representation $calR$ of the entire graph $G$, i.e., whether one can draw the remaining chords into a partially pre-drawn representation to obtain a representation of $G$. Our main result is an $O(n^3)$ 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.

Full work available at URL: https://arxiv.org/abs/1309.2399

Recommendations

• Extending partial representations of circle graphs
• Extending Partial Representations of Subclasses of Chordal Graphs
• Extending partial representations of interval graphs
• Extending partial representations of subclasses of chordal graphs
• scientific article; zbMATH DE number 3970805

zbMATH Keywords

algorithmrecognitionsplit decompositioncircle graphspartial representation extension

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (11)

• Simple algorithms for partial and simultaneous rectangular duals with given contact orientations
• Extending partial representations of trapezoid graphs
• Extending partial representations of circle graphs in near-linear time
• Extending partial representations of rectangular duals with given contact orientations
• Inserting one edge into a simple drawing is hard
• Extending partial representations of proper and unit interval graphs
• Extending Partial Orthogonal Drawings
• Extending partial representations of circular-arc graphs
• Extending Partial Representations of Subclasses of Chordal Graphs
• Extending Partial Orthogonal Drawings
• Partial and simultaneous transitive orientations via modular decompositions

This page was built for publication: Extending partial representations of circle graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5229540)