Trees and co-trees with constant maximum degree in planar 3-connected graphs

This paper considers the conjecture by Grünbaum that every planar 3-connected graph has a spanning tree T such that both T and its co-tree have maximum degree at most 3. Here, the co-tree of T is the spanning tree of the dual obtained by taking the duals of the non-tree edges. While Grünbaum’s conjecture remains open, we show that every planar 3-connected graph has a spanning tree T such that both T and its co-tree have maximum degree at most 5. It can be found in linear time.