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 ⊆ G H ⊆ G and a representation R' R ′ of H . The question is whether G admits a representation R R whose restriction to H is R' R ′ . 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) α (n + m)) O ( ( n + m ) α ( n + m ) ) time, thereby improving over an O(n³) 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.