Track Planarity Testing and Embedding

Abstract

A track graph is a graph with its vertex set partitioned into horizontal levels. It is track planar if there are permutations of the vertices on each level such that all edges can be drawn as weak monotone curves without crossings. The novelty and generalisation over level planar graphs is that horizontal edges connecting consecutive vertices on the same level are allowed. We show that track planarity can be reduced to level planarity in linear time. Hence, there are O(|V|) time algorithms for the track planarity test and for the computation of a track planar embedding.