Drawing K2,n: A Lower Bound

[.ps] [.pdf]


We give a tradeoff theorem between the area and the aspect ratio required by any planar straight-line drawing of K2,n on the integer lattice. In particular we show that if the drawing is contained in a rectangle of area O(n) then the rectangle must have aspect ratio Omega(n), and conversely, if the aspect ratio is 1 then the area must be Omega(n2/log2 n).

Bibtex Entry