
11.8. PRACTICAL APPROACHES TO DYNAMIC GRAPH DRAWING 369
Other popular intersection representations are the following. In an interval representation
of a graph each vertex is represented by an interval on the real line. A graph is chordal if
each induced cycle has length three. Gavril [Gav74] shows that chordal graphs are exactly
the intersection graphs of subtrees in a tree. This shows that the class of interval graphs
is contained in the class of chordal graphs. Permutation graphs are the intersection graphs
that can be represented by a set of line segments connecting two parallel lines. Jampani
and Lubiw [JL09] give O(n
3
)-time algorithms recognizing ...