The german site of wikipedia (Look at wikipedia k-zusammenhang) states that there are linear-time algorithms to decide whether a given undirected graph is triconnected (Deleting any two vertices does not disconnect the graph).
Unfortunately, there is no link to any such algorithm, not even a description, which method is used. A necessary condition is, that every vertex has degree at least $3$ and that the graph is connected (which can be easily checked by hand).
- Does anyone know such an algorithm ?
- Is there an algorithm, which can be done by hand ?
There is linear time algorithm due to Hopcroft and Tarjan for finding the biconnected components of a graph. There is an article on wikipedia (English).