Maintaining Triconnected Components under Node Expansion

Abstract

SPQR-trees model the decomposition of a biconnected graph into triconnected components. In this paper, we study the problem of dynamically maintaining an SPQR-tree while expanding vertices into arbitrary biconnected graphs. This allows us to efficiently merge two SPQR-trees by identifying the edges incident to two vertices with each other. We do this working along an axiomatic definition lifting the SPQR-tree to a stand-alone data structure that can be modified independently from the graph it might have been derived from. Making changes to this structure, we can now observe how the graph represented by the SPQR-tree changes, instead of having to reason which updates to the SPQR-tree are necessary after a change to the represented graph.

Using efficient expansions and merges allows us to improve the runtime of the SYNCHRONIZED PLANARITY algorithm by Bläsius et al. [TALG'23] from O(m²) to O(mΔ), where Δ is the maximum degree of a vertex with a synchronization constraint that requires two vertices to have the same rotation under a given bijection. This also reduces the time for solving several related constrained planarity problems, e.g. for CLUSTERED PLANARITY from O((n+d)²) to O(n+dΔ), where d is the total number of crossings between cluster borders and edges and Δ is the maximum number of edge crossings on a single cluster border. (There is a linear reduction from CLUSTERED to SYNCHRONIZED PLANARITY that converts edges crossing cluster boundaries to edges incident to synchronized vertices. Thereby, for an instance of the former problem, both definitions of Δ yield the same value.)