LAUSR

In this paper, we study the metric dimension problem in maximal outerplanar graphs. Concretely, if $$\beta (G)$$ β ( G ) denotes the metric dimension of a maximal outerplanar graph G of order n , we prove that $$2\le \beta (G) \le \lceil \frac{2n}{5}\rceil $$ 2 ≤ β ( G ) ≤ ⌈ 2 n 5 ⌉ and that the bounds are tight. We also provide linear algorithms to decide whether the metric dimension of G is 2 and to build a resolving set S of size $$\lceil \frac{2n}{5}\rceil $$ ⌈ 2 n 5 ⌉ for G . Moreover, we characterize all maximal outerplanar graphs with metric dimension 2.