Obtaining the shortest path between two vertices is a fundamental problem in graph theory and computer science. It is critical to modern navigation systems, transportation planning, and large-scale geographic information systems. Since classical methods such as Dijkstra’s algorithm are prohibitively slow on large graphs, indexing techniques are often used to increase the speed of shortest-path queries. Several modern indexing methods use tree decomposition (TD), an algorithm used to represent a graph as a tree. TD iteratively groups vertices of the original graph and then assigns adjacency between groups such that a tree is formed. The size of a TD’s smallest group minus one is its treewidth. Indices can then be constructed to solve shortest-path queries in O(treewidth) time. 

Our work focuses on large, sparse, undirected graphs known as road networks and builds upon iterative, elimination-based approaches for constructing TDs. Because computing a TD of minimal treewidth is computationally infeasible for large graphs, they are often computed using heuristics. There is currently a lack of data surrounding heuristic performance on road networks, and research surrounding TD heuristics often omits implementation details that can affect performance in real-world applications. We plan to evaluate the treewidth, treeheight, query processing time, and other metrics to compare several heuristic methods. In doing so, we aim to improve our understanding of which heuristics are optimal for producing TDs and indexes on road networks.