Circle Graph Isomorphism in Almost Linear Time

Abstract

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)\hat{I}\pm (n+m))$ where $n$ is the number of vertices, $m$ is the number of edges and $\hat{I}\pm$ is the inverse Ackermann function. Our algorithm is based on the minimal split decomposition [Cunnigham, 1982] and uses the state-of-art circle graph recognition algorithm [Gioan, Paul, Tedder, Corneil, 2014] in the same running time. It improves the running time $O(nm)$ of the previous algorithm [Hsu, 1995] based on a similar approach.