Abstract
Although routing is a well-studied problem in various contexts, there remain unsolved problems in routing edges for graph layouts. In contrast with techniques from other domains such as VLSI CAD and robotics, where physical constraints play a major role, aesthetics play the more important role in graph layout. For graphs, we seek paths that are easy to follow and add meaning to the layout. We describe a collection of aesthetic attributes applicable to drawing edges in graphs, and present a general approach for routing individual edges subject to these principles. We also give implementation details and survey difficulties that arise in an implementation.
Portions of the work of this author done while visiting AT&T Laboratories. This work supported in part by NSF Grant CCR-9643913 and by the US Army Research Office under Grant DAAH04-96-1-0181
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
J.-D. Boissonnat, A. Cerezo, and J. Leblond. Shortest paths of bounded curvature in the plane. J. Intell. and Robotics Systems, 11:5–20, 1994.
B. Chazelle. A theorem on polygon cutting with applications. In Proc. 23rd IEEE Symp. Foundations of Computer Science, pages 339–349, 1982.
D. P. Dobkin, D. L. Souvaine, and C. J. Van Wyk. Decomposition and intersection of simple splinegons. Algorithmica, 3:473–486, 1988.
L. E. Dubins. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents. Amer. J. Math., 79:497–516, 1957.
S. Fortune and G. Wilfong. Planning constrained motion. Annals of Mathematics and Artificial Intelligence, 3:21–82, 1991.
E.R. Gansner, E. Koutsofios, S.C. North, and K.P. Vo. A technique for drawing directed graphs. IEEE Transactions on Software Engineering, March 1993.
E.R. Gansner, S.C. North, and K.P. Vo. Dag-a program that draws directed graphs. Software-Practice and Experience, 18(11):1047–1062, 1988.
S. K. Ghosh and D. M. Mount. An output-sensitive algorithm for computing visibility graphs. SIAM J. Computing, 20(5):888–910, 1991.
J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. In Proc. 2nd Workshop Algorithms Data Struct., volume 519 of Lecture Notes in Computer Science, pages 331–342. Springer-Verlag, 1991.
10.P. Jacobs. Minimal length curvature constrained paths in the presence of obstacles. Technical Report 90042, Laboratoire d'Automatique et d'Analyse des Systemes, 7 Avenue du Colonel Roche-31077 Toulouse, France, February 1990.
Y. Kanayama and B. I. Hartman. Smooth local path planning for autonomous vehicles. In Proc. IEEE Intl. Conf. on Robotics and Automation, volume 3, pages 1265–1270, 1989.
J.-C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, Boston, 1991.
J. P. Laumond. Finding collision-free smooth trajectories for a non-holonomic mobile robot. In Proc. Intl. Joint Conf. on Artificial Intelligence, pages 1120–1123, 1987.
W. Nelson. Continuous-curvature paths for autonomous vehicles. In Proc. IEEE Intl. Conf. on Robotics and Automation, volume 3, pages 1260–1264, 1989.
S.C. North. Incremental layout in dynadag. In F.J. Brandenburg, editor, Symp. on Graph Drawing GD'95, volume 1027 of Lecture Notes in Computer Science, pages 409–418, 1996.
M. H. Overmars and E. Welzl. New methods for computing visibility graphs. In Proc. 4th Annu. ACM Sympos. Comput. Geom., pages 164–171, 1988.
J. A. Reeds and L. A. Shepp. Optimal paths for a car that goes both forwards and backwards. Pacific J. of Mathematics, 145(2), 1990.
G. Sander, M. Alt, C. Ferdinand, and R. Wilhelm. Clax, a visualized compiler. In F.J. Brandenburg, editor, Symp. on Graph Drawing GD'95, volume 1027 of Lecture Notes in Computer Science, pages 459–462, 1996.
Philip J. Schneider. An algorithm for automatically fitting digitized curves. In Andrew S. Glassner, editor, Graphics Gems, pages 612–626. Academic Press, Boston, Mass., 1990.
J. T. Schwartz and M. Sharin, Algorithmic motion planning in robotics. In J. van Leeuwen, editor, Algorithms and Complexity, volume A of Handbook of Theoretical Computer Science, pages 391–430. Elsevier, Amsterdam, 1990.
S. Suri. A linear time algorithm for minimum link paths inside a simple polygon. Computer Vision and Graphical Image Processing, 35:99–110, 1986.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dobkin, D.P., Gansner, E.R., Koutsofios, E., North, S.C. (1997). Implementing a general-purpose edge router. In: DiBattista, G. (eds) Graph Drawing. GD 1997. Lecture Notes in Computer Science, vol 1353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63938-1_68
Download citation
DOI: https://doi.org/10.1007/3-540-63938-1_68
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63938-1
Online ISBN: 978-3-540-69674-2
eBook Packages: Springer Book Archive