Geometric Spanner Networks
From MaRDI portal
Publication:3445775
DOI10.1017/CBO9780511546884zbMath1140.68068MaRDI QIDQ3445775
Giri Narasimhan, Michiel H. M. Smid
Publication date: 6 June 2007
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
The Minimum Moving Spanning Tree Problem ⋮ Euclidean Steiner Spanners: Light and Sparse ⋮ YAO GRAPHS SPAN THETA GRAPHS ⋮ Upper and Lower Bounds for Online Routing on Delaunay Triangulations ⋮ EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION ⋮ On the Power of the Semi-Separated Pair Decomposition ⋮ Connect the Dot: Computing Feed-Links with Minimum Dilation ⋮ A GEOMETRIC SPANNER OF SEGMENTS ⋮ DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES ⋮ Truly Optimal Euclidean Spanners ⋮ Computing Minimum Dilation Spanning Trees in Geometric Graphs ⋮ Near isometric terminal embeddings for doubling metrics ⋮ Spanners for Directed Transmission Graphs ⋮ Unnamed Item ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Spanners in randomly weighted graphs: Euclidean case ⋮ Improved routing on the Delaunay triangulation ⋮ On path-greedy geometric spanners ⋮ On algorithmic complexity of imprecise spanners ⋮ Reliable Spanners for Metric Spaces ⋮ New Doubling Spanners: Better and Simpler ⋮ Social distancing network creation ⋮ Generalized sweeping line spanners ⋮ Geometric spanning trees minimizing the Wiener index ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Local routing algorithms on Euclidean spanners with small diameter ⋮ Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition ⋮ Generalized sweeping line spanners ⋮ Unnamed Item ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ Spanners of Additively Weighted Point Sets ⋮ Computing the Greedy Spanner in Near-Quadratic Time ⋮ Online Spanners in Metric Spaces ⋮ Optimal Network Design with End-to-End Service Requirements ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition ⋮ Construction and Local Routing for Angle-Monotone Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fault-Tolerant Spanners in Networks with Symmetric Directional Antennas ⋮ Dilation-Optimal Edge Deletion in Polygonal Cycles ⋮ Testing Euclidean Spanners ⋮ Light Euclidean Spanners with Steiner Points ⋮ Maximum Area Axis-Aligned Square Packings. ⋮ On the expected maximum degree of Gabriel and Yao graphs ⋮ COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD ⋮ Shortest-Path Queries in Geometric Networks ⋮ COMPUTING THE STRETCH FACTOR AND MAXIMUM DETOUR OF PATHS, TREES, AND CYCLES IN THE NORMED SPACE ⋮ A rounding algorithm for approximating minimum Manhattan networks ⋮ Small hop-diameter sparse spanners for doubling metrics ⋮ A simple and efficient kinetic spanner ⋮ The Stretch - Length Tradeoff in Geometric Networks: Average Case and Worst Case Study ⋮ Geodesic Spanners for Points on a Polyhedral Terrain ⋮ A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces ⋮ Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints ⋮ Lattice Spanners of Low Degree ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Vertex fault-tolerant spanners for weighted points in polygonal domains ⋮ Spanners of Complete k-Partite Geometric Graphs ⋮ The Greedy Spanner Is Existentially Optimal ⋮ The Price of Order ⋮ ON SPANNERS OF GEOMETRIC GRAPHS ⋮ The Price of Order ⋮ Improved stretch factor of Delaunay triangulations of points in convex position ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE ⋮ Lattice spanners of low degree ⋮ Covering Metric Spaces by Few Trees ⋮ Approximating Distance Measures for the Skyline ⋮ Temporal Cliques Admit Sparse Spanners ⋮ The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension ⋮ Faster DBSCAN and HDBSCAN in Low-Dimensional Euclidean Spaces ⋮ On the Stretch Factor of Polygonal Chains ⋮ Near Isometric Terminal Embeddings for Doubling Metrics ⋮ Odd Yao-Yao Graphs are Not Spanners ⋮ Faster DBScan and HDBScan in Low-Dimensional Euclidean Spaces ⋮ Optimizing budget allocation for center and median points ⋮ A lower bound for computing geometric spanners ⋮ On approximating tree spanners that are breadth first search trees ⋮ Constrained generalized Delaunay graphs are plane spanners ⋮ \( \delta \)-greedy \(t\)-spanner ⋮ Sparse hop spanners for unit disk graphs ⋮ On the plane angle-monotone graphs ⋮ Linear-size planar Manhattan network for convex point sets ⋮ An improved construction for spanners of disks ⋮ Angle-monotonicity of Delaunay triangulation ⋮ On the spanning and routing ratios of the directed \(\varTheta_6\)-graph ⋮ The minimum moving spanning tree problem ⋮ Routing on heavy-path WSPD-spanners ⋮ Algorithms for graphs of bounded treewidth via orthogonal range searching ⋮ On the dilation spectrum of paths, cycles, and trees ⋮ Local routing in sparse and lightweight geometric graphs ⋮ (Weakly) self-approaching geometric graphs and spanners ⋮ On the spanning and routing ratios of the directed \(\Theta_6\)-graph ⋮ Models and algorithms for network reduction ⋮ Routing among convex polygonal obstacles in the plane ⋮ Linear-size approximations to the Vietoris-Rips filtration ⋮ On plane geometric spanners: a survey and open problems ⋮ Covering metric spaces by few trees ⋮ Routing in polygonal domains ⋮ Spanning properties of Theta-Theta-6 ⋮ Upper and lower bounds for online routing on Delaunay triangulations ⋮ An exact algorithm for the minimum dilation triangulation problem ⋮ Fault-tolerant spanners in networks with symmetric directional antennas ⋮ Fast query structures in anisotropic media ⋮ Theta-3 is connected ⋮ Minimum weight Euclidean \(t\)-spanner is NP-hard ⋮ Fault tolerancy of continuous Yao graph of angle less than \(2\pi/5\) ⋮ Computing the greedy spanner in linear space ⋮ On the stretch factor of Delaunay triangulations of points in convex position ⋮ Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\) ⋮ Tree spanners of bounded degree graphs ⋮ Continuous Yao graphs ⋮ Approximation of minimum weight spanners for sparse graphs ⋮ New constructions of SSPDs and their applications ⋮ Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm ⋮ Minimum rectilinear Steiner tree of \(n\) points in the unit square ⋮ The MST of symmetric disk graphs is light ⋮ Towards tight bounds on theta-graphs: more is not always better ⋮ Connected spatial networks over random points and a route-length statistic ⋮ Near-linear-time deterministic plane Steiner spanners for well-spaced point sets ⋮ Geometric spanners for weighted point sets ⋮ On the power of the semi-separated pair decomposition ⋮ Spanners of additively weighted point sets ⋮ Plane hop spanners for unit disk graphs: simpler and better ⋮ On certain geometric properties of the Yao-Yao graphs ⋮ On the stretch factor of randomly embedded random graphs ⋮ Spanners for geodesic graphs and visibility graphs ⋮ On bounded degree plane strong geometric spanners ⋮ Computing the greedy spanner in near-quadratic time ⋮ Locating battery charging stations to facilitate almost shortest paths ⋮ Bounded-degree spanners in the presence of polygonal obstacle ⋮ Constructing minimum-interference networks ⋮ Sparse geometric graphs with small dilation ⋮ I/O-efficient algorithms for computing planar geometric spanners ⋮ A spanner for the day after ⋮ Geodesic spanners for points in \(\mathbb{R}^3\) amid axis-parallel boxes ⋮ Faster force-directed graph drawing with the well-separated pair decomposition ⋮ On plane constrained bounded-degree spanners ⋮ Routing in unit disk graphs ⋮ Computational complexity of the vertex cover problem in the class of planar triangulations ⋮ Angle-constrained spanners with angle at least \(\pi/3\) ⋮ Space-efficient path-reporting approximate distance oracles ⋮ Approximating the generalized minimum Manhattan network problem ⋮ Geometric spanners with small chromatic number ⋮ Quickest path queries on transportation network ⋮ Distribution-sensitive construction of the greedy spanner ⋮ Stable roommates spanner ⋮ Well-separated pair decomposition in linear time? ⋮ Most finite point sets in the plane have dilation \(>1\) ⋮ Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree ⋮ Kinetic spanners in \(\mathbb R^{d}\) ⋮ Conic nearest neighbor queries and approximate Voronoi diagrams ⋮ The \(\varTheta_5\)-graph is a spanner ⋮ Minimum weight convex Steiner partitions ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ Geodesics and flows in a Poissonian city ⋮ On a family of strong geometric spanners that admit local routing strategies ⋮ Improved local algorithms for spanner construction ⋮ Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies ⋮ Graph spanners: a tutorial review ⋮ Temporal cliques admit sparse spanners ⋮ Fixed-orientation equilateral triangle matching of point sets ⋮ Light orthogonal networks with constant geometric dilation ⋮ Region-fault tolerant geometric spanners ⋮ Local geometric spanners ⋮ Computing the dilation of edge-augmented graphs in metric spaces ⋮ The reach of axis-aligned squares in the plane ⋮ Multi-colored spanning graphs ⋮ Minimizing the sum of distances to a server in a constraint network ⋮ An improved upper bound on dilation of regular polygons ⋮ Geometric spanner games ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ Average stretch factor: how low does it go? ⋮ Reprint of: Theta-3 is connected ⋮ Fast algorithms for approximate Fréchet matching queries in geometric trees
