This web page is concerned with the experimental package used in the preparation of the paper [DF00].

The software is designed to run both under UNIX and in the algorithm animation system Leonardo IDE, currently available on Macintosh platform. In Leonardo you can enjoy the visualizations of the implemented algorithms and test their behavior on instances created by means of a user-friendly graph editor.

Download packages:

• cplib-1.0 is a preliminary version of the package used in the preparation of the extended abstract appeared in ALENEX'00. [Download cplib-1.0]
• cplib-2.0 is the new version of the package used in the preparation of the paper [DF00]. [Download cplib-2.0]
  

The algorithms implemented in the packages aim at solving the one-sided crossing minimization problem (in short, CP):

Solving this problem represents a fundamental step in the construction of aesthetically pleasing layouts of hierarchies and directed graphs according to the approach described in [STT81]. CP has been proved to be NP-complete in[EW94].

cplib-2.0 includes C implementations both of well-known heuristics for CP (barycenter [STT81], stochastic [D94], median [EW94], greedy [YS99], sifting [MSM99]), and of a new algorithm (pm) based on the computation of feedback arc sets.

The execution of any algorithm, as well as its visualizations, can be selectively turned on/off during the experiments.

Two kinds of visualizations are provided, i.e., bipartite drawings and structure plots:

Roughly speaking, a structure plot can be considered as an adjacency matrix of a bipartite graph with rows and colums sorted according to x1 and x0, respectively. The correspondence between crossings in a bipartite drawing and "crossings" in a structure plot is pointed out in [DF00].

The package also includes:

• The implementation of two random generators able to create bipartite graphs either according to a desired edge density or with limited maximum degree. Both generators use as a subroutine the rand() pseudo-random source of numbers provided by the ANSI C standard library.

• The real test sets used in the experiments described in [DF00]. Such test sets have been either extracted from digitized images - as proposed by Knuth in the Standford Graph Base - or retrieved from Matrix Market, a visual repository of test data for use in comparative studies of algorithms provided by the US National Institute of Standards and Technology (NIST).

To test the effectiveness of the aforementioned algorithms for CP in a more general context, we also implemented a simple parameterized version of the hierarchical approach [STT81] which can use any of them as a subroutine. In particular, in such a basic implementation we remove cycles from the input digraph with a depth-first visit, we layer vertices by means of a topological sort (possibly adding dummy vertices) and we follow a single-pass layer-by-layer sweep method to minimize edge crossings.

References

[DF00] C.Demetrescu, I.Finocchi, Removing Cycles for Minimizing Crossings, Manuscript, July 2000. A preliminary version appeared in ALENEX'00.

[STT81] K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern., 11(2):109--125, 1981.

[D94] S. Dresbach. A new heuristic layout algorithm for dags. In U. Derigs and A. Drexl, editors, Operations Research Proceedings, pages 121--126, 1994.

[EW94] P. Eades and N.C. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica, 11:379--403, 1994.

[YS99] A. Yamaguchi and A. Sugimoto. An approximation algorithm for the two-layered graph drawing problem. In Proc. 5th Annual Int. Conference on Computing and Combinatorics (COCOON'99), pages 81--91, 1999.

[MSM99] C. Matuszewski, R. Schonfeld, and P. Molitor. Using sifting for k-layer straightline crossing minimization. In Proc. 7th International Symposium on Graph Drawing (GD'99), LNCS 1731, pages 217--224, 1999.