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.
References
Status
- Solved: Hubert de Fraysseix, János Pach, and Richard Pollack. How to draw a planar graph on a grid (Combinatorica, 1990) https://link.springer.com/article/10.1007/BF02122694
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.