Proper and Planar Drawings of Graphs on Three Layers

Suderman, Matthew (2006) Proper and Planar Drawings of Graphs on Three Layers. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 434-445(Official URL:

Full text not available from this repository.


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.

Item Type: Conference Paper
Additional Information: 10.1007/11618058_39
Classifications: M Methods > M.600 Planar
P Styles > P.720 Straight-line
P Styles > P.540 Planar
M Methods > M.500 Layered
P Styles > P.480 Layered

Actions (login required)

View Item View Item