Polynomial-size grid drawing problem for planar graphs

Let GG be an arbitrary planar graph. A proper grid drawing of GG is a drawing in which vertices are represented by grid points and edges by noncrossing straight-line segments, with no grid point representing a vertex lying in the interior of an edge. Is there a proper grid drawing of GG in a grid of polynomial size?

Polynomial-size grid drawing problem. For every planar graph GG, there is a proper grid drawing of GG in a grid of polynomial size.

The paper presents this as an open question because polynomial-size proper grid drawings are known for bounded-degree planar graphs, while the general case remains unresolved.

Sources & referencesView supporting material

Primary source

Martin Balko, “Grid Representations and the Chromatic Number”, arXiv:1204.0210 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.