区间图的定义简单自然,关于它已经建立起丰富优美的数学理论,还有许多深刻的公开研究问题和猜想。区间图模型也在大量应用问题中出现,其实关于区间图的最早一批系统结果就来自于美国兰德公司数学实验室的一批著名数学家。本文工作主要是关于区间图及其算法,主要结果如下：第一部分是关于严格区间图和单位区间图的.我们探索了严格区间图的极大邻域搜索(MNS)性质并从几个方面刻画了严格区间图,获得了3步MNS线性算法来识别严格区间图和单位区间图,从而推广了Corneil在2004年设计的识别单位区间图的3步字典序宽度优先搜索(LBFS)算法.对单位区间图我们还提出了新的两步MNS认证算法.第二部分是关于一般区间图的Corneil等人在2009年设计了6步LBFS算法来识别区间图.在他们的基础上我们设计出4步LBFS区间图识别算法,这个算法还可识别单位区间图.目前唯一已知的区间图认证算法是由Kratsch等人给出的,他们利用了Korte和Mohring给出的区间图识别算法,且用了叫做MPQ树的复杂数据结构.我们的算法可改进为区间图的认证算法,不包含任何复杂的存储结构且可在线性时间内实现.第三部分主要研究图的汉密尔顿性质.我们的主要发现是如果一个图存在充分厚的汉密尔顿排序,则它有很多支撑连通性质,特别地对于区间图而言,相当多看起来无关的支撑连通性质都等价于存在某个k-厚的汉密尔顿序.基于汉密尔顿厚度和支撑汉密尔顿连通性质的联系,我们得到了一些相关问题的线性算法Broersma等人在文献[12]中提出了一个开放性的问题：确定计算区间图或者单位区间图的支撑轨道连通性的时间复杂度.我们给出了一个线性的算法来解决这个问题,从而回答了Broersma等人的开放性问题.最后一部分是关于区间图1PC/1HP问题的Damaschke在1993年提出区间图1PC/1HP问题是否有多项式算法的公开问题.在2010年,Asdre和Nikolopoulos给出O(n3)的算法.我们找到了O(n+m)的算法来解决区间图上的1PC/1HP问题.