  We study the problem of efficiently answering strong connectivity queries
under two vertex failures. Given a directed graph $G$ with $n$ vertices, we
provide a data structure with $O(nh)$ space and $O(h)$ query time, where $h$ is
the height of a decomposition tree of $G$ into strongly connected subgraphs.
This immediately implies data structures with $O(n \log{n})$ space and
$O(\log{n})$ query time for graphs of constant treewidth, and $O(n^{3/2})$
space and $O(\sqrt{n})$ query time for planar graphs. For general directed
graphs, we give a refined version of our data structure that achieves
$O(n\sqrt{m})$ space and $O(\sqrt{m})$ query time, where $m$ is the number of
edges of the graph. We also provide some simple BFS-based heuristics that seem
to work remarkably well in practice. In the experimental part, we first
evaluate various methods to construct a decomposition tree with small height
$h$ in practice. Then we provide efficient implementations of our data
structures, and evaluate their empirical performance by conducting an extensive
experimental study on graphs taken from real-world applications.
