  A path in an edge-colored graph is \textit{rainbow} if no two edges of it are
colored the same. The graph is said to be \textit{rainbow connected} if there
is a rainbow path between every pair of vertices. If there is a rainbow
shortest path between every pair of vertices, the graph is \textit{strong
rainbow connected}. We consider the complexity of the problem of deciding if a
given edge-colored graph is rainbow or strong rainbow connected. These problems
are called \textsc{Rainbow connectivity} and \textsc{Strong rainbow
connectivity}, respectively. We prove both problems remain $\NP$\hyp{}complete
on interval outerplanar graphs and $k$-regular graphs for $k \geq 3$.
Previously, no graph class was known where the complexity of the two problems
would differ. We show that for block graphs, which form a subclass of chordal
graphs, \textsc{Rainbow connectivity} is $\NP$\hyp{}complete while
\textsc{Strong rainbow connectivity} is in $\P$. We conclude by considering
some tractable special cases, and show for instance that both problems are in
$\XP$ when parameterized by tree-depth.
