Rupp, TobiasFunke, Stefan2023-03-302023-03-3020211999-48931843172968http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-128767http://elib.uni-stuttgart.de/handle/11682/12876http://dx.doi.org/10.18419/opus-12857We prove a Ω(√n) lower bound on the query time for contraction hierarchies (CH) as well as hub labels, two popular speed-up techniques for shortest path routing. Our construction is based on a graph family not too far from subgraphs that occur in real-world road networks, in particular, it is planar and has a bounded degree. Additionally, we borrow ideas from our lower bound proof to come up with instance-based lower bounds for concrete road network instances of moderate size, reaching up to 96% of an upper bound given by a constructed CH. For a variant of our instance-based schema applied to some special graph classes, we can even show matching upper and lower bounds.eninfo:eu-repo/semantics/openAccesshttps://creativecommons.org/licenses/by/4.0/004380article2021-06-12