Presented by: 
Olli Pottonen, UQ
Date: 
Tue 19 Nov, 3:00 pm - 4:00 pm
Venue: 
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