How to draw a planar graph on a grid.

Answering a question of Rosenstiehl and Tarjan, we show that every plane graph with n vertices has a Fáry embedding (i.e., straight-line embedding) on the 2 n−4 by n−2 grid and provide an O(n) space, O( n log n) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any set F, which can support a Fáry embedding of every planar graph of size n, has cardinality at least n+(1− o(1))√ n which settles a problem of Mohar. [ABSTRACT FROM AUTHOR]