Extending partial representations of circle graphs

DOI10.1002/JGT.22436MaRDI QIDQ5229540zbMATH OpenOpenAlexWikidataFDO

Authors Steven Chaplick, Radoslav Fulek, Pavel Klavík

Publication date 15 August 2019

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

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

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)

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.

Recommendations

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

Cited in

(12)

• Partial and simultaneous transitive orientations via modular decompositions
• 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 subclasses of chordal graphs
• Extending partial orthogonal drawings
• Extending partial representations of rectangular duals with given contact orientations
• Inserting one edge into a simple drawing is hard
• Extending Partial Orthogonal Drawings
• Extending partial representations of circular-arc graphs
• Extending Partial Representations of Subclasses of Chordal Graphs
• Extending partial representations of circle graphs

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)