Experimental Comparison of Graph Drawing Algorithms for Cubic Graphs
Tiziana Calamoneri, Simone Jannelli, Rossella Petreschi · Journal of Graph Algorithms and Applications · 1999
We report on the results of an experimental study in which we have compared the performances of three algorithms for drawing general cubic graphs on the bidimensional orthogonal grid. The comparison works on 18,000 randomly generated graphs with up to 300 vertices and analyzes the number of bends and crossings, the area, the edge length and the running time. Communicated by R. Tamassia: submitted May 1997; revised May 1999. The rst author is supported by the Italian Research Council { CNR. T. Calamoneri et al., Experimental Comparison..., JGAA, 3(2) 1-23 (1999) 2 1 Introduction An orthogonal grid drawing of a graph is a drawing such that the edges are polygonal chains consisting of horizontal and vertical segments and the vertices have integer coordinates. The graphs that admit such a drawing must have maximum degree 4. Among these graphs, cubic graphs (i.e. regular graphs of degree 3) and at most cubic graphs (i.e. graphs having bounded degree 3), constitute interesting and comple...