Small sets supporting fary embeddings of planar graphs
Hubert de Fraysseix, János Pach, Richard M. Pollack · 1988
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 2n - 4 by n - 2 grid and provide an Ο(n) space, Ο(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 - ο(1)) √n which settles a problem of Mohar.