An SPQR-Tree-Like Embedding Representation for Upward Planarity

Guido Brückner, Markus Himmel, Ignaz Rutter

The SPQR-tree is a data structure that compactly represents all planar embeddings of a biconnected planar graph. It plays a key role in constrained planarity testing. We develop a…