A simpler linear-time recognition of circular-arc graphs

Abstract. We give a linear time recognition algorithm for circular-arc graphs. Our algorithm is much simpler than the linear time recognition algorithm of McConnell [10] (which is the only linear time recognition algorithm previously known). Our algorithm is a new and careful implementation of the algorithm of Eschen and Spinrad [4,5]. We also tighten the analysis of Eschen and Spinrad.