Skip to Main content Skip to Navigation
Journal articles

Practical and Efficient Circle Graph Recognition

Emeric Gioan 1 Christophe Paul 1 Marc Tedder 2 Derek Corneil 2 
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Circle graphs are the intersection graphs of chords in a circle. This paper presents the first sub-quadratic recognition algorithm for the class of circle graphs. Our algorithm is O(n + m) times the inverse Ackermann function, α(n + m), whose value is smaller than 4 for any practical graph. The algorithm is based on a new in- cremental Lexicographic Breadth-First Search characterization of circle graphs, and a new efficient data-structure for circle graphs, both developed in the paper. The al- gorithm is an extension of a Split Decomposition algorithm with the same running time developed by the authors in a companion paper.
Document type :
Journal articles
Complete list of metadata
Contributor : Christophe Paul Connect in order to contact the contributor
Submitted on : Wednesday, March 27, 2013 - 12:56:55 PM
Last modification on : Friday, August 5, 2022 - 3:02:53 PM

Links full text




Emeric Gioan, Christophe Paul, Marc Tedder, Derek Corneil. Practical and Efficient Circle Graph Recognition. Algorithmica, Springer Verlag, 2014, 69 (4), pp.759-788. ⟨10.1007/s00453-013-9745-8⟩. ⟨lirmm-00805194⟩



Record views