Connectivity Oracles for Planar Graphs

DOI10.1007/978-3-642-31155-0_28zbMATH Open1357.68015arXiv1204.4159OpenAlexW1798009099MaRDI QIDQ2904567FDOQ2904567

Authors: Glencora Borradaile, Seth Pettie, Christian Wulff-Nilsen 

Publication date: 14 August 2012

Published in: Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Abstract: We consider dynamic subgraph connectivity problems for planar graphs. In this model there is a fixed underlying planar graph, where each edge and vertex is either "off" (failed) or "on" (recovered). We wish to answer connectivity queries with respect to the "on" subgraph. The model has two natural variants, one in which there are $d$ edge/vertex failures that precede all connectivity queries, and one in which failures/recoveries and queries are intermixed. We present a $d$-failure connectivity oracle for planar graphs that processes any $d$ edge/vertex failures in $sort(d,n)$ time so that connectivity queries can be answered in $pred(d,n)$ time. (Here $sort$ and $pred$ are the time for integer sorting and integer predecessor search over a subset of $[n]$ of size $d$.) Our algorithm has two discrete parts. The first is an algorithm tailored to triconnected planar graphs. It makes use of Barnette's theorem, which states that every triconnected planar graph contains a degree-3 spanning tree. The second part is a generic reduction from general (planar) graphs to triconnected (planar) graphs. Our algorithm is, moreover, provably optimal. An implication of Patrascu and Thorup's lower bound on predecessor search is that no $d$-failure connectivity oracle (even on trees) can beat $pred(d,n)$ query time. We extend our algorithms to the subgraph connectivity model where edge/vertex failures (but no recoveries) are intermixed with connectivity queries. In triconnected planar graphs each failure and query is handled in $O(logn)$ time (amortized), whereas in general planar graphs both bounds become $O(lo{g}^{2}n)$.

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

Recommendations

• Connectivity of planar graphs
• Exact distance oracles for planar graphs
• Oracles for bounded-length shortest paths in planar graphs
• Almost optimal distance oracles for planar graphs
• scientific article; zbMATH DE number 140100
• Optimal vertex connectivity oracles
• Connectivity and planarity of Cayley graphs
• Connectivity oracles for graphs subject to vertex failures
• Connectivity oracles for graphs subject to vertex failures
• Computing planarity in computable planar graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Cited In (4)

• Connectivity oracles for graphs subject to vertex failures
• Connectivity oracles for failure prone graphs
• Connectivity check in 3-connected planar graphs with obstacles
• Connectivity oracles for graphs subject to vertex failures

This page was built for publication: Connectivity Oracles for Planar Graphs

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