https://hal.inria.fr/hal-01188908Li, PengPengLiDepartment of mathematics and MOE-LSC - Shanghai Jiao Tong University [Shanghai]Wu, YaokunYaokunWuDepartment of mathematics and MOE-LSC - Shanghai Jiao Tong University [Shanghai]A four-sweep LBFS recognition algorithm for interval graphsHAL CCSD2014chordal graphinterval graphinterval representationLexicographic Breadth-First Searchperfect orderingrecognition algorithm[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Episciences Iam, Coordination2015-08-31 17:03:342017-09-07 01:03:472015-09-01 13:24:16enJournal articleshttps://hal.inria.fr/hal-01188908/document10.46298/dmtcs.2094application/pdf1In 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.