2013/09/10 by Steven Chaplick, Chaplick, Steven, Radoslav Fulek +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1309.2399
openalex publication_date 2013/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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' giving some pre-drawn chords that represent an induced subgraph of G. The question is whether one can extend \cal R' to a representation \cal R 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(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.