spqrtree

Description

spqrtree is a pure Python implementation of the SPQR-tree data structure for biconnected graphs. It decomposes a biconnected graph into its triconnected components (S, P, Q, and R nodes) and organizes them as a tree.

SPQR-trees are a classical tool in graph theory, widely used for planarity testing, graph drawing, and network analysis.

The implementation is based on the Gutwenger & Mutzel (2001) linear-time algorithm, with corrections to Hopcroft & Tarjan (1973), and follows the SPQR-tree data structure defined by Di Battista & Tamassia (1996).

Features:

• Pure Python --- no compiled extensions or external dependencies.
• Handles multigraphs (parallel edges between the same vertex pair).
• Simple dict-based input for quick prototyping.
• Typed package with PEP 561 support.
• Requires Python 3.10 or later.

Installation

You can install spqrtree with pip:

pip install spqrtree

You may also install the latest source from the spqrtree GitHub repository.

pip install git+https://github.com/imacat/spqrtree.git

Quick Start

from spqrtree import SPQRTree, NodeType

# K4 complete graph
graph = {
    1: [2, 3, 4],
    2: [1, 3, 4],
    3: [1, 2, 4],
    4: [1, 2, 3],
}
tree = SPQRTree(graph)
print(tree.root.type)     # NodeType.R
print(len(tree.nodes()))  # number of SPQR-tree nodes

Documentation

Refer to the documentation on Read the Docs.

Change Log

Refer to the change log.

References

• C. Gutwenger and P. Mutzel, "A Linear Time Implementation of SPQR-Trees," Graph Drawing (GD 2000), LNCS 1984, pp. 77--90, 2001. doi:10.1007/3-540-44541-2_8
• J. E. Hopcroft and R. E. Tarjan, "Dividing a Graph into Triconnected Components," SIAM Journal on Computing, 2(3), pp. 135--158, 1973. doi:10.1137/0202012
• G. Di Battista and R. Tamassia, "On-Line Planarity Testing," SIAM Journal on Computing, 25(5), pp. 956--997, 1996. doi:10.1137/S0097539794280736

Acknowledgments

This project was written from scratch in pure Python but drew inspiration from the SageMath project. The SPQR-tree implementation in SageMath served as a valuable reference for both its implementation approach and its comprehensive test cases.

Development was assisted by Claude Code (Anthropic).

Copyright

Copyright (c) 2026 imacat.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Authors

imacat

imacat@mail.imacat.idv.tw

2026/3/4