Dynamically switching vertices in planar graphs

states: either on or off. We wish to maintain dynamically such
graphs under an intermixed sequence of updates and queries. An update
may reverse the status of a vertex, by switching it either on or
off, and may insert a new edge or delete an existing edge. A query
tests whether any two given vertices are connected in the subgraph
induced by the vertices that are on. We give efficient algorithms
that maintain information about connectivity on planar graphs in
$O(log^3 n)$ amortized time per query, insert, delete, switch-on
and switch-off operation over sequences of at least $\Omega(n)$
operations, where $n$ is the number of vertices of the graph.
This improves sharply on previous approaches.