Proper and Planar Drawings of Graphs on Three Layers

A proper k-layer planar graph, for an integer k>=0, is any graph with a planar drawing in which the vertices are drawn on k horizontal lines called layers and each edge is drawn a straight-line segment between end-vertices on adjacent layers. In this paper, we point out errors in an algorithm of Foessmeier and Kaufmann (CIAC, 1997) for recognizing proper 3-layer planar graphs, and then present a new characterization of proper 3-layer planar graphs that is partially based on their algorithm. Using the characterization, we then derive corresponding linear-time algorithms for recognizing and drawing proper 3-layer planar graphs. On the basis of our results, we predict that the approach of Foessmeier and Kaufmann will not easily generalize for drawings on four or more layers and suggest another possible approach along with some of the reasons why it may be more successful