2020/10/07 by Yixin Cao, Cao, Yixin
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Numerical Methods and Algorithms
paper · pdf · doi:10.48550/arxiv.2010.03354
openalex publication_date 2020/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Corneil, Olariu, and Stewart [SODA 1998; SIAM Journal on Discrete Mathematics 2009] presented a recognition algorithm for interval graphs by six graph searches. Li and Wu [Discrete Mathematics & Theoretical Computer Science 2014] simplified it to only four. The great simplicity of the latter algorithm is however eclipsed by the complicated and long proofs. The main purpose of this paper is to present a new and significantly short proof for Li and Wu's algorithm, as well as a simpler implementation. We also give a self-contained simpler interpretation of the recognition algorithm of Corneil [Discrete Applied Mathematics 2004] for unit interval graphs, based on three sweeps of graph searches. Moreover, we show that two sweeps are already sufficient. Toward the proofs of the main results, we make several new structural observations that might be of independent interests.