Graph Drawing Toolkit

Precompiled library and header files, available for 32bit/64bit Linux and 32bit Windows platforms.

Main changes:

• First LEDA independent release.
  The tools based on the LEDA graphics functions are no longer available in this version. Namely, GRID and GDTDEMO have been removed.
• Boyer & Myrvold planarity testing and embedding algorithm
• PQ-Tree data structure
• Lowest Common Ancestor with Schieber and Viskin algorithm
• Minumum spanning tree for planar graphs with Matsui algorithm
• New supported platfoms: Linux Debian, Ubuntu, Gentoo. Windows XP/Vista with Visual Studio .NET 2005
• Full 64bit architecture compatibility
• Several memory leaks removed.
• Several bugs fixed

Batch layout generator, available for 32bit/64bit Linux and 32bit Windows platforms

Prrecompiled library and header files, with an upper bound on the number of nodes of the graphs (20 nodes max).
Available for 32bit/ 64bit Linux and 32bit Windows platforms.

Batch layout generator, with an upper bound on the number of nodes of the graphs (20 nodes max).
Available for 32bit/64bit Linuxand 32bit Windows platforms

Prrecompiled library and header files. This is a full-functional copy of the library, with a time limitation of 6 months.
This software is distributed free of charge for academic research and teaching only.
Available for 32bit/ 64bit Linux and 32bit Windows platforms.

Batch layout generator. This is a full-functional copy of BLAG, with a time limitation of 6 months.
This software is distributed free of charge for academic research and teaching only.
Available for 32bit/64bit Linux and 32bit Windows platforms

Compatible LEDA release: LEDA-4.0 and LEDA-4.1

Main changes:

• New compaction refinement (based on one-dimensional compaction techinques similar to those used in VLSI)
• Fully customizable size of the nodes in orthogonal drawings
• Extension of the incremental orthogonalizer for nodes of arbitrary degree
• New constraints for specifying the vertex-angles in orthogonal drawings
• New methods for exporting the GDT graphs in the "fig" file format (the "fig" format is the own format of the "xfig" application under Unix. Many modules are freely provided to export the "fig" format to most used formats (as PostScript, Latex, gif, BMP, etc.)
• New algorithm for computing an orthogonal-quasi-upward drawing starting from a quasi-upward drawing
• New methods for specifying the orientation of an orthogonal representation
• Extensions of the self-test facility to check the correctness of your installation and the performance of GDToolkit on your platform
• New interactive demos for handling orthogonal drawings with nodes of prescribed sizes, and improvement of the already existing demos
• New supported platforms: Linux Redhat 6.0, and Windows 95/98/NT with Visual C++ 6.0
• Minor bugs fixed

Compatible LEDA releases: LEDA-R-3.6.1 and LEDA-R-3.7.1

Main changes:

• New compaction techniques (based on flow-techniques and on a turn-regularization pre-processing step)
• Several bugs fixed
• Improved reliability for the Windows version
• New installation facilities
• Selftest facility to check the correctedness of your installation and the performance of GDToolkit on your platform.
• Improved documentation for the class undi_graph
• New interactive demo (called gdtdemo) allowing you to:
  • see the drawings produced by BLAG
  • create a graph with a simple graphic editor
  • launch orthogonal, upward, and polyline drawing methods
• New supported platform: Linux RedHat 5.2

Compatible LEDA releases: LEDA-R-3.6.1

Main changes:

• Dual-graph generation
• Planarizer supporting constraints
• Extension of min-cost flow with lower bounds
• Batch layout generator (BLAG)
• Refinement of the end-user graph-editing tool (GRID)
• Constraints management
  • No crosses on the specified edge
  • No bends / any number of bends on the specified edge
  • Only right / only left bends along the specified edge
  • Specified set of nodes on the same face
  • Specified ordered set of nodes on the same face
• Quasi-upward graphs
  • Slow upward layout generator (minimum number of bends over all the planar embeddings)
  • Slow compactor (based on a min-cost-flow technique)
• Orthogonal graphs
  • Slow compactor (based on a min-cost-flow technique)
  • Compaction-refinement heuristic
  • Extension of orthogonal algorithms for nodes with arbitrary degree

Main changes:

• Markers management
• Bimodality test
• ST-digraph test
• Planarity test
• Bimodal planarity test
• Embedding mutuation
• Degree-reducing heuristic
• Multigraph to simple-graph transformer
• End-user graph-editing tool (GRID)
• Directed graphs
  • Node expansion
  • Edge contraction
• Planar graphs
  • Random nodes/edges generator preserving biconnectivity
  • Visibility representation (for biconnected graphs)
  • Polyline representation (based on visibility representation)
• Orthogonal graphs
  • Slow orthogonalizer (minimum number of bends over all the planar embeddings)
  • Incremental orthogonalizer for dynamic drawing (only for nodes with degree < 5)
• Upward graphs
  • Face saturator
  • Fast compactor
  • Optimal layout generator (minimum number of bends within the given planar embedding)

Basic features:

• Identifiers management
• Labels management
• Embedding management
• Save & load functionalities
• Extensible tag-based file format
• Editor method of the draw_undi class
• Undirected, partially directed, and directed multigraphs
  • Breadth First Search (BFS)
  • Depth First Search / Spanning tree (DFS)
  • Depth First Search with low-points calculation
  • Topological Sort
  • ST-numbering
  • Connectivity test
  • Biconectivity test
  • Acyclicity test
  • Connected components extractor
• Directed graphs
  • Shortest Path (Dijkstra)
  • Longest Path
  • Min-cost flow (non-negative costs only)
• Planar graphs
  • Edge and face split
  • Separation-pairs detection
  • Wide set of face management methods
  • Wide set of face-border management methods
• Orthogonal graphs
  • Quick orthogonalizer (based on visibility representation)
  • Optimal orthogonalizer (minimum number of bends within the given planar embedding)
  • Slow orthogonalizer (minimum number of bends over all the planar embeddings)
  • Face rectangularizer
  • Fast orthogonal compactor (based on DFS on the dual graph)
• Tree graphs
  • Breadth First Search
  • Depth First Search
  • Post-order visit
  • Efficient evert operation
  • Layout generator
• SPQR-tree graphs
  • Decomposition of the reference planar graph into its triconnected components
  • Wide set of methods for generating planar embeddings of the reference planar graph
  • Specialized efficient evert operation