| Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming. | |
| | |
MedLine Citation:
|
PMID: 20498505 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
Metro maps are schematic diagrams of public transport networks that serve as visual aids for route planning and navigation tasks. It is a challenging problem in network visualization to automatically draw appealing metro maps. There are two aspects to this problem that depend on each other: the layout problem of finding station and link coordinates and the labeling problem of placing non-overlapping station labels. In this paper we present a new integral approach that solves the combined layout and labeling problem (each of which, independently, is known to be NP-hard) using mixed-integer programming (MIP). We identify seven design rules used in most real-world metro maps. We split these rules into hard and soft constraints and translate them into a MIP model. Our MIP formulation finds a metro map that satisfies all hard constraints (if such a drawing exists) and minimizes a weighted sum of costs that correspond to the soft constraints. We have implemented the MIP model and present a case study and the results of an expert assessment to evaluate the performance of our approach in comparison to both manually designed official maps and results of previous layout methods. |
| | |
Authors:
|
Martin Nöllenburg; Alexander Wolff |
Related Documents
:
|
16128465 - Redundant manipulator techniques for partially decentralized path planning and control ... 3812835 - Degree of public support for household hazardous waste control alternatives. 20358405 - Theoretical and practical problems with wide reflective equilibrium in bioethics. 281145 - The palatally impacted canine: a new approach to treatment. 11434485 - Orthopedic problems in sport climbing. 12904915 - Temporal patterns in bacterial communities in three temperate lakes of different trophi... |
Publication Detail:
|
Type: JOURNAL ARTICLE Date: 2010-5-21 |
Journal Detail:
|
Title: IEEE transactions on visualization and computer graphics Volume: - ISSN: 1077-2626 ISO Abbreviation: - Publication Date: 2010 May |
Date Detail:
|
Created Date: 2010-5-25 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9891704 Medline TA: IEEE Trans Vis Comput Graph Country: - |
Other Details:
|
Languages: ENG Pagination: - Citation Subset: - |
Affiliation:
|
Karlsruhe Institute of Technology (KIT) , Karlsruhe. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Analyzing Visibility Configurations.
Next Document: An application of multivariate statistical analysis for Query-Driven Visualization.