Isomorphism of graph classes related to the circular-ones property

ANDREW R. CURTIS; MIN CHIH LIN; ROSS M. MCCONNELL; YAHAV NUSSBAUM; FRANCISCO J. SOULIGNAC; JEREMY P. SPINRAD; JAYME L. SZWARCFITER

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE (DMTCS)

DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE

Lugar: Nancy; Año: 2013 vol. 15 p. 157 - 182

1365-8050

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, $Gamma$ circular-arc graphs, proper circular-arc graphs and convex-round graphs.