Finding Tutte paths in linear time

Therese Biedl, Philipp Kindermann

It is well-known that every planar graph has a Tutte path, i.e., a path $P$ such that any component of $G-P$ has at most three attachment points on $P$. However, it was only recent…