A recognition algorithm for II-graphs

This thesis studies an extension of both interval and permutation graphs known as II-graphs (Interval-Interval or trapezoidal graphs). Given two parallel horizontal lines with n intervals on each line, for any interval of the top line there is exactly one trapezoid joining it with an interval of the lower line. Each such trapezoid corresponds to a vertex of the II-graph, where two vertices are adjacent if and only if their corresponding trapezoids intersect. It is known that II-graphs exhibit many interesting properties such as being weakly chordal, co-comparability and asteroidal-triple free. Their complements are transitively orientable with an interval order of dimension two. This thesis presents an $O(n\sp3$) algorithm for solving the II-graph recognition problem. Using an operation for splitting a vertex into two (called the Vertex Splitting Operation), our recognition algorithm will transform a given graph into a permutation graph with some special properties if and only if the given graph is an II-graph. Unlike other II-graph recognition algorithms, our algorithm will also construct an II-representation. We will also show that the Vertex Splitting Operation exhibits various interesting properties when applied to other families of graphs, including perfect graphs, chordal graphs and interval graphs.