4-Labelings and Grid Embeddings of Plane Quadrangulations

摘要

Finding aesthetic drawings of planar graphs is a main issue in graph drawing.Of special interest are rectangle of influence drawings.The graphs considered here are quadrangulations, that is, planar graphs all whose faces have degree four.We show that each quadrangulation on n vertices has a closed rectangle of influence drawing on the (n - 2) × (n - 2) grid.