Extending Partial Representations of Circle Graphs in Near-Linear Time

The partial representation extension problem generalizes the recognition problem for geometric intersection graphs. The input consists of a graph G, a subgraph \(H \subseteq G\) $H\subseteq G$ and a representation  \(\mathcal R'\) ${\mathcal{R}}^{\prime }$ of H. The question is whether G admits a representation \(\mathcal R\) $\mathcal{R}$ whose restriction to H is \(\mathcal R'\) ${\mathcal{R}}^{\prime }$ . We study this question for circle graphs, which are intersection graphs of chords of a circle. Their representations are called chord diagrams. We show that for a graph with n vertices and m edges the partial representation extension problem can be solved in \(O((n + m) \alpha (n + m))\) $O((n+m)\alpha (n+m))$ time, thereby improving over an \(O(n^3)\) $O(n^3)$ -time algorithm by Chaplick et al. (J Graph Theory 91(4), 365–394, 2019). The main technical contributions are a canonical way of orienting chord diagrams and a novel compact representation of the set of all canonically oriented chord diagrams that represent a given circle graph G, which is of independent interest.