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
    0 references
    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
    0 references
    outerplanar
    0 references
    straight-line drawing
    0 references
    area-efficient
    0 references
    0 references