{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T15:36:44Z","timestamp":1779205004095,"version":"3.51.4"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T00:00:00Z","timestamp":1568764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>\n            We present LOOM (Line-Ordering Optimized Maps), an automatic generator of geographically accurate transit maps. The input to LOOM is data about the lines of a transit network: for each line, its station sequence and geographical course. LOOM proceeds in three stages: (1) construct a line graph, where edges correspond to network segments with the same set of lines following the same course; (2) apply a set of local transformation rules that compute an optimal partial ordering of the lines and speed up the next stage; (3) construct an Integer Linear Program (ILP) that yields a line ordering for each edge and minimizes the total number of line crossings and line separations; and (4) based on the line graph and the computed line ordering, draw the map. As our maps respect the geography of the transit network, they can be used as overlays in typical map services. Previous research either did not take the network geography into account or was only concerned with schematic metro map layouting. We evaluate LOOM on six real-world transit networks, with line-ordering search-space sizes up to 2 \u00d7 10\n            <jats:sup>267<\/jats:sup>\n            . Using our transformation rules and an improved ILP formulation, we compute optimal line orderings in a fraction of a second for all networks. This enables interactive use of our method in map editors.\n          <\/jats:p>","DOI":"10.1145\/3337790","type":"journal-article","created":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T18:35:06Z","timestamp":1568831706000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Efficient Generation of Geographically Accurate Transit Maps"],"prefix":"10.1145","volume":"5","author":[{"given":"Hannah","family":"Bast","sequence":"first","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick","family":"Brosi","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sabine","family":"Storandt","sequence":"additional","affiliation":[{"name":"University of Konstanz, Konstanz, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,9,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-014-0222-6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_7"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 16th International Symposium on Graph Drawing (GD\u201908)","author":"Argyriou Evmorfia N.","year":"2008"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00199"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 14th Symposium on Computing: The Australasian Theory (CATS\u201908)","volume":"77","author":"Asquith Matthew","year":"2008"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1784907.1784933"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1758612.1758641"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1667528.1667537"},{"key":"e_1_2_1_9_1","volume-title":"Retrieved May 15th","author":"Developers Google","year":"2016"},{"key":"e_1_2_1_10_1","volume-title":"Us. Retrieved May 15th","author":"Dubreau Anton","year":"2016"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36763-2_41"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03841-4_29"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00351"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116261.3116408"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01450.x"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvlc.2005.09.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11805-0_36"},{"key":"e_1_2_1_18_1","volume-title":"Schematic Mapping Workshop, Essex, UK","author":"N\u00f6llenburg Martin","year":"2014"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25878-7_14"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3337790","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3337790","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:25Z","timestamp":1750204465000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3337790"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,18]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3337790"],"URL":"https:\/\/doi.org\/10.1145\/3337790","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,18]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}