A Survey on Computing Schematic Network Maps: The Challenge to Interactivity

Information

Abstract

Schematic maps are in daily use to show the connec- tivity of subway systems and to facilitate travellers to plan their journeys effectively. This study surveys up-to-date algorithmic approaches in order to give an overview of the state of the art in schematic network mapping. The study investigates the hypothesis that the choice of algorithmic approach is often guided by the requirements of the mapping application. For example, an algorithm that computes globally optimal solutions for schematic maps is capable of producing results for printing, while it is not suitable for computing instant layouts due to its long running time. Our analysis and discussion, therefore, focus on the compu- tational complexity of the problem formulation and the running times of the schematic map algorithms, including algorithmic network layout techniques and station labeling techniques. The correlation between problem complexity and running time is then visually depicted using scatter plot diagrams. Moreover, since metro maps are common metaphors for data visualization, we also investigate online tools and application domains using metro map representations for analytics purposes, and finally summarize the potential future opportunities for schematic maps.

Additional Files and Images

Additional images and videos

Additional files

Weblinks

BibTeX

@WorkshopTalk{wu-2019-smw,
  title =      " A Survey on Computing Schematic Network Maps: The Challenge
               to Interactivity",
  author =     "Hsiang-Yun Wu and Benjamin  Niedermann and Shigeo Takahashi
               and Martin N\"{o}llenburg",
  year =       "2019",
  abstract =   "Schematic maps are in daily use to show the connec- tivity
               of subway systems and to facilitate travellers to plan their
               journeys effectively. This study surveys up-to-date
               algorithmic approaches in order to give an overview of the
               state of the art in schematic network mapping. The study
               investigates the hypothesis that the choice of algorithmic
               approach is often guided by the requirements of the mapping
               application. For example, an algorithm that computes
               globally optimal solutions for schematic maps is capable of
               producing results for printing, while it is not suitable for
               computing instant layouts due to its long running time. Our
               analysis and discussion, therefore, focus on the compu-
               tational complexity of the problem formulation and the
               running times of the schematic map algorithms, including
               algorithmic network layout techniques and station labeling
               techniques. The correlation between problem complexity and
               running time is then visually depicted using scatter plot
               diagrams. Moreover, since metro maps are common metaphors
               for data visualization, we also investigate online tools and
               application domains using metro map representations for
               analytics purposes, and finally summarize the potential
               future opportunities for schematic maps.",
  month =      apr,
  doi =        "https://www.ac.tuwien.ac.at/files/pub/smw19-position-5.pdf",
  event =      "The 2nd Schematic Mapping Workshop 2019",
  location =   "Vienna, Austria",
  keywords =   "Metro Maps, Graph Drawing, Metaphors",
  URL =        "/research/publications/2019/wu-2019-smw/",
}