How to draw a planar graph on a grid (Q804582): Difference between revisions

The authors show that every plane graph with n vertices has a straight- line embedding on the 2n-4 by n-2 grid, and provide an O(n) space, O(n.log n) time algorithm for finding the embedding. On the other hand, they prove that any set F, which can support a straight-line embedding of every planar graph of size n, has cardinality at least \(n+(1- o(1))\sqrt{n}\). This settles a problem of B. Mohar.