Grid spanners
Arthur L. Liestman, Thomas Caton Shermer · Networks · 1993
Abstract A t‐spanner of a network is a subnetwork in which every two nodes that were connected by an edge in the original network are connected by a path of at most t edges in the subnetwork. We present t‐spanners with small maximum or average degree for multidimensional grids. We show how to construct small maximum degree 3‐spanners for d‐dimensional grids for d © 2 and constant average degree 3‐spanners for d‐dimensional grids. We also present t‐spanners of minimum average degree for 2‐dimensional grids. © 1993 by John Wiley & Sons, Inc.