2026-07-23T08:46:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25561 2026-03-19T13:35:01Z ddc:004 open_access

Circle Graphs Can Be Recognized in Linear Time Paul, Christophe Rutter, Ignaz graph classes circle graphs graph algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christophe Paul and Ignaz Rutter 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.72 urn:nbn:de:0030-drops-255614 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.72 eng https://creativecommons.org/licenses/by/4.0/legalcode