Complexity of metric dimension on planar graphs

作者：

Highlights：

• In Metric Dimension, we distinguish all pairs of vertices by few selected landmarks.

• We show that Metric Dimension is NP-complete on planar graphs.

• We show that Metric Dimension has a polynomial-time algorithm on outerplanar graphs.

• This closes a 30-year old complexity gap for Metric Dimension.

摘要

•In Metric Dimension, we distinguish all pairs of vertices by few selected landmarks.•We show that Metric Dimension is NP-complete on planar graphs.•We show that Metric Dimension has a polynomial-time algorithm on outerplanar graphs.•This closes a 30-year old complexity gap for Metric Dimension.

论文关键词：Metric dimension,Planar graph,Outerplanar graph,NP-completeness

论文评审过程：Received 12 February 2015, Revised 10 May 2016, Accepted 17 June 2016, Available online 15 July 2016, Version of Record 15 September 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.06.006