{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:22:13Z","timestamp":1787498533976,"version":"build-2736575974"},"reference-count":0,"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":[[1996,9]]},"abstract":"<jats:p>Rooted trees are usually drawn planar and upward, i.e., without crossings and with-out any parent placed below its child. In this paper we investigate the area requirement of planar upward drawings of rooted trees. We give tight upper and lower bounds on the area of various types of drawings, and provide linear-time algorithms for constructing optimal area drawings. Let T be a bounded-degree rooted tree with N nodes. Our results are summarized as follows:<\/jats:p>\n                  <jats:p>\n                    \u2022 We show that T admits a planar polyline upward grid drawing with area O(N), and with width O(N\n                    <jats:sup>\u03b1<\/jats:sup>\n                    ) for any prespecified constant a such that 0&lt;\u03b1&lt;1.\n                  <\/jats:p>\n                  <jats:p>\u2022 If T is a binary tree, we show that T admits a planar orthogonal upward grid drawing with area O (N log log N).<\/jats:p>\n                  <jats:p>\u2022 We show that if T is ordered, it admits an O(N log N)-area planar upward grid drawing that preserves the left-to-right ordering of the children of each node.<\/jats:p>\n                  <jats:p>\u2022 We show that all of the above area bounds are asymptotically optimal in the worst case.<\/jats:p>\n                  <jats:p>\u2022 We present O(N)-time algorithms for constructing each of the above types of drawings of T with asymptotically optimal area.<\/jats:p>\n                  <jats:p>\u2022 We report on the experimentation of our algorithm for constructing planar polyline upward grid drawings, performed on trees with up to 24 million nodes.<\/jats:p>","DOI":"10.1142\/s0218195996000228","type":"journal-article","created":{"date-parts":[[2004,9,6]],"date-time":"2004-09-06T07:50:09Z","timestamp":1094457009000},"page":"333-356","source":"Crossref","is-referenced-by-count":37,"title":["PLANAR UPWARD TREE DRAWINGS WITH OPTIMAL AREA"],"prefix":"10.1142","volume":"06","author":[{"given":"ASHIM","family":"GARG","sequence":"first","affiliation":[{"name":"Dept. of Computer Science, Brown University, Providence, RI, USA 02912\u20131910, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"MICHAEL T.","family":"GOODRICH","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, The Johns Hopkins University, Baltimore, MD, USA 21218\u20132694, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"ROBERTO","family":"TAMASSIA","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, Brown University, Providence, RI, USA 02912\u20131910, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195996000228","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:37:42Z","timestamp":1565177862000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195996000228"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1996,9]]}},"alternative-id":["10.1142\/S0218195996000228"],"URL":"https:\/\/doi.org\/10.1142\/s0218195996000228","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}