4-labelings and grid embeddings of plane quadrangulations

A straight-line drawing of a planar graph GG is a closed rectangle-of-influence drawing   if for each edge uvuv, the closed axis-parallel rectangle with opposite corners uu and vv contains no other vertices. We show that each quadrangulation on nn vertices has a closed rectangle-of-influence drawing on the (n−3)×(n−3)(n−3)×(n−3) grid.The algorithm is based on angle labeling and simple face counting in regions. This answers the question of what would be a grid embedding of quadrangulations analogous to Schnyder’s classical algorithm for embedding triangulations and extends previous results on book embeddings for quadrangulations from Felsner, Huemer, Kappes, and Orden.A further compaction step yields a straight-line drawing of a quadrangulation on the (⌈n2⌉−1)×(⌈3n4⌉−1) grid. The advantage over other existing algorithms is that it is not necessary to add edges to the quadrangulation to make it 44-connected.