Minimum-layer drawings of trees (extended abstract). (English) Zbl 1317.68136

Katoh, Naoki (ed.) et al., WALCOM: Algorithms and computation. 5th international workshop, WALCOM 2011, New Delhi, India, February 18–20, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-19093-3/pbk). Lecture Notes in Computer Science 6552, 221-232 (2011).
Summary: A layered drawing of a tree \(T\) is a planar straight-line drawing of \(T\), where the vertices of \(T\) are placed on some horizontal lines called layers. A minimum-layer drawing of \(T\) is a layered drawing of \(T\) on \(k\) layers, where \(k\) is the minimum number of layers required for any layered drawing of \(T\). In this paper we give a linear-time algorithm for obtaining minimum-layer drawings of trees.
For the entire collection see [Zbl 1206.68014].


68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI


[1] Alam, M.J.: Minimum-layer drawings of trees. M. Sc. Engg. thesis, Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (2010) · Zbl 1213.05033
[2] Alam, M.J., Samee, M.A.H., Rabbi, M.M., Rahman, M.S.: Minimum-layer upward drawings of trees. Journal of Graph Algorithms and Applications 14(2), 245–267 (2010) · Zbl 1213.05033
[3] Cornelsen, S., Schank, T., Wagner, D.: Drawing graphs on two and three lines. Journal of Graph Algorithms and Applications 8(2), 161–177 (2004) · Zbl 1087.05040
[4] Dujmović, 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: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 488–499. Springer, Heidelberg (2001) · Zbl 1006.68544
[5] Felsner, S., Liotta, G., Wismath, S.K.: Straight-line drawings on restricted integer grids in two and three dimensions. Journal of Graph Algorithms and Applications 7(4), 363–398 (2003) · Zbl 1068.68103
[6] Hayashi, K., Masuda, S.: Complexity results on the minimum width drawing problem for rooted unordered trees. Electronics and Communications in Japan (Part III: Fundamental Electronic Science) 81(1), 32–41 (1998)
[7] Marriott, K., Stuckey, P.J.: NP-completeness of minimal width unordered tree layout. Journal of Graph Algorithms and Applications 8(2), 295–312 (2004) · Zbl 1088.68070
[8] Nishizeki, T., Rahman, M.S.: Planar Graph Drawing. World Scientific, Singapore (2004) · Zbl 1070.68124
[9] Suderman, M.: Pathwidth and layered drawings of trees. International Journal of Computational Geometry and Applications 14(3), 203–225 (2004) · Zbl 1080.68087
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.