{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T00:32:19Z","timestamp":1728174739924},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1993,6]]},"abstract":"<jats:p> Rooted trees abound in computing and it is often necessary to draw them for visualization and documentation purposes. In the classical convention for tree drawing, the tree is drawn in a \u201clevel\u201d fashion, with nodes (represented by boxes) at depth k lying on a horizontal line at a distance of k units below the root. The parent \u2014 child relationships are represented by lines between the boxes. Several algorithms have been developed for constructing a compact layout of a tree in the classical convention. <\/jats:p><jats:p> In this paper we investigate algorithms for drawing trees according to two new conventions. In the inclusion convention, nodes are represented by boxes, and the parent \u2014 child relationship is represented by inclusion of one box in another. The tip-over convention again represents nodes as boxes, and, like the classical convention, represents the parent \u2014 child relationship by lines between the boxes; however, we allow siblings to be arranged vertically rather than horizontally. <\/jats:p><jats:p> For many of the cases which arise in visualization of trees (for example, binary trees with textual information at the leaves) we present polynomial time algorithms. However, the general problem of finding minimum size layouts for either of the new conventions is shown to be NP-hard. <\/jats:p>","DOI":"10.1142\/s0218195993000099","type":"journal-article","created":{"date-parts":[[2004,11,23]],"date-time":"2004-11-23T03:29:30Z","timestamp":1101180570000},"page":"133-153","source":"Crossref","is-referenced-by-count":21,"title":["TWO TREE DRAWING CONVENTIONS"],"prefix":"10.1142","volume":"03","author":[{"given":"PETER","family":"EADES","sequence":"first","affiliation":[{"name":"Geometric Algorithms Laboratory, Department of Computer Science, The University of Newcastle, NSW 2308, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TAO","family":"LIN","sequence":"additional","affiliation":[{"name":"Geometric Algorithms Laboratory, Department of Computer Science, The University of Newcastle, NSW 2308, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"XUEMIN","family":"LIN","sequence":"additional","affiliation":[{"name":"Geometric Algorithms Laboratory, Department of Computer Science, The University of Newcastle, NSW 2308, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"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\/S0218195993000099","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T23:57:41Z","timestamp":1565135861000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195993000099"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1993,6]]}},"alternative-id":["10.1142\/S0218195993000099"],"URL":"https:\/\/doi.org\/10.1142\/s0218195993000099","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,6]]}}}