Maintaining triconnected components under node expansion

DOI10.1007/978-3-031-30448-4_15arXiv2301.03972MaRDI QIDQ6057331FDOQ6057331

Ignaz Rutter, Simon D. Fink

Publication date: 4 October 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: SPQR-trees are a central component of graph drawing and are also important in many further areas of computer science. From their inception onwards, they have always had a strong relation to dynamic algorithms maintaining information, e.g., on planarity and triconnectivity, under edge insertion and, later on, also deletion. In this paper, we focus on a special kind of dynamic update, the expansion of vertices into arbitrary biconnected graphs, while maintaining the SPQR-tree and further information. This will also allow 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"asius et al. [ESA 2021] from $O(m^2)$ to $O(mcdotDelta)$, where $Delta$ is the maximum pipe degree. This also reduces the time for solving several constrained planarity problems, e.g. for Clustered Planarity from $O((n+d{)}^2)$ to $O(n+dcdotDelta)$, where $d$ is the total number of crossings between cluster borders and edges and $Delta$ is the maximum number of edge crossings on a single cluster border.

Full work available at URL: https://arxiv.org/abs/2301.03972

Recommendations

• Maintenance of triconnected components of graphs
• Decremental maintenance of strongly connected components
• Maintaining 3-connectivity relative to a fixed basis
• On-line maintenance of triconnected components with SPQR-trees
• Maintaining bridge-connected and biconnected components on-line
• Triconnected decomposition for computingK-terminal network reliability
• Tri-connectivity augmentation in trees
• Maintaining the 3-Edge-Connected Components of a Graph On-Line
• scientific article
• Active and Concurrent Topology Maintenance

zbMATH Keywords

SPQR-treedynamic algorithmcluster planarity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On-Line Planarity Testing
• On-line maintenance of triconnected components with SPQR-trees
• Atomic Embeddability, Clustered Planarity, and Thickenability
• Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
• Separator based sparsification. I: Planarity testing and minimum spanning trees
• Fully-dynamic planarity testing in polylogarithmic time
• Title not available (Why is that?)
• TESTING MUTUAL DUALITY OF PLANAR GRAPHS
• Worst-Case Polylog Incremental SPQR-trees: Embeddings, Planarity, and Triconnectivity

Cited In (1)

• Maintaining triconnected components under node expansion

This page was built for publication: Maintaining triconnected components under node expansion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6057331)