Vertex Splitting and the Recognition of Trapezoid Graphs
George B. Mertzios, Derek G. Corneil
Trapezoid graphs are the intersection family of trapezoids where every
trapezoid has a pair of opposite sides lying on two parallel lines.
These graphs have received considerable attention and lie strictly between
permutation graphs (where the trapezoids are lines) and cocomparability
graphs (the complement has a transitive orientation). The operation of
``vertex splitting'', introduced in~\cite{CC}, first augments a given
graph $G$ and then transforms the augmented graph by replacing each of
the original graph's vertices by a pair of new vertices. This ``splitted
graph'' is a permutation graph with special properties if and only if $G$
is a trapezoid graph. Recently vertex splitting has been used to show
that the recognition problems for both tolerance and bounded tolerance
graphs is NP-complete~\cite{MSZ2}. Unfortunately, the vertex splitting
trapezoid graph recognition algorithm presented in~\cite{CC} is not
correct. In this paper, we present a new way of augmenting the given
graph and using vertex splitting such that the resulting algorithm is
simpler and faster than the one reported in~\cite{CC}.