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 metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00805194
Contributor : Christophe Paul <>
Submitted on : Wednesday, March 27, 2013 - 12:56:55 PM
Last modification on : Monday, March 25, 2019 - 9:57:01 AM

Links full text

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

284