Upright Drawings of Planar Graphs on Three Layers

Abstract. An upright drawing of a planar graph G on k layers is a planar straight-line drawing of G, where each vertex of G is placed on a set of k horizontal lines, called layers and no two adjacent vertices are placed on the same layer. In this paper, we give a linear-time algorithm to check whether or not a given planar graph G admits an upright drawing on three layers and if so, to obtain such a drawing of G. To the best of our knowledge, this is the first algorithm for upright drawings of planar graphs on k layers for k> 2.