Track Planarity Testing and Embedding


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.

Peter van Emde Boas, Jaroslav Pokorný, Mariá Bieliková, Július Štuller, Proc. International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2004, 2:3–17, MatFyzPress