Area-efficient planar straight-line drawings of outerplanar graphs (Q885284)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Area-efficient planar straight-line drawings of outerplanar graphs |
scientific article |
Statements
Area-efficient planar straight-line drawings of outerplanar graphs (English)
0 references
8 June 2007
0 references
An outerplanar graph \(G\) with \(n\) vertices and maximal degree \(d\) admits a planar straight-line grid drawing with area \(\mathbf O(dn^{1.48})\) in \(\mathbf O(n)\) time. In case \(d=\mathbf o(n^{0.52})\), \(G\) can be drawn this way in \(\mathbf o(n^2)\) area.
0 references
outerplanar
0 references
straight-line drawing
0 references
area-efficient
0 references
