A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909899773968384 |
|---|---|
| author | S, Ajaykrishnan E Ganian, Robert Lokshtanov, Daniel Surianarayanan, Vaishali |
| author_facet | S, Ajaykrishnan E Ganian, Robert Lokshtanov, Daniel Surianarayanan, Vaishali |
| contents | 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, \prec)$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_09707 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs S, Ajaykrishnan E Ganian, Robert Lokshtanov, Daniel Surianarayanan, Vaishali Data Structures and Algorithms Computational Geometry 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, \prec)$ 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. |
| title | A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/2511.09707 |