4-labelings and grid embeddings of plane quadrangulations

A straight-line drawing of a planar graph G is a closed rectangle-of-influence drawing if for each edge u v , the closed axis-parallel rectangle with opposite corners u and v contains no other vertices. We show that each quadrangulation on n vertices has a closed rectangle-of-influence drawing on the ( n − 3 ) × ( n − 3 ) grid. gorithm 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. her compaction step yields a straight-line drawing of a quadrangulation on the ( ⌈ n 2 ⌉ − 1 ) × ( ⌈ 3 n 4 ⌉ − 1 ) grid. The advantage over other existing algorithms is that it is not necessary to add edges to the quadrangulation to make it 4 -connected.