Metro Maps on Octilinear Grid Graphs

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BAST, Hannah, Patrick BROSI, Sabine STORANDT, 2020. Metro Maps on Octilinear Grid Graphs. Eurographics Conference on Visualization (EuroVis) 2020. Norrköping, May 25, 2020 - May 29, 2020. In: Computer Graphics Forum. Hoboken, New Jersey:Wiley-Blackwell - STM, pp. 357-367. ISSN 0167-7055. eISSN 1467-8659. Available under: doi: 10.1111/cgf.13986

@inproceedings{Bast2020Metro-51239, title={Metro Maps on Octilinear Grid Graphs}, url={}, year={2020}, doi={10.1111/cgf.13986}, number={Vol. 39}, issn={0167-7055}, address={Hoboken, New Jersey}, publisher={Wiley-Blackwell - STM}, booktitle={Computer Graphics Forum}, pages={357--367}, author={Bast, Hannah and Brosi, Patrick and Storandt, Sabine}, note={Article Number: 3} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dc:date rdf:datatype="">2020-10-07T08:16:02Z</dc:date> <dc:creator>Bast, Hannah</dc:creator> <dc:creator>Brosi, Patrick</dc:creator> <dcterms:available rdf:datatype="">2020-10-07T08:16:02Z</dcterms:available> <dcterms:abstract xml:lang="eng">Schematic transit maps (often called "metro maps" in the literature) are important to produce comprehensible visualizations of complex public transit networks. In this work, we investigate the problem of automatically drawing such maps on an octilinear grid with an arbitrary (but optimal) number of edge bends. Our approach can naturally deal with obstacles that should be respected in the final drawing (points of interest, rivers, coastlines) and can prefer grid edges near the real-world course of a line. This allows our drawings to be combined with existing maps, for example as overlays in map services. We formulate an integer linear program which can be used to solve the problem exactly. We also provide a fast approximation algorithm which greedily calculates shortest paths between node candidates on the underlying octilinear grid graph. Previous work used local search techniques to update node positions until a local optimum was found, but without guaranteeing octilinearity. We can thus calculate nearly optimal metro maps in a fraction of a second even for complex networks, enabling the interactive use of our method in map editors.</dcterms:abstract> <dc:contributor>Brosi, Patrick</dc:contributor> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:creator>Storandt, Sabine</dc:creator> <dspace:isPartOfCollection rdf:resource=""/> <dcterms:isPartOf rdf:resource=""/> <dc:contributor>Bast, Hannah</dc:contributor> <dcterms:title>Metro Maps on Octilinear Grid Graphs</dcterms:title> <dc:language>eng</dc:language> <bibo:uri rdf:resource=""/> <dc:contributor>Storandt, Sabine</dc:contributor> <dcterms:issued>2020</dcterms:issued> <dcterms:rights rdf:resource=""/> <dc:rights>terms-of-use</dc:rights> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


My Account