Record link: 
http://hdl.handle.net/20.500.12708/230300
-
Title: 
A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
en
Citation: 
Ajaykrishnan E S, Ganian, R., Lokshtanov, D., & Surianarayanan, V. (2026). A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs. In S. Assadi & E. Rotenberg (Eds.), 2026 SIAM Symposium on Simplicity in Algorithms (SOSA) (pp. 65–80). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611978964.6
-
Publisher DOI: 
10.1137/1.9781611978964.6
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Ajaykrishnan E S 
Ganian, Robert 
Lokshtanov, Daniel 
Surianarayanan, Vaishali 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
E056-13 - Fachbereich LogiCS 
-
Published in: 
2026 SIAM Symposium on Simplicity in Algorithms (SOSA) 
-
ISBN: 
978-1-61197-896-4
-
DOI of the book: 
10.1137/1.9781611978964
-
Date (published): 
2026
-
Event name: 
SIAM Symposium on Simplicity in Algorithms (SOSA26) 
en
Event date: 
12-Jan-2026 - 14-Jan-2026
-
Event place: 
Vancouver, Canada
-
Number of Pages: 
16
-
Publisher: 
Society for Industrial and Applied Mathematics
-
Peer reviewed: 
Yes
-
Keywords: 
Circle Graphs; Graph Coloring (3-Coloring); Quasi-Polynomial Time Algorithms
en
Abstract: 
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ᴼ(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, ≺) 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.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

9
checked on Aug 25, 2026

Google ScholarTM

Check