Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications

Abstract

The metric dimension of a graph is the smallest number of nodes required to identify all other nodes uniquely based on shortest path distances. Applications of metric dimension include discovering the source of a spread in a network, canonically labeling graphs, and embedding symbolic data in low-dimensional Euclidean spaces. This survey gives a self-contained introduction to metric dimension and an overview of the quintessential results and applications. We discuss methods for approximating the metric dimension of general graphs, and specific bounds and asymptotic behavior for deterministic and random families of graphs. We conclude with related concepts and directions for future work.