On Spanners of Geometric Graphs

DOI10.1007/11785293_36MaRDI QIDQ5757901zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(19)

• Minimum weight Euclidean t-spanner is NP-hard
• A lower bound for computing geometric spanners
• Spanners of Complete k-Partite Geometric Graphs
• Geodesic spanners on polyhedral surfaces
• Spanning triangulations in graphs
• scientific article; zbMATH DE number 2014449 (Why is no real title available?)
• 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
• Spanners for geodesic graphs and visibility graphs
• Geometric Spanners for Points Inside a Polygonal Domain

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)