World Scientific
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at customercare@wspc.com for any enquiries.

TWO TREE DRAWING CONVENTIONS

    https://doi.org/10.1142/S0218195993000099Cited by:21 (Source: Crossref)

    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 “level” 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 — 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.

    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 — 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 — child relationship by lines between the boxes; however, we allow siblings to be arranged vertically rather than horizontally.

    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.

    Remember to check out the Most Cited Articles!

    Check out these titles in image analysis!