Constrained routing between non-visible vertices

DOI10.1016/j.tcs.2021.02.017zbMath1497.68370arXiv1710.08060OpenAlexW4206956491MaRDI QIDQ5918146

André van Renssen, Sander Verdonschot, Matias Korman, Prosenjit Bose

Publication date: 9 March 2021

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1710.08060

zbMATH Keywords

triangulationconstraintsvisibility graphrouting\(\Theta\)-graph

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Related Items

Routing among convex polygonal obstacles in the plane ⋮ Routing in polygonal domains ⋮ Bounded-degree spanners in the presence of polygonal obstacle ⋮ Constrained routing between non-visible vertices ⋮ Routing on the visibility graph

Cites Work

• Unnamed Item
• A geometric consistency theorem for a symbolic perturbation scheme
• Guide to wireless mesh networks
• Classes of graphs which approximate the complete Euclidean graph
• On plane constrained bounded-degree spanners
• Competitive online routing in geometric graphs
• Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Survey on Oblivious Routing Strategies
• Routing on the Visibility Graph
• A General Approach to Removing Degeneracies
• Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints
• Constrained routing between non-visible vertices
• Routing with guaranteed delivery in ad hoc wireless networks