Isomorphism of graph classes related to the circular-ones property
Andrew R. Curtis (1), Min Chih Lin (2), Ross M. Mcconnell (3) (4), Yahav Nussbaum (5), Francisco Juan Soulignac (2), Jeremy P. Spinrad (6), Jayme Luiz Szwarcfiter (7)
(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) Colorado State University [Fort Collins]
(5) School of Computer Science
(6) Department of Electrical Engineering & Computer Science [Nashville]
(7) Instituto de Matemática da Universidade Federal do Rio de Janeiro
Isomorphism of graph classes related to the circular-ones property
Andrew R. Curtis (1), Min Chih Lin (2), Ross M. Mcconnell (3) (4), Yahav Nussbaum (5), Francisco Juan Soulignac (2), Jeremy P. Spinrad (6), Jayme Luiz Szwarcfiter (7)
(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) Colorado State University [Fort Collins]
(5) School of Computer Science
(6) Department of Electrical Engineering & Computer Science [Nashville]
(7) Instituto de Matemática da Universidade Federal do Rio de Janeiro
Abstract
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.
