{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T15:24:38Z","timestamp":1779895478661,"version":"3.53.1"},"reference-count":14,"publisher":"Wiley","issue":"7","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":5965,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1990,7]]},"abstract":"Abstract<\/jats:title>Drawing a tree consists of two stages: determining the position of each node, and actually rendering the individuals nodes and interconnecting branches. The algorithm described in this paper is concerned with the first stage: given a list of nodes, an indication of the hierarchical relationship among them, and their shape and size, where should each node be positioned for optimal aesthetic effect?<\/jats:p>This algorithm determines the positions of the nodes for any arbitrary general tree. It is the most desirable positioning with respect to certain widely\u2010accepted heuristics. The positioning, specified in x, y co\u2010ordinates, minimizes the width of the tree. In a general tree, there is no limit on the number of offspring per node; this contrasts with binary and ternary trees, for example, which are trees with a limit of two and three offspring per node. This algorithm operates in time O(N), where N is the number of nodes in the tree.<\/jats:p>Previously, most tree drawings have been positioned by the sure hand of a human graphic designer. Many computer\u2010generated positionings have been either trivial or contained irregularities. Earlier work by Wetherell and Shannon1<\/jats:sup> and Tilford,2<\/jats:sup> upon which this algorithm builds, failed to position the interior nodes of some trees correctly. The algorithm presented here correctly positions a tree's node using only two passes. It also handles several practical considerations: alternative orientations of the tree, variable node sizes and out\u2010of\u2010bounds conditions. Radack,3<\/jats:sup> also building on Tilford's work, has solved this same problem with a different algorithm which makes four passes.<\/jats:p>","DOI":"10.1002\/spe.4380200705","type":"journal-article","created":{"date-parts":[[2006,11,18]],"date-time":"2006-11-18T00:44:26Z","timestamp":1163810666000},"page":"685-705","source":"Crossref","is-referenced-by-count":87,"title":["A node\u2010positioning algorithm for general trees"],"prefix":"10.1002","volume":"20","author":[{"suffix":"II","given":"John Q.","family":"Walker","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1979.234212"},{"key":"e_1_2_1_3_2","unstructured":"J. S.Tilford \u2018Tree drawing algorithms\u2019 M.S. Thesis Department of Computer Science University of Illinois Urbana IL Report UIUCDCS\u2010R\u201081\u20101055 April 1981. Available as Document UILU\u2010ENG\u201081\u20101711 from the College of Engineering Document Center at the University of Illinois."},{"key":"e_1_2_1_4_2","volume-title":"Report CES\u201088\u201024, Department of Computer Engineering and Science","author":"Radack G. M.","year":"1988"},{"key":"e_1_2_1_5_2","unstructured":"R. E.Sweet \u2018Empirical estimates of program entropy\u2019 Report STAN\u2010CS\u201078\u2010698 Department of Computer Science Stanford University Stanford CA November 1978. Also issued as Report CSL\u201078\u20103 Xerox PARC Palo Alto CA September1978."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289576"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1981.234519"},{"key":"e_1_2_1_8_2","volume-title":"The Art of Computer Programming, Volume 1: Fundamental Algorithms","author":"Knuth D. E.","year":"1973"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264289"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380100706"},{"key":"e_1_2_1_11_2","volume-title":"Algorithms + Data Structures = Programs","author":"Wirth N.","year":"1976"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1985.1662718"},{"key":"e_1_2_1_13_2","unstructured":"A. A.Poggio personal communication 21 October1985."},{"issue":"22","key":"e_1_2_1_14_2","first-page":"199","article-title":"\u2018A sight better than TREE\u2019","volume":"4","author":"Petzold C.","year":"1985","journal-title":"PC Magazine"},{"key":"e_1_2_1_15_2","first-page":"159","article-title":"\u2018Fast detection and display of symmetry in trees\u2019","volume":"64","author":"Manning J. B.","year":"1988","journal-title":"Congressus Numerantium"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380200705","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380200705","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T10:26:58Z","timestamp":1697970418000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380200705"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,7]]},"references-count":14,"journal-issue":{"issue":"7","published-print":{"date-parts":[[1990,7]]}},"alternative-id":["10.1002\/spe.4380200705"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380200705","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,7]]}}}