Graph Theory Applications in Network Design for Rural Telecommunications in Borno State

This study explores the application of graph theory to the design of cost-effective telecommunications networks for rural communities in Borno State, North East Nigeria, a region where communication infrastructure remains critically underdeveloped following years of security-related disruptions. The study frames the network design problem as a minimum spanning tree and shortest path optimisation challenge, drawing on classical graph theory algorithms including Kruskal's algorithm, Prim's algorithm, and Dijkstra's shortest path algorithm. Geographic data on the locations of twenty-five rural settlements in the Gwoza and Chibok local government areas are used to construct weighted graphs representing potential network linkages, with edge weights corresponding to estimated installation costs and distances between nodes. Each algorithm is implemented programmatically, and the resulting network topologies are compared across criteria including total network cost, redundancy, and mean path length between nodes. The study finds that Prim's algorithm converges more rapidly than Kruskal's for the sparse graphs typical of rural settings, while Dijkstra's algorithm provides practically useful routing solutions for identifying optimal communication pathways within proposed network architectures. The research contextualises its findings within the Nigerian government's National Broadband Plan and the Universal Service Provision Fund's rural connectivity mandate. Recommendations are advanced for the adoption of graph-theoretic planning tools by telecommunications infrastructure planners operating in underserved regions of the North East. Keywords: graph theory, minimum spanning tree, rural telecommunications, network design, Borno State