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
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.
Full Text: PDF PostScript