# Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies
## 1 Introduction  
The goal of graph partitioning is to divide a graph into a given number of roughly equally sized parts by removing a small number of edges or nodes. Graph partitioning has many practical applications, such as accelerating matrix multiplication, dividing compute workloads, image processing, circuit design, and the focus of this work, accelerating shortest path computations in road networks. For an overview of the state-of-the-art in graph partitioning, we refer the reader to a survey article [1]. Computing shortest paths in road networks is a fundamental building block in applications such as navigation systems (e.g., Google Maps), logistics planning, and traffic simulation. Unfortunately, [PERSON]'s algorithm [2] takes over a second for a single query on continental-size road networks with tens of millions of nodes, rendering it infeasible for interactive scenarios. This has led to a large amount of research on speedup techniques [3], which often use an expensive preprocessing phase to enable fast queries. Arc-Flags [4; 5] is one of the early techniques that use graph partitioning. It has been frequently used to enhance other techniques, e.g., SHARC [6], combining shortcuts [7] and Arc-Flags, ReachFlags [8], combining Reach [9] and Arc-Flags as well as CHASE [8], combining Contraction Hierarchies [10] and Arc-Flags. In navigation systems, the graph topology changes infrequently, but the metric (arc weights) changes frequently, e.g., due to traffic congestion or road closures. To accommodate this, modern speedup techniques split the preprocessing phase into an expensive metric-independent preprocessing phase and a fast metric-dependent _customization_ phase. The two state-of-the-art techniques are Multilevel Overlays, also known as Customizable Route Planning [11], which use nested k-way partitions and Customizable Contraction Hierarchies (CCHs) [12], whichuse nested dissection orders [13]. In this work, we focus on CCHs, which extend classic two-phase Contraction Hierarchies [10] to the three-phase approach with customization. Contraction Hierarchies simulate contracting all nodes in a given order and insert shortcut arcs between the neighbors of a contracted node. These represent paths via the contracted nodes. Shortest \(s\)-\(t\) path queries are answered by, e.g., a bidirectional Dijkstra search [2] from \(s\) and \(t\), which only considers shortcut and original arcs to higher-ranked nodes. Thus, nodes which lie on many shortest paths should be ranked high in the order. Customizable Contraction Hierarchies [12] use contraction orders computed via recursive balanced node separators (nested dissection) in order to achieve a logarithmic search space depth with few added shortcuts. Node separators are considered to lie on many shortest paths, as any path between the components crosses the separator. The weights of the contraction hierarchy can then be quickly customized to any metric, allowing, e.g., the incorporation of real-time traffic information. The running time needed for the customization and the shortest path queries depends on the quality of the calculated order. Previously proposed partitioning tools for computing separators in road networks include FlowCutter [14], Inertial Flow [15], KaHiP [16], Metis [17], PUNCH [18], and Buffoon [19]. KaHiP and Metis are general-purpose graph partitioning tools. PUNCH and Buffoon are special-purpose partitioners, which aim to use geographical features of road networks such as rivers or mountains. Rivers and mountains form very small cuts and were dubbed _natural cuts_ in [18]. PUNCH identifies and deletes natural cuts, then contracts the remaining components and subsequently runs a variety of highly randomized local search algorithms. Buffoon incorporates the idea of natural cuts into KaHiP, running its evolutionary multilevel partitioner instead of the flat local searches of PUNCH. In [14], it was shown that FlowCutter is also able to identify and leverage natural cuts.