On Spanners of Geometric Graphs

DOI10.1007/11785293_36zbMATH Open1142.05346OpenAlexW1496182974MaRDI QIDQ5757901FDOQ5757901

Authors: Joachim Gudmundsson, Michiel Smid 

Publication date: 7 September 2007

Published in: Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11785293_36

Recommendations

• ON SPANNERS OF GEOMETRIC GRAPHS
• Minimum weight Euclidean \(t\)-spanner is NP-hard
• scientific article; zbMATH DE number 1375574
• scientific article; zbMATH DE number 1107724
• NP-hardness and fixed-parameter tractability of the minimum spanner problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (19)

• Spanners of Complete k-Partite Geometric Graphs
• Geodesic spanners on polyhedral surfaces
• Minimum weight Euclidean \(t\)-spanner is NP-hard
• A lower bound for computing geometric spanners
• Spanning triangulations in graphs
• Title not available (Why is that?)
• Planar subgraphs without low-degree nodes
• Spanners for geometric intersection graphs with applications
• Geometric spanners with applications in wireless networks
• Spanners of Complete k-Partite Geometric Graphs
• ON SPANNERS OF GEOMETRIC GRAPHS
• Drawing graphs as spanners
• On algorithmic complexity of imprecise spanners
• Routing among convex polygonal obstacles in the plane
• On Pairwise Spanners
• On plane geometric spanners: a survey and open problems
• Spanners for Geometric Intersection Graphs
• Geometric Spanners for Points Inside a Polygonal Domain
• Spanners for geodesic graphs and visibility graphs

This page was built for publication: On Spanners of Geometric Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5757901)