Practical and efficient circle graph recognition

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

zbMATH Keywords

split decompositioncircle graphs

Mathematics Subject Classification ID

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