Convex grid embeddings of 3-connected planar graphs
Luís Fernando Schultz Xavier da Silveira
University of Ottawa
We show an improvement on a result of Schnyder by Felsner which allows us to embed any $n$-vertex 3-connected planar graph on an $O(n)$ by $O(n)$ grid in $O(n)$ time in such a way that all the internal faces are drawn in a (non-strictly) convex fashion. The face structure of any input combinatorial embedding can be preserved if so desired. This has uncanny similarities with the non-blocking grid obstacle representation problem.