Semi-proper interval graphs

We present a new subclass of interval graphs that generalizes connected proper interval graphs. These graphs are characterized by vertex orderings called connected perfect elimination orderings (PEO), i.e., PEOs where consecutive vertices are adjacent. Alternatively, these graphs can also be characterized by special interval models and clique orderings. We present a linear-time recognition algorithm that uses PQ-trees. Furthermore, we study the behavior of multi-sweep graph searches on this graph class. This study also shows that Corneil’s well-known LBFS-recognition algorithm for proper interval graphs can be generalized to a large family of graph searches. Finally, we show that a strong result on the existence of Hamiltonian paths and cycles in proper interval graphs can be generalized to semi-proper interval graphs. • Introduction of semi-proper interval graphs, a novel subclass of interval graphs generalizing connected proper interval graphs. • Linear-time recognition algorithm for semi-proper interval graphs. • Generalization of Corneil’s LBFS recognition algorithm of proper interval graphs. • Generalization of Hamilton properties of proper interval graphs to semi-proper intervals.