Abstract-The dynamic shortest paths problem on planar graphs asks us to preprocess a planar graph G such that we may support insertions and deletions of edges in G as well as distance queries between any two nodes u, v subject to the constraint that the graph remains planar at all times. This problem has been extensively studied in both the theory and experimental communities over the past decades. In this paper, we follow a recent and very active line of work on showing lower bounds for polynomial time problems based on popular conjectures, obtaining the first such results for natural problems in planar graphs. Such results were previously out of reach due to the highly non-planar nature of known reductions and the impossibility of "planarizing gadgets". We introduce a new framework which is inspired by techniques from the literatures on distance labelling schemes and on parameterized complexity. Using our framework, we show that no algorithm for dynamic shortest paths or maximum weight bipartite matching in planar graphs can support both updates and queries in amortized O(n 1 2 −ε ) time, for any ε > 0, unless the classical allpairs-shortest-paths problem can be solved in truly subcubic time, which is widely believed to be impossible. We extend these results to obtain strong lower bounds for other related problems as well as for possible trade-offs between query and update time. Interestingly, our lower bounds hold even in very restrictive models where only weight updates are allowed.
Recently, the first conditional lower bounds for dynamic problems on planar graphs were shown by Abboud and Dahlgaard REF , however, they did not cover dynamic reachability in directed planar graphs.
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
Computer Science Mathematics