Drawing K-2,n: A lower bound
We give a tradeoff theorem between the area and the aspect ratio required by any planar straight-line drawing of K-2,K-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 O(1) then the area must be Omega(n(2)/log(2) n). (C) 2002 Elsevier Science B.V. All rights reserved.
aspect ratio computational geometry graph drawing planar embeddings