Skip to Main Content
Handbook of Graph Drawing and Visualization
book

Handbook of Graph Drawing and Visualization

by Roberto Tamassia
August 2013
Intermediate to advanced content levelIntermediate to advanced
862 pages
32h 20m
English
Chapman and Hall/CRC
Content preview from Handbook of Graph Drawing and Visualization
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
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Handbook of Graph Theory, 2nd Edition

Handbook of Graph Theory, 2nd Edition

Jonathan L. Gross, Jay Yellen, Ping Zhang
Drawing Product Ideas

Drawing Product Ideas

Kent E. Eisenhuth, Manuel Lima

Publisher Resources

ISBN: 9781420010268