Practical and efficient circle graph recognition
From MaRDI portal
Publication:472484
DOI10.1007/S00453-013-9745-8zbMATH Open1303.05190arXiv1104.3284OpenAlexW2050872937MaRDI QIDQ472484FDOQ472484
Authors: Emeric Gioan, Christophe Paul, Marc Tedder, Derek G. Corneil 
Publication date: 19 November 2014
Published in: Algorithmica (Search for Journal in Brave)
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, {alpha}(n + m), whose value is smaller than 4 for any practical graph. The algorithm is based on a new incremental Lexicographic Breadth-First Search characterization of circle graphs, and a new efficient data-structure for circle graphs, both developed in the paper. The algorithm is an extension of a Split Decomposition algorithm with the same running time developed by the authors in a companion paper.
Full work available at URL: https://arxiv.org/abs/1104.3284
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Introduction to algorithms
- Algorithmic graph theory and perfect graphs
- Efficiency of a Good But Not Linear Set Union Algorithm
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Rank-width and vertex-minors
- Algorithmic Aspects of Vertex Elimination on Graphs
- Decomposition of Directed Graphs
- Recognition of Circle Graphs
- Reconnaissance des graphes de cordes
- Graphic presentations of isotropic systems
- Reducing prime graphs and recognizing circle graphs
- Recognizing circle graphs in polynomial time
- Circle graphs and monadic second-order logic
- Graph-Theoretic Concepts in Computer Science
- An O(n2) Algorithm for Undirected Split Decomposition
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- The monadic second-order logic of graphs XVI : Canonical graph decompositions
- Dynamic Distance Hereditary Graphs Using Split Decomposition
- Practical and efficient split decomposition via graph-labelled trees
- LexBFS-orderings and powers of chordal graphs
- Excluding a bipartite circle graph from line graphs
- Circle graph obstructions under pivoting
Cited In (27)
- Title not available (Why is that?)
- Parameterized domination in circle graphs
- Recognition of Circle Graphs
- Fully dynamic recognition of proper circular-arc graphs
- Extending partial representations of circle graphs in near-linear time
- Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search
- A characterization of circle graphs in terms of multimatroid representations
- Splitting cubic circle graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- The expansion of a chord diagram and the Tutte polynomial
- From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals
- Practical and efficient split decomposition via graph-labelled trees
- 2-nested matrices: towards understanding the structure of circle graphs
- Notes on a theorem of Naji
- A survey of the algorithmic aspects of modular decomposition
- Isotropic matroids. II: Circle graphs
- Title not available (Why is that?)
- Diamond-free circle graphs are Helly circle
- Reconnaissance des graphes de cordes
- Reducing prime graphs and recognizing circle graphs
- On polygon numbers of circle graphs and distance hereditary graphs
- Title not available (Why is that?)
- Optical Graph Recognition
- Circle graph isomorphism in almost linear time
- Leaf sector covers with applications on circle graphs
- Forbidden induced subgraph characterization of circle graphs within split graphs
This page was built for publication: Practical and efficient circle graph recognition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472484)
