Presented by: 
Olli Pottonen, UQ
Tue 19 Nov, 3:00 pm - 4:00 pm
Room 213, Building 05
Given a graph G = (V, E), a subset L of V is a resolving set if the distances from L uniquely identify all vertices. Formally, for any v, w in V, there is z in L such that d(z, v) ≠ d(z, w). The metric dimension of G is the size of minimal set L.
Metric dimension is known to be NP-hard. Our results show that it is NP-hard on planar graphs but polynomial-time solvable on outer planar graphs.
Joint work with Josep Diaz, Maria Serna and Erik Jan van Leeuwen