Showing 2025Show all
2 papers · 1 filter
cs.DS2025
A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
Romain Bourneuf, Tim Planken
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-connect…
math.CO2025
A Tutte-type canonical decomposition of 3- and 4-connected graphs
Jan Kurkofka, Tim Planken
We provide a unique decomposition of every 4-connected graph into parts that are either quasi-5-connected, cycles of triangle-torsos and 3-connected torsos on vertices, ge…