Small Sets Supporting Fáry Embeddings of Planar Graphs

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 Ο( 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.

Authors

• Hubert de Fraysseix
• János Pach
• Richard Pollack

Keywords

No keywords are indexed for this paper.