Two linear time algorithms for MST on minor closed graph classes
This article presents two simple deterministic algorithms for finding the Minimum Spanning Tree in time for any non-trivial class of graphs closed on graph minors. This applies in particular to planar graphs and graphs of bounded genus. Both algorithms run on a pointer machine and they require no a priori knowledge of the structure of the class except for its density. Edge weights are only compared.