| Title: |
Circle Graphs Can Be Recognized in Linear Time |
| Authors: |
Paul, Christophe; Rutter, Ignaz |
| Contributors: |
Christophe Paul and Ignaz Rutter |
| Publisher Information: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| Publication Year: |
2026 |
| Collection: |
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| Subject Terms: |
graph classes; circle graphs; graph algorithms |
| Description: |
To date, the best circle graph recognition algorithm, due to Gioan et al. [E. Gioan et al., 2014] runs in almost linear time as it relies on a split decomposition algorithm [E. Gioan et al., 2014] that uses the union-find data-structure [B.A. Galler and M.J. Fischer, 1964; R. Tarjan, 1975]. We show that in the case of circle graphs, the PC-tree data-structure [W. K. Shih and W. L. Hsu, 1999] allows one to avoid the union-find data-structure to compute the split decomposition in linear time. As a consequence, we obtain the first linear-time recognition algorithm for circle graphs. |
| Document Type: |
article in journal/newspaper; conference object |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.72 |
| DOI: |
10.4230/LIPIcs.STACS.2026.72 |
| Availability: |
https://doi.org/10.4230/LIPIcs.STACS.2026.72; https://nbn-resolving.org/urn:nbn:de:0030-drops-255614; https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.72 |
| Rights: |
https://creativecommons.org/licenses/by/4.0/legalcode |
| Accession Number: |
edsbas.9EA13B5 |
| Database: |
BASE |