Routing on the visibility graph

DOI10.4230/LIPICS.ISAAC.2017.18MaRDI QIDQ5136234zbMATH OpenOpenAlexFDO

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

Publication date 25 November 2020

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

zbMATH Keywords

\(\Theta\)-graphconstraintsroutingvisibility graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We consider the problem of routing on a network in the presence of line segment constraints (i.e., obstacles that edges in our network are not allowed to cross). Let $P$ be a set of $n$ points in the plane and let $S$ be a set of non-crossing line segments whose endpoints are in $P$. We present two deterministic 1-local $O(1)$-memory routing algorithms that are guaranteed to find a path of at most linear size between any pair of vertices of the emph{visibility graph} of $P$ with respect to a set of constraints $S$ (i.e., the algorithms never look beyond the direct neighbours of the current location and store only a constant amount of additional information). Contrary to {em all} existing deterministic local routing algorithms, our routing algorithms do not route on a plane subgraph of the visibility graph. Additionally, we provide lower bounds on the routing ratio of any deterministic local routing algorithm on the visibility graph.

Recommendations

• Routing on the Visibility Graph
• Competitive local routing with constraints
• Competitive local routing with constraints

Cites work

• Competitive local routing with constraints
• Guide to wireless mesh networks
• Survey on oblivious routing strategies
• Upper bounds on the spanning ratio of constrained theta-graphs

Cited in

(7)

• Routing among convex polygonal obstacles in the plane
• Routing in polygonal domains
• Competitive local routing with constraints
• Routing on the Visibility Graph
• Routing in polygonal domains
• Competitive local routing with constraints
• Routing among convex polygonal obstacles in the plane

This page was built for publication: Routing on the visibility graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136234)