Chordal Graphs
   Recognition: O(n+m) (Rose and Tarjan)

Chordal Bipartite Graphs
   Recognition: O(n^2) (Spinrad, Paige and Tarjan), O(mlogn) (Paige and Tarjan)

Circle Graphs
   Recognition: O(n^2) (Ma and Spinrad)

Circular-Arc Graphs
   Recognition: O(n^2) (Eschen and Spinrad)

Comparability Graphs
   Recognition: O(matrix multiplication) (Spinrad)

Interval Graphs
   Recognition: O(n+m) (Booth and Leuker)

Permutation Graphs
   Recognition: O(n^2) (Spinrad) O(n+m) McConnell and Spinrad forthcoming

Trapezoid Graphs
   Recognition: O(n^2) (Ma and Spinrad)

Weakly Triangulated Graphs
   Recognition: O(n^4) (Spinrad and Sritharan)