Drawing graphs with GLEE

Nachmanson, Lev and Robertson, George and Lee, Bongshin (2008) Drawing graphs with GLEE. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 389-394 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_38).

Full text not available from this repository.


This paper describes novel methods we developed to lay out graphs using Sugiyama's scheme [16] in a tool named GLEE. The main contributions are: a heuristic for creating a graph layout with a given aspect ratio, an efficient method of edge-crossings counting while performing adjacent vertex swaps, and a simple and fast spline routing algorithm.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_38
Classifications:S Software and Systems > S.001 General
ID Code:854

Repository Staff Only: item control page


Drawing graphs with GLEE technical report, Lev Nachmanson, George Robertson and Bongshin Lee, ftp://ftp.research.microsoft.com/pub/tr/TR-2007-72.pdf

graphviz todo list 22-December-2005}, note= URL:http://www.graphviz.org/doc/todo.html,.

J. Abello and E. R. Gansner. Short and smooth polygonal paths. In Proc. of the 3rd Latin American Symposium on Theoretical Informatics (LATIN'98), pages 151-162, Campinas, Brazil, 1998.

W. Barth, M. Jünger, and P. Mutzel. Simple and efficient bilayer cross counting. In Goodricht and Kobourov [10], pages 130-141.

U. Brandes and B. Köpf. Fast and simple horizontal coordinate assignment. In P. Mutzel, M. Jünger, and S. Leipert, editors, Graph drawing: 9th International Symposium, GD 2001, Vienna, Austria, September 2001, Revised Papers, volume 2265 of Lecture Notes in Computer Science, pages 31-44, New York, NY, USA, 2002. Springer-Verlag Inc.

E. G. Coffman and R. L. Graham. Optimal Scheduling for Two-Processor Systems. Acta Informatica, 1(3):200-213, Feb. 1972.

D. P. Dobkin, E. R. Gansner, E. Koutsofios, and S. North. Implementing a general-purpose edge router. In G. Di Battista, editor, Graph Drawing, Rome, Italy, September 18-20, 1997, pages pp. 262-271. Springer, 1998.

M. Eiglsperger, M. Siebenhaller, and M. Kaufmann. An efficient implementation of sugiyama's algorithm for layered graph drawing. In J. Pach, editor, Graph Drawing, New York, 2004, pages pp. 155-166. Springer, 2004.

E. R. Gansner, E. Koutsofios, S. C. North, and K.-P. Vo. A Technique for Drawing Directed Graphs. IEEE Transactions on Software Engineering, 19(3):214-230, Mar. 1993.

M. T. Goodricht and S. G. Kobourov, editors. Graph drawing: 10th International Symposium, GD 2002, Irvine, CA, USA, August 2002, Revised Papers, volume 2528 of Lecture Notes in Computer Science, New York, NY, USA, 2002. Springer-Verlag Inc.

P. Healy and N. S. Nikolov. A branch-and-cut approach to the directed acyclic graph layering problem. In Goodricht and Kobourov [10], pages 98-109.

D. Lutterkort and J. Peters. Smooth paths in a polygonal channel. In Symposium on Computational Geometry, pages 316-321, 1999.

A. Myles and J. Peters. Threading splines through 3d channels. Computer-Aided Design, 37(2):139-148, 2005.

N. S. Nikolov and A. Tarassov. Graph layering by promotion of nodes. Discrete Applied Mathematics, 154(5):848-860, 2006.

N. S. Nikolov, A. Tarassov, and J. Branke. In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes. J. Exp. Algorithmics, 10:2.7, 2005.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man and Cybernetics, SMC-11(2):109-125, Feb. 1981.