A Linear Time Algorithm for Deciding Interval Graph Isomorphism

A graph is an interval graph tf and only if each of Its verttces can be associated with an interval on the real hne m such a way that two vertices are adjacent m the graph exactly when the corresponding mtervals have a nonempty mtersectmn An effictent algonthrn for testing tsomorpinsm of interval graphs ts unplemented using a data structure called a PQ-tree.The algorithm runs m O(n + e) steps for graphs having n vemces and e edges It is shown that for a somewhat larger class of graphs, namely the chordal graphs, lsomorpinsm is as hard as for general graphs KEY WORDS AND PHRASES graph tsomorpinsm algonthms, polynomial reduclinhty, intersection graphs, interval graphs, chordal graphs, ngtd clrcmt graphs CR CATEGORIES. 5 25, 5.32 Permission to copy without fee all or part of tins material ,s granted provtded that the