Ulrik Brandes
Abstract
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.
- Ahuja, R., Magnanti, T., and Orlin, J. 1993. Network Flows. Prentice-Hall, Englewood Cliffs, NJ.]]Google Scholar
- 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/.]] Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- 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.]] Google Scholar
- Davidson, R. and Harel, D. 1996. Drawing graphs nicely using simulated annealing. ACM Trans. Graphics 15, 4, 301--331.]] Google Scholar
- Eades, P. 1984. A heuristic for graph drawing. Congressus Numerantium 42, 149--160.]]Google Scholar
- Eades, P. and Wormald, N. C. 1990. Fixed edge-length graph drawing is np-hard. Discrete Appl. Math. 28, 111--134.]] Google Scholar
- Fruchterman, T. M. and Reingold, E. M. 1991. Graph-drawing by force-directed placement. Softw. - Pract. Exp. 21, 11, 1129--1164.]] Google Scholar
- 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.]] Google Scholar
- Golub, G. H. and van Loan, C. F. 1996. Matrix Computations, 3rd ed. Johns Hopkins University Press, Baltimore, MD.]] Google Scholar
- 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.]] Google Scholar
- Kamada, T. and Kawai, S. 1989. An algorithm for drawing general undirected graphs. Inf. Process. Lett. 31, 7--15.]] Google Scholar
- 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.]]Google Scholar
- Kosmol, P. 1993. Methoden zur numerischen Behandlung nichtlinearer Gleichungen und Optimierungsaufgaben. Teubner Verlag.]]Google Scholar
- 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.]]Google Scholar
- Lengauer, T. 1990. Combinatorial Algorithms for Integrated Circuit Layout. Wiley, New York.]] Google Scholar
- Nachtigall, K. 1995. Time depending shortest-path problems with applications to railway networks. Eur. J. Oper. Res. 83, 1, 154--166.]]Google Scholar
- 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).]]Google Scholar
- Schulz, F., Wagner, D., and Weihe, K. 2000. Dijkstra's algorithm on-line: An empirical case study from public railroad transport. J. Exp. Algorithmics 5, 12.]] Google Scholar
- 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.]] Google Scholar
- Sedgewick, R. and Vitter, J. S. 1986. Shortest paths in Euclidean space. Algorithmica 1, 1, 31--48.]] Google Scholar
- 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.]] Google Scholar
- Siklóssy, L. and Tulp, E. 1988. Trains, an active time-table searcher. In Proceedings of the 8th European Conference on Artificial Intelligence. 170--175.]]Google Scholar
- Spellucci, P. 1993. Numerische Verfahren der nichtlinearen Optimierung. Birkhäuser Verlag.]]Google Scholar
- 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.]] Google Scholar
- Tutte, W. T. 1963. How to draw a graph? Proc. London Math. Soc., Third Series 13, 743--768.]]Google Scholar
Index Terms
- Generating node coordinates for shortest-path computations in transportation networks
Recommendations
Centroid virtual coordinates - A novel near-shortest path routing paradigm
Geographic routing has received increasing attention in the context of Wireless Sensor Networks since it frees the network from the energy-demanding task of building and maintaining a structure. It requires however each node to know its position, which ...
Detour Admitting Short Paths
ITNG '11: Proceedings of the 2011 Eighth International Conference on Information Technology: New GenerationsFinding the shortest path between two vertices in a weighted graph is a well explored problem and several efficient algorithms for solving it have been reported. We propose a new variation of this problem which we call the detour admitting shortest path ...
Generalization of Shortest Path Map
ITNG '10: Proceedings of the 2010 Seventh International Conference on Information Technology: New GenerationsWe consider the problem of constructing shortest path maps in two dimensions under angle constraint. Shortest path maps are used for planning short length paths from a fixed source point s to varying goal points. In the standard shortest path map the ...
Comments