Skip to main content

How to Derive Tidy Drawings of Trees

Jeremy Gibbons

Abstract

The \em tree-drawing problem\/ is to produce a `tidy' mapping of elements of a tree to points in the plane. In this paper, we derive an efficient algorithm for producing tidy drawings of trees. The specification, the starting point for the derivations, consists of a collection of intuitively appealing \em criteria\/ satisfied by tidy drawings. The derivation shows constructively that these criteria completely determine the drawing. Indeed, there is essentially only one reasonable drawing algorithm satisfying the criteria; its development is almost mechanical. \par The algorithm consists of an \em upwards accumulation\/ followed by a \em downwards accumulation\/ on the tree, and is further evidence of the utility of these two higher-order tree operations.

Address
Department of Computer Science‚ University of Auckland
Annote
Condensed version of Gibbons93:Deriving
Book Title
Proceedings of Salodays in Auckland
Editor
C. Calude and M. J. J. Lennon and H. Maurer
Note
Also in Proceedings of First New Zealand Formal Program Development Colloquium‚ 105–126p‥
Pages
53–73
Year
1994