Computer-assisted City Touring for Explorers

The basic purpose of a map is to trace shortest paths between two locations in a city. However, this is not always what a user needs. Consider a tourist in an unknown city, he/she might want to trace routes to visit multiple landmarks while passing through the main streets of the city, possibly more than once through the same street. Such functionality is not yet available in online map services, which are prone to provide shortest paths that connect all landmarks. Rather, is of common interest a tour that puts together the most central streets (topologically speaking), minimizes the trajectory and, at the same time, passes through such landmarks. To cope with this problem, it is possible to investigate techniques of Center-Piece Subgraph, Absorbing Random Walk Centrality and Spanning Edge-Betweenness; such techniques can be used to find induced subgraphs that optimize centrality measures for a set of referential nodes or edges, i.e. landmarks or streets. The results shall be in the form of optimized algorithms, and how to integrate them into online systems. Studies in this line can succeed if they can guarantee timely scalability at the same time that they provide algorithms that produce tours (1) considering all the known destinations; (2) including the main streets of a city; and, (3) ensuring the shortest routes.