Circle graph isomorphism in almost linear time

DOI10.1007/978-3-031-20350-3_15arXiv1908.09151OpenAlexW2969356218MaRDI QIDQ6111955

Peter Zeman, Pavel Klavík, Vít Kalisz

Publication date: 4 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1908.09151

zbMATH Keywords

split decompositioncircle graphsgraph canonizationgraph isomorphism problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Practical and efficient circle graph recognition
• Practical and efficient split decomposition via graph-labelled trees
• Unimodularity and circle graphs
• Reducing prime graphs and recognizing circle graphs
• Lexicographically least circular substrings
• Local complementation and interlacement graphs
• On a characterization of Gauss codes
• Efficient graph representations
• Rank-width and vertex-minors
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• A Combinatorial Decomposition Theory
• Fast canonization of circular strings
• Decomposition of Directed Graphs
• Recognition of Circle Graphs
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Recognizing circle graphs in polynomial time
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs

This page was built for publication: Circle graph isomorphism in almost linear time