标题： 一种结构线性时间算法用于计算图的Tutte分解 显示英文标题

标题： A Structural Linear-Time Algorithm for Computing the Tutte Decomposition

摘要： 块-割树将连通图沿着其割点分解，显示其2-连通分量。 Tutte分解将这一思想扩展到2-连通图中的2-分离，产生一个规范的树分解，将图分解为其三连通分量。 1973年，Hopcroft和Tarjan引入了一种线性时间算法来计算Tutte分解。 Cunningham和Edmonds后来通过完全嵌套的2-分离建立了Tutte分解的结构特征。 我们提出一个基于此特征的概念简单的算法，该算法以线性时间计算Tutte分解。 我们的算法首先计算所有完全嵌套的2-分离，然后从这些分离构建Tutte分解。 在此过程中，我们利用一种新的稳定性概念，得出了关于2-连通图中完全嵌套2-分离结构的新结构结果，这可能具有独立的兴趣。 显示英文摘要

摘要： 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.