A Simpler Linear-Time Recognition of Circular-Arc Graphs.

We give a linear-time recognition algorithm for circular-arc graphs based on the algorithm of Eschen and Spinrad (Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 128-137, ) and Eschen (PhD thesis, ). Our algorithm both improves the time bound of Eschen and Spinrad, and fixes some flaws in it. Our algorithm is simpler than the earlier linear-time recognition algorithm of McConnell (Algorithmica 37(2):93-147, ), which is the only linear time recognition algorithm previously known. [ABSTRACT FROM AUTHOR]