AIB 2009-16: Vertex Splitting and the Recognition of Trapezoid Graphs

[Carsten Fuhs]

The following technical report is available from
http://aib.informatik.rwth-aachen.de:

Vertex Splitting and the Recognition of Trapezoid Graphs
George B. Mertzios, Derek G. Corneil
AIB 2009-16

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}.