Implementing a General-Purpose Edge Router

Dobkin, David P. and Gansner, Emden R. and Koutsofios, Lefteris and North, Stephen (1998) Implementing a General-Purpose Edge Router. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 262-271 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_68).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_68
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.999 Others
D Aesthetics > D.001 General
ID Code:87

Repository Staff Only: item control page

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., 74: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.

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 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. Sharir. Algorithmic motion planning in robotics. In J. van Leeuwen, editor, Algorithms and Complexity, volume A of Handbook of Theoretical Computer Science, pages 391-340. 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.