Authors: Andrew R. Curtis ¹; Min Chih Lin ²; Ross M. Mcconnell ³; Yahav Nussbaum ⁴; Francisco Juan Soulignac ²; Jeremy P. Spinrad ⁵; Jayme Luiz Szwarcfiter ⁶

• 1 David R. Cheriton School of Computer Science
• 2 Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires]
• 3 Computer Science Department, Colorado State University
• 4 School of Computer Science
• 5 Department of Electrical Engineering & Computer Science [Nashville]
• 6 Instituto de Matemática da Universidade Federal do Rio de Janeiro

Discrete Algorithms

[en]
We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. Our algorithm is similar to the isomorphism algorithm for interval graphs of Lueker and Booth, but works on PC trees, which are unrooted and have a cyclic nature, rather than with PQ trees, which are rooted. This algorithm leads to linear-time isomorphism algorithms for related graph classes, including Helly circular-arc graphs, Γ circular-arc graphs, proper circular-arc graphs and convex-round graphs.