## Abstract

We make progress on a number of open problems concerning the area requirement for drawing trees on a grid. We prove that (1) every tree of size n (with arbitrarily large degree) has a straight-line drawing with area n2O(loglognlogloglogn), improving the longstanding O(nlog n) bound; (2) every tree of size n (with arbitrarily large degree) has a straight-line upward drawing with area nlogn(loglogn)O(1), improving the longstanding O(nlog n) bound; (3) every binary tree of size n has a straight-line orthogonal drawing with area n2O(log∗n), improving the previous O(nlog log n) bound; (4) every binary tree of size n has a straight-line order-preserving drawing with area n2O(log∗n), improving the previous O(nlog log n) bound; (5) every binary tree of size n has a straight-line orthogonal order-preserving drawing with area n2O(logn), improving the previous O(n^{3 / 2}) bound.

Original language | English (US) |
---|---|

Pages (from-to) | 799-820 |

Number of pages | 22 |

Journal | Discrete and Computational Geometry |

Volume | 63 |

Issue number | 4 |

DOIs | |

State | Published - Jun 1 2020 |

## Keywords

- Graph drawing
- Recursion
- Trees

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics