Complexity of metric dimension on planar graphs

The metric dimension of a graph is the size of a smallest subset such that for any with there is a such that the graph distance between and differs from the graph distance between and . Even though this notion has been part of the literature for almost 40 years, prior to our work the computational complexity of determining the metric dimension of a graph was still very unclear. In this paper, we show tight complexity boundaries for the problem. We achieve this by giving two complementary results. First, we show that the problem on planar graphs of maximum degree 6 is NP-complete. Then, we give a polynomial-time algorithm for determining the metric dimension of outerplanar graphs.