Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles

DOI10.1137/140988103zbMath1333.68205arXiv1409.6397OpenAlexW2963197342MaRDI QIDQ3451755

Prosenjit Bose, André van Renssen, Rolf Fagerberg, Sander Verdonschot

Publication date: 18 November 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

online routinggeometric spannerlocal routingtheta-graphcompetitive routing

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Online algorithms; streaming algorithms (68W27)

Related Items (18)

On the spanning and routing ratios of the directed \(\varTheta_6\)-graph ⋮ Routing on heavy-path WSPD-spanners ⋮ 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 ⋮ Routing among convex polygonal obstacles in the plane ⋮ Routing in polygonal domains ⋮ Upper and lower bounds for online routing on Delaunay triangulations ⋮ On the spanning and routing ratio of the directed theta-four graph ⋮ Local routing algorithms on Euclidean spanners with small diameter ⋮ Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition ⋮ Construction and Local Routing for Angle-Monotone Graphs ⋮ On plane constrained bounded-degree spanners ⋮ The Price of Order ⋮ Routing among convex polygonal obstacles in the plane ⋮ Competitive Searching for a Line on a Line Arrangement. ⋮ Local routing in a tree metric \(1\)-spanner ⋮ Routing in Polygonal Domains

Cites Work

• Unnamed Item
• A simple routing algorithm based on Schnyder coordinates
• On succinct greedy drawings of plane triangulations and 3-connected plane graphs
• Some results on greedy embeddings in metric spaces
• Searching in the plane
• Greedy drawings of triangulations
• Towards tight bounds on theta-graphs: more is not always better
• Realizability of Delaunay triangulations
• Guide to wireless mesh networks
• Classes of graphs which approximate the complete Euclidean graph
• There are planar graphs almost as good as the complete graph
• On a conjecture related to geometric routing
• On the Spanning Ratio of Theta-Graphs
• New and improved spanning ratios for Yao graphs
• Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
• Survey on Oblivious Routing Strategies
• Plane Spanners of Maximum Degree Six
• Succinct Greedy Geometric Routing in the Euclidean Plane
• Online Routing in Triangulations
• ONLINE ROUTING IN CONVEX SUBDIVISIONS
• An Algorithm to Construct Greedy Drawings of Triangulations

This page was built for publication: Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles