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 Fary embedding (i.e., straight-line embedding) on the 2n-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 Fary embedding of every planar graph of size n, has cardinality at least n+(1-o(1)) square-root n which settles a problem of Mohar.