相交图是图中非常重要的有着广泛应用的图，相交图的应用背景涉及生物、矩阵分析、统计学、任务分配等多个领域，而正是由于其具有广泛应用背景使得它在最近二三十年间得到了迅速的发展。相交图中有一些图类，对于图同构问题等有着良好的线性时间算法。在相交图中，区间图和置换图等，是被广泛研究的图类，原因之一是它们自然的出现在如任务调度，基因组学，系统发育和考古学等方面。　　正因为这类图在现实世界中有着很重要的应用，因此本文对于相交图的编码和基于编码的相交图图同构算法进行了深入研究。本文系统地介绍了图的发展历史，国内外对于图编码和图同构的研究现状。然后，针对图编码和图同构，进行了研究。图编码的目的主要是为了压缩存储空间，并且能够还原图的信息，加快图的同构查询。上述目标并不能同时满足，有的算法达到很好的压缩比例，但对于编码后的图，无法还原成原来的图。本文的主要工作是，使得编码以后的图，能加快图的同构查询。本文针对图的同构问题，深入研究了区间图的编码和同构问题，对已有的PQ树进行了改进，得到了标签PQ树和它的规范化编码表示，在此基础上提出了基于标签PQ树的区间图图同构算法——GIBPQ-Tree算法，该算法具有线性时间复杂度。本文对已有的图谱编码算法进行了改进，在邻接矩阵的特征值的基础上加入顶点的度，提出了改进的基于图谱编码相交图图同构算法——GIBS算法，该算法具有良好的时间性能，能应用在更广泛的图同构中。　　最后，对所提出的图同构算法进行了相应的实验性能评价与分析。对于GIBPQ-Tree算法的响应时间进行了对比分析。对比分析了两个图同构算法在区间图上的同构查询响应时间。实验结果表明，两种算法都具有较高的有效性和良好的时间性能。