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.
Details
| 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 |
Links
Related pages
|
People |
|
|
Activities |