{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:33:12Z","timestamp":1759847592781},"reference-count":16,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2004,6]]},"abstract":"<jats:p>An h-layer drawing of a graph G is a planar drawing of G in which each vertex is placed on one of h parallel lines and each edge is drawn as a straight line between its end-vertices. In such a drawing, we say that an edge is proper if its endpoints lie on adjacent layers, flat if they lie on the same layer and long otherwise. Thus, a proper h-layer drawing contains only proper edges, a short h-layer drawing contains no long edges, an upright h-layer drawing contains no flat edges, and an unconstrained h-layer drawing contains any type of edge. In this paper, we derive upper and lower bounds on the number of layers required by proper, short, upright, and unconstrained layered drawings of trees. We prove that these bounds are optimal with respect to the pathwidth of the tree being drawn. Finally, we give linear-time algorithms for obtaining layered drawings that match these upper bounds.<\/jats:p>","DOI":"10.1142\/s0218195904001433","type":"journal-article","created":{"date-parts":[[2004,8,30]],"date-time":"2004-08-30T11:36:17Z","timestamp":1093865777000},"page":"203-225","source":"Crossref","is-referenced-by-count":27,"title":["PATHWIDTH AND LAYERED DRAWINGS OF TREES"],"prefix":"10.1142","volume":"14","author":[{"given":"MATTHEW","family":"SUDERMAN","sequence":"first","affiliation":[{"name":"School of Computer Science, McGill University, 3480 University Street, McConnell Engineering Building, Room 318, Montr\u00e9al, Qu\u00e9bec, H3A 2A7, Canada"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"Di Battista G.","year":"1999"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1980.4308390"},{"key":"rf3","volume-title":"Drawing graphs on two and three lines in Graph Drawing, 10th Int. Symp. (GD 2002)","author":"Cornelsen S.","year":"2002"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44676-1_41"},{"key":"rf6","unstructured":"P.\u00a0Eades, B.\u00a0McKay and N.\u00a0Wormald, Proc. of the 9th Australian Computer Science Conf. (Australian National University, 1986)\u00a0pp. 327\u2013334."},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1064"},{"key":"rf8","doi-asserted-by":"crossref","unstructured":"S.\u00a0Felsner, G.\u00a0Liotta and S. K.\u00a0Wismath, Graph Drawing, 9th Int. Symp. (GD 200l), Lecture Notes in Computer Science\u00a02265, eds. P.\u00a0Mutzel, M.\u00a0J\u00fcnger and S.\u00a0Leipert (Springer-Verlag, 2001)\u00a0pp. 328\u2013342.","DOI":"10.1007\/3-540-45848-4_26"},{"key":"rf10","unstructured":"U.\u00a0F\u00f6\u00dfmeier and M.\u00a0Kaufmann, Graph Drawing, 5th Int. Symp. (GD'97), Lecture Notes in Computer Science\u00a01353, ed. G.\u00a0Di Battista (Springer-Verlag, 1997)\u00a0pp. 134\u2013145."},{"key":"rf11","first-page":"203","volume":"1","author":"Harary F.","journal-title":"Utilitas Mathematics"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44969-8"},{"key":"rf13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatotial Algorithms for Integrated Circuit Layout","author":"Lengauer T.","year":"1990"},{"key":"rf14","unstructured":"P.\u00a0Mutzel, Encyclopedia of Optimization, eds. P. M.\u00a0Pardalos and C. A.\u00a0Floudas (Kluwer Academic Publishers, 2001)\u00a0pp. 189\u2013196."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-46908-4_70"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1981.4308636"},{"key":"rf17","first-page":"502","volume":"7","author":"Warfield J. N.","journal-title":"IEEE Trans. Syst., Man Cybern."},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/BF02460022"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195904001433","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,29]],"date-time":"2023-04-29T07:47:08Z","timestamp":1682754428000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195904001433"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6]]},"references-count":16,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,1,25]]},"published-print":{"date-parts":[[2004,6]]}},"alternative-id":["10.1142\/S0218195904001433"],"URL":"https:\/\/doi.org\/10.1142\/s0218195904001433","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,6]]}}}