Answers are grounded in this paper and cite their sources.
We describe a simple and practical algorithm for compact routing on connected random unit disk graphs. Using a recursive nested dissection of an n -vertex graph based on compact and balanced vertex separators, we construct routing tables with an average of O (log 2 n ) entries per vertex in a preprocessing step. The routing tables then support handshaking-based routing, where the handshaking can be implemented similarly to a DNS lookup. Our routing algorithm is guaranteed to deliver on the graph, while incurring moderate stretch. We describe a basic version of the algorithm that requires modifiable headers and a more advanced version which eliminates this need and incurs less stretch.
No takes yet. Share an insight, caveat, or question.
Gotsman et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: