Linear-size planar Manhattan network for convex point sets
From MaRDI portal
Publication:824337
DOI10.1016/j.comgeo.2021.101819zbMath1479.05334arXiv1909.06457OpenAlexW3192572748MaRDI QIDQ824337
Anil Maheshwari, Sasanka Roy, Satyabrata Jana
Publication date: 15 December 2021
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1909.06457
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22)
Cites Work
- Minimum Manhattan network is NP-complete
- On the stretch factor of Delaunay triangulations of points in convex position
- On rectilinear link distance
- The rectilinear Steiner arborescence problem
- Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
- Approximating the generalized minimum Manhattan network problem
- Geometric biplane graphs. II: Graph augmentation
- The minimum Manhattan network problem: Approximations and exact solutions
- A rounding algorithm for approximating minimum Manhattan networks
- The Stretch Factor of the Delaunay Triangulation Is Less than 1.998
- A plane 1.88-spanner for points in convex position
- GREEDY CONSTRUCTION OF 2-APPROXIMATE MINIMUM MANHATTAN NETWORKS
- Geometric Spanner Networks
- Planar graph decomposition and all pairs shortest paths
- Planar spanners and approximate shortest path queries among obstacles in the plane
- AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
- The Rectilinear Steiner Arborescence Problem Is NP-Complete
- Algorithms and Computation
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Linear-size planar Manhattan network for convex point sets
