Two Linear Time Algorithms for MST on Minor Closed Graph Classes

Abstract: This article presents two simple deterministic algorithms for finding the Minimum Spanning Tree in O(jV j + jEj) time for any proper class of graphs closed on graph minors, which includes planar graphs and graphs of bounded genus. Both algorithms require no a priori knowledge of the structure of the class except for its density; edge weights are only compared and no random access to data is needed. 1. Introduction: The MS