The Vertex-Exchange Graph: a New Mechanism for Multi-Level Crossing Minimisation

and laying out a multi-level graph. We introduce a new abstraction that
we call a vertex-exchange graph. We demonstrate how this concept can be
used to solve these problems by providing clear and simple algorithms
for testing a multi-level graph for planarity and laying out a
multi-level graph when planar. We also show how the concept can be used
for multi-level crossing minimisation and bounding the crossing number
of a multi-level graph.