Geo-MST: A geographical minimum spanning tree plugin for QGIS

Abstract

Graphs describing the relation between nodes and edges are common in geographic information science. One of the algorithms that operate on graphs is ‘Minimum Spanning Tree (MST)’, which is a tree that connects all the nodes of a graph with minimum cost. There is no built-in functionality in QGIS, an open-source Geographical Information System (GIS) software, which can determine MST. This paper proposes a QGIS plugin that determines MST on geographical data using Kruskal’s algorithm. The updated version of the plugin (v2.0) offers three substantial improvements with respect to its former version (v1.0). First, the updated version is much faster in execution. The execution time of the two versions was assessed by determining MST on a randomly generated dataset consisting of 5000 polygons and New York City’s census blocks consisting of 38799 polygons. The updated version determined MSTs much faster, reaching up to 30-fold improvements. Second, the updated version can handle raster data. In this way, researchers might consider continuous geographical characteristics while estimating the costs of edges in addition to the discrete measure distance. Third, a barrier (obstacle) might be provided to ensure that the MST is fit for purpose as political boundaries or other restrictive socio-economic issues can be considered.

Keywords

• Kruskal’s algorithm
• Network analysis
• GIS
• Open-science