{"ID":2884692,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.06212","arxiv_id":"2508.06212","title":"A Structural Linear-Time Algorithm for Computing the Tutte Decomposition","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.","short_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...","url_abs":"https://arxiv.org/abs/2508.06212","url_pdf":"https://arxiv.org/pdf/2508.06212v1","authors":"[\"Romain Bourneuf\",\"Tim Planken\"]","published":"2025-08-08T10:48:18Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\",\"math.CO\"]","methods":"[]","has_code":false}