17.5. SUCCESS STORIES 563
17.5.1 SPQR-Trees
In the early 1970s, Hopcroft and Tarjan [HT73a] published the first linear-time algorithm
for computing the triconnected components of a graph. This decomposition is in particular
important in graph drawing—here usually known as the data structure SPQR-tree—, as it
allows us to encode all planar embedding of a graph. Hence, this algorithm has been cited
over and over again for showing that SPQR-trees can be constructed in linear time. However,
for a long time nobody was able to come up with an implementation of this algorithm, since
the paper was hard to understand and contained various flaws, thus preventing a straight-
forward implementation.
This situation is a classical example for showing the need of