Evaluating the Influence of Graph Characteristics on Parallel Algorithms for Derived Graph Structures

This work investigates how graph characteristics affect the quality of derived graphs, specifically focusing on graph spanners. Graph spanners retain all vertices and a subset of edges while preserving shortest distances with an allowable stretch, making them essential for efficiently approximating graph structures. We emphasize recent advancements in parallel algorithms for constructing spanners in sparse graphs, building on the work of Miller et al. and Forster et al. By extracting key graph properties and employing data analysis techniques—such as correlation analysis, linear regression, and random forest regression—we examine the relationships between these characteristics and the size of the derived graphs, which is vital for optimizing spanner construction in real-world applications.