A Structural Linear-Time Algorithm for Computing the Tutte Decomposition

Name: A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
Keywords: FOS: Computer and information sciences, Data Structures and Algorithms, Discrete Mathematics (cs.DM), Discrete Mathematics, Combinatorics, FOS: Mathematics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO)

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 Jan 2025Embargo end date: 01 Jan 2025Publisher:arXiv

Authors: Bourneuf, Romain; Planken, Tim;

doi: 10.48550/arxiv.2508.06212

arXiv: http://arxiv.org/abs/2508.06212

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition

- Summary
- Subjects
- Metrics

Abstract

The block-cut tree decomposes a connected graph along its cutvertices, displaying its 2-connected components. The Tutte-decomposition extends this idea to 2-separators in 2-connected graphs, yielding a canonical tree-decomposition that decomposes the graph into its triconnected components. In 1973, Hopcroft and Tarjan introduced a linear-time algorithm to compute the Tutte-decomposition. Cunningham and Edmonds later established a structural characterization of the Tutte-decomposition via totally-nested 2-separations. We present a conceptually simple algorithm based on this characterization, which computes the Tutte-decomposition in linear time. Our algorithm first computes all totally-nested 2-separations and then builds the Tutte-decomposition from them. Along the way, we derive new structural results on the structure of totally-nested 2-separations in 2-connected graphs using a novel notion of stability, which may be of independent interest.

41 pages, 4 figures

Keywords

FOS: Computer and information sciences, Data Structures and Algorithms, Discrete Mathematics (cs.DM), Discrete Mathematics, Combinatorics, FOS: Mathematics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO)

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average

Found an issue? Give us feedback

Average

Green