Small sets supporting fary embeddings of planar graphs

Publisher Website
Google Scholar
Abstract
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 &Ogr;(n) space, &Ogr;(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 - &ogr;(1)) √n which settles a problem of Mohar.

This publication has 0 references indexed in Scilit: