A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs

A graph \(G\) is a circle graph if it is an intersection graph of chords of a unit circle. We give an algorithm that takes as input an n vertex circle graph \(G\), runs in time at most \(n^O(\log n)\) and finds a proper 3-coloring of \(G\), if one exists. As a consequence we obtain an algorithm with the same running time to determine whether a given ordered graph \((G, \unicode{x227A})\) has a 3-page book embedding. This gives a partial resolution to the well known open problem of Dujmović and Wood [Discret. Math. Theor. Comput. Sci. 2004], Eppstein [2014], and Bachmann, Rutter and Stumpf [J. Graph Algorithms Appl. 2024] of whether 3-Coloring on circle graphs admits a polynomial time algorithm.