{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:43:15Z","timestamp":1750308195494,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2004,12,31]],"date-time":"2004-12-31T00:00:00Z","timestamp":1104451200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2004,12,31]]},"abstract":"<jats:p>Speed-up techniques that exploit given node coordinates have proven useful for shortest-path computations in transportation networks and geographic information systems. To facilitate the use of such techniques when coordinates are missing from some, or even all, of the nodes in a network we generate artificial coordinates using methods from graph drawing. Experiments on a large set of German train timetables indicate that the speed-up achieved with coordinates from our drawings is close to that achieved with the true coordinates---and in some special cases even better.<\/jats:p>","DOI":"10.1145\/1005813.1005815","type":"journal-article","created":{"date-parts":[[2005,8,2]],"date-time":"2005-08-02T06:34:09Z","timestamp":1122964449000},"source":"Crossref","is-referenced-by-count":0,"title":["Generating node coordinates for shortest-path computations in transportation networks"],"prefix":"10.1145","volume":"9","author":[{"given":"Ulrik","family":"Brandes","sequence":"first","affiliation":[{"name":"University of Konstanz, Konstanz, Germany"}]},{"given":"Frank","family":"Schulz","sequence":"additional","affiliation":[{"name":"University of Karlsruhe, Karlsruhe, Germany"}]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[{"name":"University of Karlsruhe, Karlsruhe, Germany"}]},{"given":"Thomas","family":"Willhalm","sequence":"additional","affiliation":[{"name":"University of Karlsruhe, Karlsruhe, Germany"}]}],"member":"320","published-online":{"date-parts":[[2004,12,31]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Ahuja R. Magnanti T. and Orlin J. 1993. Network Flows. Prentice-Hall Englewood Cliffs NJ.]]  Ahuja R. Magnanti T. and Orlin J. 1993. Network Flows. Prentice-Hall Englewood Cliffs NJ.]]"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Anderson E. Bai Z. Bischof C. Blackford S. Demmel J. Dongarra J. Du Croz J. Greenbaum A. Hammarling S. McKenney A. and Sorensen D. 1999. LAPACK User's Guide 3rd ed. Society for Industrial and Applied Mathematics. Available at http:\/\/www.netlib.org\/lapack\/.]]   Anderson E. Bai Z. Bischof C. Blackford S. Demmel J. Dongarra J. Du Croz J. Greenbaum A. Hammarling S. McKenney A. and Sorensen D. 1999. LAPACK User's Guide 3rd ed. Society for Industrial and Applied Mathematics. Available at http:\/\/www.netlib.org\/lapack\/.]]","DOI":"10.1137\/1.9780898719604"},{"volume-title":"Proceedings of the Third Nordic Workshop on Genetic Algorithms and their Applications. 193--206","author":"Branke J.","key":"e_1_2_1_3_1","unstructured":"Branke , J. , Bucher , F. , and Schmeck , H . 1997. A genetic algorithm for drawing undirected graphs . In Proceedings of the Third Nordic Workshop on Genetic Algorithms and their Applications. 193--206 .]] Branke, J., Bucher, F., and Schmeck, H. 1997. A genetic algorithm for drawing undirected graphs. In Proceedings of the Third Nordic Workshop on Genetic Algorithms and their Applications. 193--206.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1215\/S0012-7094-40-00718-9","article-title":"The dissection of rectangles into squares","volume":"7","author":"Brooks R. L.","year":"1940","unstructured":"Brooks , R. L. , Smith , C. A. B. , Stone , A. H. , and Tutte , W. T. 1940 . The dissection of rectangles into squares . Duke Math. J. 7 , 312 -- 340 .]] Brooks, R. L., Smith, C. A. B., Stone, A. H., and Tutte, W. T. 1940. The dissection of rectangles into squares. Duke Math. J. 7, 312--340.]]","journal-title":"Duke Math. J."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Third International Symposium on Graph Drawing (GD '95)","volume":"1027","author":"Cruz I. F.","unstructured":"Cruz , I. F. and Twarog , J. P . 1996. 3D graph drawing with simulated annealing . In Proceedings of the Third International Symposium on Graph Drawing (GD '95) , F. J. Brandenburg, ed. Lecture Notes in Computer Science , vol. 1027 . Springer, Berlin, 162--165.]] Cruz, I. F. and Twarog, J. P. 1996. 3D graph drawing with simulated annealing. In Proceedings of the Third International Symposium on Graph Drawing (GD '95), F. J. Brandenburg, ed. Lecture Notes in Computer Science, vol. 1027. Springer, Berlin, 162--165.]]"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/234535.234538"},{"key":"e_1_2_1_7_1","volume-title":"Congressus Numerantium 42","author":"Eades P.","year":"1984","unstructured":"Eades , P. 1984 . A heuristic for graph drawing . Congressus Numerantium 42 , 149--160.]] Eades, P. 1984. A heuristic for graph drawing. Congressus Numerantium 42, 149--160.]]"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90110-X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380211102"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Eighth International Symposium on Graph Drawing (GD","volume":"1984","author":"Gajer P.","year":"2000","unstructured":"Gajer , P. , Goodrich , M. T. , and Kobourov , S. G . 2001. A fast multi-dimensional algorithm for drawing large graphs . In Proceedings of the Eighth International Symposium on Graph Drawing (GD 2000 ), J. Marks, ed. Lecture Notes in Computer Science , vol. 1984 . Springer, Berlin, 211--221.]] Gajer, P., Goodrich, M. T., and Kobourov, S. G. 2001. A fast multi-dimensional algorithm for drawing large graphs. In Proceedings of the Eighth International Symposium on Graph Drawing (GD 2000), J. Marks, ed. Lecture Notes in Computer Science, vol. 1984. Springer, Berlin, 211--221.]]"},{"key":"e_1_2_1_11_1","volume-title":"Matrix Computations","author":"Golub G. H.","unstructured":"Golub , G. H. and van Loan , C. F. 1996. Matrix Computations , 3 rd ed. Johns Hopkins University Press , Baltimore, MD .]] Golub, G. H. and van Loan, C. F. 1996. Matrix Computations, 3rd ed. Johns Hopkins University Press, Baltimore, MD.]]","edition":"3"},{"volume-title":"Proceedings of the 12th IEEE International Conference Data Engineering. 76--84","author":"Jung S.","key":"e_1_2_1_12_1","unstructured":"Jung , S. and Pramanik , S . 1996. Hiti graph model of topographical road maps in navigation systems . In Proceedings of the 12th IEEE International Conference Data Engineering. 76--84 .]] Jung, S. and Pramanik, S. 1996. Hiti graph model of topographical road maps in navigation systems. In Proceedings of the 12th IEEE International Conference Data Engineering. 76--84.]]"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90102-6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1109\/21.278993","article-title":"Automating the layout of network diagrams with specified visual organization","volume":"24","author":"Kosak C.","year":"1994","unstructured":"Kosak , C. , Marks , J. , and Shieber , S. 1994 . Automating the layout of network diagrams with specified visual organization . IEEE Trans. Syst. Man Cybern. 24 , 3, 440 -- 454 .]] Kosak, C., Marks, J., and Shieber, S. 1994. Automating the layout of network diagrams with specified visual organization. IEEE Trans. Syst. Man Cybern. 24, 3, 440--454.]]","journal-title":"IEEE Trans. Syst. Man Cybern."},{"volume-title":"Methoden zur numerischen Behandlung nichtlinearer Gleichungen und Optimierungsaufgaben","author":"Kosmol P.","key":"e_1_2_1_15_1","unstructured":"Kosmol , P. 1993. Methoden zur numerischen Behandlung nichtlinearer Gleichungen und Optimierungsaufgaben . Teubner Verlag .]] Kosmol, P. 1993. Methoden zur numerischen Behandlung nichtlinearer Gleichungen und Optimierungsaufgaben. Teubner Verlag.]]"},{"key":"e_1_2_1_16_1","unstructured":"Kumar A. and Fowler R. 1994. A Spring Modeling Algorithm to Position Nodes of an Undirected Graph in Three Dimensions. Tech. rep. Department of Computer Science University of Texas Pan American Edinburgh.]]  Kumar A. and Fowler R. 1994. A Spring Modeling Algorithm to Position Nodes of an Undirected Graph in Three Dimensions. Tech. rep. Department of Computer Science University of Texas Pan American Edinburgh.]]"},{"volume-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"Lengauer T.","key":"e_1_2_1_17_1","unstructured":"Lengauer , T. 1990. Combinatorial Algorithms for Integrated Circuit Layout . Wiley , New York .]] Lengauer, T. 1990. Combinatorial Algorithms for Integrated Circuit Layout. Wiley, New York.]]"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/0377-2217(94)E0349-G","article-title":"Time depending shortest-path problems with applications to railway networks","volume":"83","author":"Nachtigall K.","year":"1995","unstructured":"Nachtigall , K. 1995 . Time depending shortest-path problems with applications to railway networks . Eur. J. Oper. Res. 83 , 1, 154 -- 166 .]] Nachtigall, K. 1995. Time depending shortest-path problems with applications to railway networks. Eur. J. Oper. Res. 83, 1, 154--166.]]","journal-title":"Eur. J. Oper. Res."},{"volume-title":"Proceedings of the Sixth International Conference on Applied Computer Networking in Architecture, Construction, Design, Civil Engineering, and Urban Planning (europIA '97)","author":"Preuss T.","key":"e_1_2_1_19_1","unstructured":"Preuss , T. and Syrbe , J . -H. 1997. An integrated traffic information system . In Proceedings of the Sixth International Conference on Applied Computer Networking in Architecture, Construction, Design, Civil Engineering, and Urban Planning (europIA '97) .]] Preuss, T. and Syrbe, J.-H. 1997. An integrated traffic information system. In Proceedings of the Sixth International Conference on Applied Computer Networking in Architecture, Construction, Design, Civil Engineering, and Urban Planning (europIA '97).]]"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384254"},{"volume-title":"Proceedings of the Algorithm Engineering and Experiments (ALENEX '02)","author":"Schulz F.","key":"e_1_2_1_21_1","unstructured":"Schulz , F. , Wagner , D. , and Zaroliagis , C . 2002. Using multi-level graphs for timetable information . In Proceedings of the Algorithm Engineering and Experiments (ALENEX '02) . Lecture Notes in Computer Science, Springer, Berlin, in press.]] Schulz, F., Wagner, D., and Zaroliagis, C. 2002. Using multi-level graphs for timetable information. In Proceedings of the Algorithm Engineering and Experiments (ALENEX '02). Lecture Notes in Computer Science, Springer, Berlin, in press.]]"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840435"},{"volume-title":"Proceedings of the Ninth IEEE International Conference on Data Engineering. 31--39","author":"Shekhar S.","key":"e_1_2_1_23_1","unstructured":"Shekhar , S. , Kohli , A. , and Coyle , M . 1993. Path computation algorithms for advanced traveler information system (ATIS) . In Proceedings of the Ninth IEEE International Conference on Data Engineering. 31--39 .]] Shekhar, S., Kohli, A., and Coyle, M. 1993. Path computation algorithms for advanced traveler information system (ATIS). In Proceedings of the Ninth IEEE International Conference on Data Engineering. 31--39.]]"},{"volume-title":"Proceedings of the 8th European Conference on Artificial Intelligence. 170--175","author":"Sikl\u00f3ssy L.","key":"e_1_2_1_24_1","unstructured":"Sikl\u00f3ssy , L. and Tulp , E . 1988. Trains, an active time-table searcher . In Proceedings of the 8th European Conference on Artificial Intelligence. 170--175 .]] Sikl\u00f3ssy, L. and Tulp, E. 1988. Trains, an active time-table searcher. In Proceedings of the 8th European Conference on Artificial Intelligence. 170--175.]]"},{"volume-title":"Numerische Verfahren der nichtlinearen Optimierung","author":"Spellucci P.","key":"e_1_2_1_25_1","unstructured":"Spellucci , P. 1993. Numerische Verfahren der nichtlinearen Optimierung . Birkh\u00e4user Verlag .]] Spellucci, P. 1993. Numerische Verfahren der nichtlinearen Optimierung. Birkh\u00e4user Verlag.]]"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the Sixth International Symposium on Graph Drawing (GD '98)","volume":"1547","author":"Tunkelang D.","year":"1998","unstructured":"Tunkelang , D. 1998 . JIGGLE: Java interactive general graph layout environment . In Proceedings of the Sixth International Symposium on Graph Drawing (GD '98) , S. H. Whitesides, ed. Lecture Notes in Computer Science , vol. 1547 . Springer, Berlin, 413--422.]] Tunkelang, D. 1998. JIGGLE: Java interactive general graph layout environment. In Proceedings of the Sixth International Symposium on Graph Drawing (GD '98), S. H. Whitesides, ed. Lecture Notes in Computer Science, vol. 1547. Springer, Berlin, 413--422.]]"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1112\/plms\/s3-13.1.743","article-title":"How to draw a graph","volume":"13","author":"Tutte W. T.","year":"1963","unstructured":"Tutte , W. T. 1963 . How to draw a graph ? Proc. London Math. Soc., Third Series 13 , 743 -- 768 .]] Tutte, W. T. 1963. How to draw a graph? Proc. London Math. Soc., Third Series 13, 743--768.]]","journal-title":"Proc. London Math. Soc., Third Series"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1005813.1005815","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1005813.1005815","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:24:55Z","timestamp":1750263895000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1005813.1005815"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,12,31]]},"references-count":27,"alternative-id":["10.1145\/1005813.1005815"],"URL":"https:\/\/doi.org\/10.1145\/1005813.1005815","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2004,12,31]]}}}