Structures And Algorithmic Problems Of Interval Graphs And Related Graph Classes

Interval graphs arise so naturally that they must be studied from the applica-tion viewpoint. The mathematical theory of interval graphs was developed with a view towards applications by researchers at the RAND Corporation’s mathematics department.This paper is mainly about interval graphs and their algorithms. Our main results are the following:The first part is about rigid interval graphs and unit interval graphs. We devel-op the MNS properties of rigid interval graphs and characterize this graph class in several different ways. This allows us obtain several linear time multi-sweep MNS algorithms for recognizing rigid interval graphs and unit interval graphs, generalizing a corresponding3-sweep LBFS algorithm for unit interval graph recognition designed by Corneil in2004. For unit interval graphs, we even present a new linear time2-sweep MNS certifying recognition algorithm.The second part is about general interval graphs. In their2009paper, 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. Thanks to the LBFS structure theory established mainly by Corneil et al., we are able to present a4-sweep LBFS algorithm which determines whether or not the input graph is a unit interval graph or an interval graph. Till now, seems that the only known linear time certifying recognition algorithm for interval graphs is reported by Kratsch et al.. This algorithm makes use of the recognition algorithm of Korte and Mohring, which in turn applies the data structure called MPQ tree. Our4-sweep LBFS interval graph recognition algorithm can be further developed into a certifying algorithm and does not involve any complicated data structure and can be executed in linear time.The third part is about the graph Hamiltonian property. Our main discovery is that the existence of a thick Hamiltonian ordering will guarantee that the graph has various kinds of spanning connectivity properties and for interval graphs, quite a few seemingly unrelated spanning connectivity properties are equivalent to the existence of a thick Hamiltonian ordering. Due to the connection between Hamiltonian thickness and spanning connectivity properties, we can present several linear time algorithms for relevant problems. An open problem in [12] is to determine the computational complexity of the problem of calculating the spanning rail connectivity for interval graphs or even proper interval graphs. We give a linear time algorithm to solve this problem.The last part is about the1HP and1PC problem of interval graphs. In1993, Dam-aschke raised a open problem that whether or not there exists polynomial algorithm to solve the1PC/1HP problem on interval graphs. In2010, Asdre and Nikolopoulos gives an O(n3)-time algorithm. We give an0(n+m)-time algorithm to solve the1PC/1HP problem on interval graphs.