# Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures

Preprint · Guillaume Chapuis, Hristo Djidjev

- Archive id: arxiv:1503.07192
- Published: 2015-03-24
- arXiv: https://arxiv.org/abs/1503.07192
- Source URL: https://arxiv.org/abs/1503.07192
- PDF: https://arxiv.org/pdf/1503.07192
- Provenance: arxiv

## Abstract

We develop an efficient parallel algorithm for answering shortest-path queries in planar graphs and implement it on a multi-node CPU/GPU clusters. The algorithm uses a divide-and-conquer approach for decomposing the input graph into small and roughly equal subgraphs and constructs a distributed data structure containing shortest distances within each of those subgraphs and between their boundary vertices. For a planar graph with $n$ vertices, that data structure needs $O(n)$ storage per processor and allows queries to be answered in $O(n^{1/4})$ time.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.