Show simple item record

dc.contributor.authorBast, Hannahen_US
dc.contributor.authorBrosi, Patricken_US
dc.contributor.authorStorandt, Sabineen_US
dc.contributor.editorViola, Ivan and Gleicher, Michael and Landesberger von Antburg, Tatianaen_US
dc.description.abstractSchematic 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.en_US
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.rightsAttribution 4.0 International License
dc.subjectHuman centered computing
dc.subjectGraph drawings
dc.subjectTheory of computation
dc.subjectInteger programming
dc.subjectMathematics of computing
dc.subjectApproximation algorithms
dc.titleMetro Maps on Octilinear Grid Graphsen_US
dc.description.seriesinformationComputer Graphics Forum
dc.description.sectionheadersNetworks and Sets

Files in this item


This item appears in the following Collection(s)

  • 39-Issue 3
    EuroVis 2020 - Conference Proceedings

Show simple item record

Attribution 4.0 International License
Except where otherwise noted, this item's license is described as Attribution 4.0 International License