Complexity of metric dimension on planar graphs

DOI10.1016/j.jcss.2016.06.006zbMath1350.68119OpenAlexW2460825048MaRDI QIDQ314819

Olli Pottonen, Josep Diaz, Erik Jan van Leeuwen, Maria J. Serna

Publication date: 16 September 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2016.06.006

zbMATH Keywords

NP-completenessplanar graphmetric dimensionouterplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications ⋮ Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters ⋮ On finding the best and worst orientations for the metric dimension ⋮ On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results ⋮ Computing a metric basis of a 2-connected bipartite distance-hereditary graph ⋮ Sequential metric dimension ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ Metric dimension parameterized by treewidth ⋮ Metric dimension of maximal outerplanar graphs ⋮ Computing a metric basis of a bipartite distance-hereditary graph ⋮ Local metric dimension for graphs with small clique numbers ⋮ Hardness of metric dimension in graphs of constant treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation complexity of metric dimension problem
• The (weighted) metric dimension of graphs: hard and easy cases
• Resolvability in graphs and the metric dimension of a graph
• Locating a robber on a graph via distance queries
• Computing the metric dimension for chain graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Landmarks in graphs
• Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs
• Metric Dimension of Bounded Width Graphs
• Base size, metric dimension and other invariants of groups and graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Efficient Planarity Testing
• Approximation algorithms for NP-complete problems on planar graphs
• The Complexity of Multiterminal Cuts
• Notions of Metric Dimension of Corona Products: Combinatorial and Computational Results

This page was built for publication: Complexity of metric dimension on planar graphs