Functional pearls: Deriving tidy drawings of trees
The tree-drawing problem is to produce a 'tidy' mapping from 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 a...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
1996
|
| _version_ | 1826279624622997504 |
|---|---|
| author | Gibbons, J |
| author_facet | Gibbons, J |
| author_sort | Gibbons, J |
| collection | OXFORD |
| description | The tree-drawing problem is to produce a 'tidy' mapping from 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 criteria satisfied by tidy drawings. The derivation shows constructively that these criteria completely determine the drawing. Indeed, the criteria completely determine a simple but inefficient algorithm for drawing a tree, which can be transformed into an efficient algorithm using just standard techniques and a small number of inventive steps. The algorithm consists of an upwards accumulation followed by a downwards accumulation on the tree, and is further evidence of the utility of these two higher-order tree operations. |
| first_indexed | 2024-03-07T00:01:33Z |
| format | Journal article |
| id | oxford-uuid:7620a383-1a33-47b2-9b38-982598a8f015 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:01:33Z |
| publishDate | 1996 |
| record_format | dspace |
| spelling | oxford-uuid:7620a383-1a33-47b2-9b38-982598a8f0152022-03-26T20:13:38ZFunctional pearls: Deriving tidy drawings of treesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7620a383-1a33-47b2-9b38-982598a8f015EnglishSymplectic Elements at Oxford1996Gibbons, JThe tree-drawing problem is to produce a 'tidy' mapping from 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 criteria satisfied by tidy drawings. The derivation shows constructively that these criteria completely determine the drawing. Indeed, the criteria completely determine a simple but inefficient algorithm for drawing a tree, which can be transformed into an efficient algorithm using just standard techniques and a small number of inventive steps. The algorithm consists of an upwards accumulation followed by a downwards accumulation on the tree, and is further evidence of the utility of these two higher-order tree operations. |
| spellingShingle | Gibbons, J Functional pearls: Deriving tidy drawings of trees |
| title | Functional pearls: Deriving tidy drawings of trees |
| title_full | Functional pearls: Deriving tidy drawings of trees |
| title_fullStr | Functional pearls: Deriving tidy drawings of trees |
| title_full_unstemmed | Functional pearls: Deriving tidy drawings of trees |
| title_short | Functional pearls: Deriving tidy drawings of trees |
| title_sort | functional pearls deriving tidy drawings of trees |
| work_keys_str_mv | AT gibbonsj functionalpearlsderivingtidydrawingsoftrees |