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 uv, 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. 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 (?n/2?-1)×(?34?-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.