Circle Graph Isomorphism in Almost Linear Time

Vít Kalisz, Pavel Klavík, Peter Zeman

Circle graphs are intersection graphs of chords of a circle. In this paper, we present a new algorithm for the circle graph isomorphism problem running in time $O((n+m)\alpha (n+m))$ whe…