548 CHAPTER 17. THE OPEN GRAPH DRAWING FRAMEWORK (OGDF)
the triconnected components (called the skeletons of the tree nodes) of the graph: S-nodes
correspond to serial structures, P-nodes to parallel structures, and R-nodes to simple, tri-
connected structures; Q-nodes simply correspond to the edges in the graph and are hence
not required by an implementation. Both data structures can be build in linear time; the
latter constructs the SPQR-tree by applying the corrected version [GM01] of Hopcroft and
Tarjan’s algorithm [HT73a] for decomposing a graph into its triconnected components. The
OGDF is one of the few places where one can find a correct implementation of this complex
and involved algorithm (to the best of our knowledge, AGD was the first