Edge-disjoint Spanning Trees in Triangulated Graphs on Surfaces and application to node labeling 1
Arnaud Labourel · 2006
In 1974, Kundu [4] has shown that triangulated (or maximal) simple toroidal graphs have three edge-disjoint spanning trees. We extend this result by showing that a triangulated graph on an orientable surface of genus g has at least three edge-disjoint spanning trees and so we can partition the edges of graphs of genus g into three forests plus a set of at most 6g − 3 edges.