Practical and efficient circle graph recognition
From MaRDI portal
Publication:472484
DOI10.1007/s00453-013-9745-8zbMath1303.05190arXiv1104.3284OpenAlexW2050872937MaRDI QIDQ472484
Christophe Paul, Emeric Gioan, Marc Tedder, Derek Gordon Corneil
Publication date: 19 November 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1104.3284
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)
Related Items (15)
Notes on a theorem of Naji ⋮ 2-nested matrices: towards understanding the structure of circle graphs ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals ⋮ Circle graph isomorphism in almost linear time ⋮ Parameterized domination in circle graphs ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Practical and efficient split decomposition via graph-labelled trees ⋮ Diamond-free circle graphs are Helly circle ⋮ The expansion of a chord diagram and the Tutte polynomial ⋮ Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search ⋮ Splitting cubic circle graphs ⋮ Isotropic matroids. II: Circle graphs ⋮ A characterization of circle graphs in terms of multimatroid representations ⋮ Forbidden induced subgraph characterization of circle graphs within split graphs
Cites Work
- Unnamed Item
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- Practical and efficient split decomposition via graph-labelled trees
- Circle graphs and monadic second-order logic
- Reconnaissance des graphes de cordes
- Graphic presentations of isotropic systems
- Reducing prime graphs and recognizing circle graphs
- LexBFS-orderings and powers of chordal graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Algorithmic graph theory and perfect graphs
- Rank-width and vertex-minors
- Excluding a bipartite circle graph from line graphs
- Circle graph obstructions under pivoting
- Decomposition of Directed Graphs
- Efficiency of a Good But Not Linear Set Union Algorithm
- Algorithmic Aspects of Vertex Elimination on Graphs
- Recognition of Circle Graphs
- An O(n2) Algorithm for Undirected Split Decomposition
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- Recognizing circle graphs in polynomial time
- The monadic second-order logic of graphs XVI : Canonical graph decompositions
- Dynamic Distance Hereditary Graphs Using Split Decomposition
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Practical and efficient circle graph recognition
