  We present a data structure that, given a graph $G$ of $n$ vertices and $m$
edges, and a suitable pair of nested $r$-divisions of $G$, preprocesses $G$ in
$O(m+n)$ time and handles any series of edge-deletions in $O(m)$ total time
while answering queries to pairwise biconnectivity in worst-case $O(1)$ time.
In case the vertices are not biconnected, the data structure can return a
cutvertex separating them in worst-case $O(1)$ time.
  As an immediate consequence, this gives optimal amortized decremental
biconnectivity, 2-edge connectivity, and connectivity for large classes of
graphs, including planar graphs and other minor free graphs.
