<p><strong>theory results:</strong></p>

<p><em>exact:</em> </p>

<p>Jittat Fakcharoenphol, Satish Rao: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5): 868-889 (2006)</p>

<p><em>approximate:</em></p>

<p>Ittai Abraham, Shiri Chechik, Cyril Gavoille: Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. STOC 2012: 1199-1218</p>

<p>Philip N. Klein, Sairam Subramanian: A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. Algorithmica 22(3): 235-249 (1998)</p>

<p><strong>implementation for road networks:</strong></p>

<p>Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato Fonseca F. Werneck: Customizable Route Planning. SEA 2011: 376-387</p>

<p>(updates only to cost of edges, might be possible to extend to addition and deletion of edges)</p>

<p><strong>comment</strong></p>

<p>none of the methods above achieves O(1) query time</p>

<p>note that if you use lots of space for a data structure, it probably means that you will need significant time to update the data structure in case the graph changes
(low query time at the cost of high update time)</p>

<p>if updates are rare, it might be worth it.
what is the application?</p>

CC BY-SA 3.0
2013-03-18T04:23:21.950Z
2013-03-18T04:23:21.950Z
Christian Sommer
<p>I'm trying to come up with an algorithm to solve all-pairs shortest paths (APSP) problem in dynamic directed planar graph with nonnegative real weights. Additionally:</p>

<ul>
<li><strong>My primary focus is to achieve lowest possible query time ($O(1)$ would be perfect)</strong>, it's the most important thing for me, this operation will be done <em>very</em> often (of course the price will be increased memory consumption, but I'm fine with that),</li>
<li>Graph is fully dynamic - both edges &amp; vertices can be added/deleted - it would be nice if I didn't have to recompute everything from scratch,</li>
<li>$|V| = 10000$ (approximately).</li>
</ul>

<p>I've search the Internet and skimmed through lots of articles, but didn't find anything that matched perfectly my case.</p>

<p>Any help and/or links would be highly appreciated.</p>

<planar-graphs><shortest-path>
Dynamic all-pairs shortest paths - O(1) query
Darmak
# Dynamic all-pairs shortest paths - O(1) query

(Asked by: username_0 on 2013-03-16)

I'm trying to come up with an algorithm to solve all-pairs shortest paths (APSP) problem in dynamic directed planar graph with nonnegative real weights. Additionally:

* **My primary focus is to achieve lowest possible query time ($O(1)$ would be perfect)**, it's the most important thing for me, this operation will be done *very* often (of course the price will be increased memory consumption, but I'm fine with that),
* Graph is fully dynamic - both edges & vertices can be added/deleted - it would be nice if I didn't have to recompute everything from scratch,
* $|V| = 10000$ (approximately).

I've search the Internet and skimmed through lots of articles, but didn't find anything that matched perfectly my case.

Any help and/or links would be highly appreciated.

**Tags:** planar-graphs, shortest-path

---

## 1 answers

### Answer by username_1 on 2013-03-18. Score: 4

**theory results:**

*exact:*

Jittat Fakcharoenphol, Satish Rao: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5): 868-889 (2006)

*approximate:*

Ittai Abraham, Shiri Chechik, Cyril Gavoille: Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. STOC 2012: 1199-1218

Philip N. Klein, Sairam Subramanian: A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. Algorithmica 22(3): 235-249 (1998)

**implementation for road networks:**

Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato Fonseca F. Werneck: Customizable Route Planning. SEA 2011: 376-387

(updates only to cost of edges, might be possible to extend to addition and deletion of edges)

**comment**

none of the methods above achieves O(1) query time

note that if you use lots of space for a data structure, it probably means that you will need significant time to update the data structure in case the graph changes
(low query time at the cost of high update time)

if updates are rare, it might be worth it.
what is the application?


---

