Lecture Notes in ComputerScience 7579, Springer Verlag (2012), 166-174.
Compact grid representation of graphs
by José Cáceres, Carmen Cortés, Clara Isabel Grima, Masahiro Hachimori, Alberto Márquez,
Raiji Mukae, Atsuhiro Nakamoto, Seiya Negami, Rafael Robles, Jesús Valenzuela
Abstract
A graph G is said to be grid locatable if it admits a representation such that vertices are
mapped to grid points and edges to line segments that avoid grid points but the extremes.
Additionally G is said to be properly embeddable in the grid if it is grid locatable and the
segments representing edges do not cross each other. We study the area needed to obtain those
representations for some graph families.