### A Four-Sweep LBFS Recognition Algorithm for Interval Graphs

*Peng Li, Yaokun Wu*

#### Abstract

In their 2009 paper, Corneil

*et al.*design a linear time interval graph recognition algorithm based on six sweeps of Lexicographic Breadth-First Search (LBFS) and prove its correctness. They believe that their corresponding 5-sweep LBFS interval graph recognition algorithm is also correct. Thanks to the LBFS structure theory established mainly by Corneil*et al.*, we are able to present a 4-sweep LBFS algorithm which determines whether or not the input graph is a unit interval graph or an interval graph. Like the algorithm of Corneil*et al.*, our algorithm does not involve any complicated data structure and can be executed in linear time.Full Text: PDF PostScript