Circle graph isomorphism in almost linear time

DOI10.1007/978-3-031-20350-3_15MaRDI QIDQ6111955zbMATH OpenOpenAlexFDO

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

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

circle graphsgraph canonizationgraph isomorphism problemsplit decomposition

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Circle graphs are intersection graphs of chords of a circle. In this paper, we present a new algorithm for the circle graph isomorphism problem running in time $O((n+m)alpha(n+m))$ where $n$ is the number of vertices, $m$ is the number of edges and $alpha$ is the inverse Ackermann function. Our algorithm is based on the minimal split decomposition [Cunnigham, 1982] and uses the state-of-art circle graph recognition algorithm [Gioan, Paul, Tedder, Corneil, 2014] in the same running time. It improves the running time $O(nm)$ of the previous algorithm [Hsu, 1995] based on a similar approach.

Cites work

• O(M\cdot N) Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• A Combinatorial Decomposition Theory
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• Decomposition of Directed Graphs
• Efficient graph representations
• Fast canonization of circular strings
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• Isomorphism of graph classes related to the circular-ones property
• Lexicographically least circular substrings
• Local complementation and interlacement graphs
• On a characterization of Gauss codes
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Practical and efficient circle 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
• Reducing prime graphs and recognizing circle graphs
• Unimodularity and circle graphs

Cited in

(4)

• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• scientific article; zbMATH DE number 6829367 (Why is no real title available?)
• Extending partial representations of circle graphs in near-linear time
• Sublinear hitting sets for some geometric graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6111955)