CS 5984: Algorithms in Bioinformatics

Fall Semester, 2002
Material on Interval Graphs

Ron Shamir's Advanced Topics in Graph Algorithms

• Shamir's lecture notes are available as a technical report which I have reformatted for letter-size paper.

• The definition of an interval graph is given in Chapter 1.

• The definitions of perfect elimination ordering (PEO) and triangulated graphs are given in Chapters 3 and 4, as is an algorithm for recognizing triangulated graphs using PEOs.

• The problem of recognizing comparability graphs is covered in Chapter 9.

• The problem of recognizing interval graphs is covered in Chapters 10 and 11.

• The important tool of PQ-trees is covered in Chapter 11.

Lecture Notes for Graph-Theoretic Algorithms (University of Waterloo)

• The definition of an interval graph is given in the notes for Lecture 1.

• The definitions of perfect elimination ordering (PEO) and chordal graphs are given in the notes for Lecture 4, as is a proof that a graph with a PEO must be chordal.

• The proof of the converse that a chordal graph must have a PEO is given in the notes for Lecture 5.

• The lexical BFS algorithm for recognizing chordal graphs is given in the notes for Lectures 5 and 6.

• The problem of recognizing interval graphs is discussed in the notes for Lectures 9 and 10. The mention of PQ-trees there is brief.