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, Limerick, Ireland , 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
ID Code:709

Repository Staff Only: item control page


Arnborg, S., Proskurowski, A.: Characterization and recognition of partial 3-trees. SIAM Journal of Algebraic and Discrete Methods 7 (1986) 305-314

Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999)

Cornelsen, S., Schank, T., Wagner, D.: Drawing graphs on two and three lines. Goodrich, M., Kobourov, S., eds.: Graph Drawing, 10th International Symposium (GD 2002). Volume 2528 of Lecture Notes in Computer Science., Springer-Verlag (2002) 31-41

Dujmovic, V., Fellows, M.R., Hallett, M.T., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F.A., Suderman, M., Whitesides, S., Wood, D.R.: On the parameterized complexity of layered graph drawing. In auf der Heide, F.M., ed.: Algorithms, 9th European Symposium (ESA 2001). Volume 2161 of Lecture Notes in Computer Science., Springer-Verlag (2001) 488-499

Eades, P., McKay, B., Wormald, N.: On an edge crossing problem. In: Proceedings of the 9th Australian Computer Science Conference, Australian National University (1986) 327-334

Fößmeier, U., Kaufmann, M.: Nice drawings for planar bipartite graphs. In Bongiovanni, G.C., Bovet, D.P., Battista, G.D., eds.: Proceedings of the 3rd Italian Conference on Algorithms and Complexity (CIAC 1997). Volume 1203 of Lecture Notes in Computer Science., Springer-Verlag (1997) 122-134

Harary, F., Schwenk, A.: A new crossing number for bipartite graphs. Utilitas Mathematica 1 (1972) 203-209

Heath, L.S., Rosenberg, A.L.: Laying out graphs using queues. SIAM Journal on Computing 21 (1992) 927-958

Kaufmann, M., Wagner, D.: Drawing Graphs: Methods and Models. Volume 2025 of Lecture Notes in Computer Science. Springer-Verlag (2001)

Lengauer, T.: Combinatorial Algorithms for Integrated Circuit Layout. Wiley (1990)

Matousek, J., Thomas, R.: Algorithms finding tree-decompositions of graphs. Journal of Algorithms 12 (1991) 1-22

Sanders, D.P.: On linear recognition of tree-width at most four. SIAM Journal on Discrete Mathematics 9 (1995) 101-117

Suderman, M.: Pathwidth and layered drawings of trees. International Journal of Computational Geometry & Applications 14 (2004) 203-225

Tarjan, R.: Depth-first search and linear graph algorithms. SIAM Journal on Computing 1 (1972) 146-160

Tomii, N., Kambayashi, Y., Yajima, S.: On planarization algorithms of 2-level graphs. Technical Report EC77-38, Institute of Electronic and Communication Engineers of Japan (IECEJ) (1977)

Warfield, J.N.: Crossing theory and hierarchy mapping. IEEE Transactions on Systems, Man, and Cybernetics 7 (1977) 502-523

Waterman, M.S., Griggs, J.R.: Interval graphs and maps of DNA. Bulletin of Mathematical Biology 48 (1986) 189-195