Practical and efficient circle graph recognition
From MaRDI portal
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.
Recommendations
Cites work
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithmic graph theory and perfect graphs
- An O(n2) Algorithm for Undirected Split Decomposition
- Circle graph obstructions under pivoting
- Circle graphs and monadic second-order logic
- Decomposition of Directed Graphs
- Dynamic Distance Hereditary Graphs Using Split Decomposition
- Efficiency of a Good But Not Linear Set Union Algorithm
- Excluding a bipartite circle graph from line graphs
- Graph-Theoretic Concepts in Computer Science
- Graphic presentations of isotropic systems
- Introduction to algorithms
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- LexBFS-orderings and powers of chordal graphs
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- Practical and efficient split decomposition via graph-labelled trees
- Rank-width and vertex-minors
- Recognition of Circle Graphs
- Recognizing circle graphs in polynomial time
- Reconnaissance des graphes de cordes
- Reducing prime graphs and recognizing circle graphs
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- The monadic second-order logic of graphs XVI : Canonical graph decompositions
Cited in
(27)- scientific article; zbMATH DE number 3933116 (Why is no real title available?)
- Parameterized domination in circle graphs
- Fully dynamic recognition of proper circular-arc graphs
- Recognition of Circle 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
- scientific article; zbMATH DE number 5630984 (Why is no real title available?)
- scientific article; zbMATH DE number 3997838 (Why is no real title available?)
- Practical and efficient split decomposition via graph-labelled trees
- The expansion of a chord diagram and the Tutte polynomial
- From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals
- Notes on a theorem of Naji
- 2-nested matrices: towards understanding the structure of circle graphs
- A survey of the algorithmic aspects of modular decomposition
- Isotropic matroids. II: Circle graphs
- scientific article; zbMATH DE number 437537 (Why is no real title available?)
- 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
- scientific article; zbMATH DE number 6007785 (Why is no real title available?)
- Optical Graph Recognition
- Circle graph isomorphism in almost linear time
- Forbidden induced subgraph characterization of circle graphs within split graphs
- Leaf sector covers with applications on circle 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)
