Polynomial-size grid drawing problem for planar graphs
Polynomial-size grid drawing problem for planar graphs
Let be an arbitrary planar graph. A proper grid drawing of 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 in a grid of polynomial size?
Polynomial-size grid drawing problem. For every planar graph , there is a proper grid drawing of 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.