Dilation-free graphs in the l1 metric

Abstract

The dilation-free graph of a planar point set S is a graph that spans S in such a way that the distance between two points in the graph is no longer than their planar distance. Metrically speaking, those graphs are equivalent to complete graphs; however they have far fewer edges when considering the Manhattan distance (we give here an upper bound on the number of saved edges). This article provides several theoretical, algorithmic, and complexity features of dilation-free graphs in the l1-metric, giving several construction algorithms and proving some of their properties. Moreover, special attention is paid to the planar case due to its applications in the design of printed circuit boards.