How to eat a graph: Computing selection sequences for the continuous generalization of road networks

Autor(en): Chimani, M. 
Van Dijk, T.C.
Haunert, J.-H.
Herausgeber: Schneider, M.
Gertz, M.
Huang, Y.
Sankaranarayanan, J.
Krumm, J.
Stichwörter: Approximation algorithms; Continuous generalization; Generalized map; Geographic information systems; Information systems; Integer linear programs; Integer programming; Map generalization; Motor transportation; Optimization; Road segments; Roads and streets; Scheduling; Selection sequences; Transportation, Constant-factor approximation algorithms; Weighted graph, Optimization
Erscheinungsdatum: 2014
Herausgeber: Association for Computing Machinery
Journal: GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
Volumen: 04-07-November-2014
Startseite: 243
Seitenende: 252
In a connected weighted graph, consider deleting the edges one at a time, in some order, such that after every deletion the remaining edges are still connected. We study the problem of finding such a deletion sequence that maximizes the sum of the weights of the edges in all the distinct graphs generated: the weight of an edge is counted in every graph that it is in. This effectively asks for the high-weight edges to remain in the graph as long as possible, subject to connectivity. We apply this to road network generalization in order to generate a sequence of successively more generalized maps of a road network so that these maps go well together, instead of considering each level of generalization independently. In particular, we look at the problem of making a road segment selection that is consistent across zoom levels. We show that the problem is NP-hard and give an integer linear program (ILP) that solves it optimally. Solving this ILP is only feasible for small instances. Next we develop constant-factor approximation algorithms and heuristics. We experimentally demonstrate that these heuristics perform well on real-world instances. Copyright 2014 ACM.
Conference of 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2014 ; Conference Date: 4 November 2014 Through 7 November 2014; Conference Code:119343
ISBN: 9781450331319
DOI: 10.1145/2666310.2666414
Externe URL:

Show full item record

Page view(s)

Last Week
Last month
checked on Apr 18, 2024

Google ScholarTM