𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Area requirement of visibility representations of trees

✍ Scribed by Goos Kant; Giuseppe Liotta; Roberto Tamassia; Ioannis G. Tollis

Book ID
104137384
Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
760 KB
Volume
62
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

We study the area requirement of bar-visibility and rectangle-visibility representations of trees in the plane. We prove asymptotically tight lower and upper bounds on the area of such representations, and give linear-time algorithms that construct representations with asymptotically optimal area. @ 1997 Elsevier Science B.V.

πŸ“œ SIMILAR VOLUMES

Rectangular and visibility representatio
Rectangular and visibility representations of infinite planar graphs
✍ Carsten Thomassen πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 75 KB

## Abstract We provide a new method for extending results on finite planar graphs to the infinite case. Thus a result of Ungar on finite graphs has the following extension: Every infinite, planar, cubic, cyclically 4‐edge‐connected graph has a representation in the plane such that every edge is a h

Reducing the space requirement of suffix
Reducing the space requirement of suffix trees
✍ Stefan Kurtz πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 202 KB

We show that suffix trees store various kinds of redundant information. We exploit these redundancies to obtain more space efficient representations. The most space efficient of our representations requires 20 bytes per input character in the worst case, and 10.1 bytes per input character on average