The Ultimate Interval Graph Recognition Algorithm? (Extended Abstract).
Derek Gordon Corneil, Stephan Olariu, Lorna K. Stewart · 1998
) Derek G. Corneil Stephan Olariu y Lorna Stewart z Summary of Results An independent set of three vertices is called an asteroidal triple if between every two vertices in the triple there exists a path avoiding the neighbourhood of the third. A graph is asteroidal triplefree (AT-free, for short) if it contains no asteroidal triple. A classic result states that a graph is an interval graph if and only if it is chordal and AT-free. Our main contribution is to exhibit a very simple, linear-time, recognition algorithm for interval graphs involving four sweeps of the wellknown Lexicographic Breadth First Search. Unlike the vast majority of existing algorithms, we do not use maximal cliques in our algorithm -- we rely, instead, on a less well-known characterization by a linear order of the vertices. 1 Introduction Interval graphs arise naturally in the process of modeling real-life situations, especially those involving time dependencies or other restrictions that are linear...