Heuristics, Experimental Subjects, and Treatment Evaluation in Bigraph Crossing Minimization

ABSTRACT

The bigraph crossing problem, embedding the two node sets of a bipartite graph along two parallel lines so that edge crossings are minimized, has applications to circuit layout and graph drawing. Experimental results for several previously known and two new heuristics suggest continued exploration of the problem, particularly sparse instances. We emphasize careful design of experimental subject classes and present novel views of the results. All source code, data, and scripts are available on-line

REFERENCES

• 1: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 2: Franc Brglez , Hemang Lavana, A universal client for distributed networked design and computing, Proceedings of the 38th conference on Design automation, p.401-406, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378534]
• 3: BRGLEZ, F., LAVANA, H., GHOSH, D., ALLEN, B., CASSTEVENS, R., III, J. H., KURVE, R., PAGE, S., AND STALLMANN, M. 2000. OpenExperiment: A Configurable Environment for Collaborative Experimental Design and Execution on the Internet. Technical Report 2000-TR@CBL-02-Brglez (March), CBL, CS Dept., NCSU, Box 8206, Raleigh, NC 27695.
• 4: CHUNG, F. R. K. 1984. On optimal linear arrangement of trees. <i>Comp. and Maths. with Appls. 10,</i> 1, 43-60.
• 5: Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 6: EADES, P. AND KELLY, D. 1986. Heuristics for reducing crossings in 2-layered networks. <i>Ars Combinatoria 21-A,</i> 89-98.
• 7: EADES, P., MCKAY, B. D., AND WORMALD, N. C. 1976. On an Edge Crossing Problem. Technical report, Department of Computer Science, University of Newcastle, New South Wales 2308, Australia.
• 8: Peter Eades , Kozo Sugiyama, How to draw a directed graph, Journal of Information Processing, v.13 n.4, p.424-437, 1990
• 9: Peter Eades , Sue Whitesides, Drawing graphs in two layers, Theoretical Computer Science, v.131 n.2, p.361-374, Sept. 12, 1994 [doi>10.1016/0304-3975(94)90179-1]
• 10: EADES, P. AND WORMALD, N.C. 1994. Edge Crossings in Drawings of Bipartite Graphs. <i>Algorithmica 11,</i> 379-403.
• 11: E. R. Gansner , E. Koutsofios , S. C. North , K.-P. Vo, A Technique for Drawing Directed Graphs, IEEE Transactions on Software Engineering, v.19 n.3, p.214-230, March 1993 [doi>10.1109/32.221135]
• 12: GAREY, M. R. AND JOHNSON, D. S. 1983. Crossing Number is NP-complete. <i>SIAM J. Algebraic Discrete Methods 4,</i> 312-316.
• 13: Debabrata Ghosh , Paul Franzon , Franc Brglez, Generation of tightly controlled equivalence classes for experimental design of heuristics for graph-based np-hard problems, 2000
• 14: GHOSH, D. AND BRGLEZ, F. 1999. Equivalence Classes of Circuit Mutants for Experimental Design. In <i>IEEE 1999 International Symposium on Circuits and Systems - ISCAS'99</i> (May 1999). A reprint also accessible from http://www.cbl.ncsu.edu/experiments/- DoEArchives/1999-ISCAS.
• 15: GHOSH, D., BRGLEZ, F., AND STALLMANN, M. 1998a. First steps towards experimental design in evaluating layout algorithms: Wire length versus wire crossing in linear placement optimization. Technical Report 1998-TR@CBL-11-Ghosh (October), CBL, CS Dept., NCSU, Box 7550, Raleigh, NC 27695. Also available at http://www.cbl.ncsu.edu/- publications/#1998-TR@CBL-11-Ghosh.
• 16: GHOSH, D., BRGLEZ, F., AND STALLMANN, M. 1998b. Hypercrossing Number: A New and Effective Cost Function for Cell Placement Optimization. Technical Report 1998-TR@CBL- 12-Ghosh (December), CBL, CS Dept., NCSU, Box 7550, Raleigh, NC 27695. Also available at http://www.cbl.ncsu.edu/publications/#1998-TR@CBL-12-Ghosh.
• 17: D. Ghosh , N. Kapur , J. Harlow, III , F. Brglez, Synthesis of wiring signature-invariant equivalence class circuit mutants and applications to benchmarking, Proceedings of the conference on Design, automation and test in Europe, p.656-663, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 18: HARARY, F. AND SCHWENK, A. J. 1971. Trees with Hamiltonian Square. <i>Mathematika 18,</i> 138-140.
• 19: HARARY, F. AND SCHWENK, A. J. 1972. A New Crossing Number for Bipartite Graphs. <i>Utilitas Mathematica 1,</i> 203-209.
• 20: Patrick Healy , Ago Kuusik , Sebastian Leipert, Characterization of Level Non-planar Graphs by Minimal Patterns, Proceedings of the 6th Annual International Conference on Computing and Combinatorics, p.74-84, July 26-28, 2000
• 21: JÜNGER, M. AND MUTZEL, P. 1997. 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms. <i>Journal of Graph Algorithms and Applications (JGAA) 1,</i> 1, 1-25.
• 22: K. KOZMINSKI, (ED.). 1992. OASIS2.0 User's Guide. MCNC, Research Triangle Park, N.C. 27709. (Over 600 pages, distributed to over 60 teaching and research universities worldwide).
• 23: Nevin Kapur , Debabrata Ghosh , Franc Brglez, Towards a new benchmarking paradigm in EDA: analysis of equivalence class mutant circuit distributions, Proceedings of the 1997 international symposium on Physical design, p.136-143, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267704]
• 24: KERNIGHAN, B. W. AND LIN, S. 1970. An efficient heuristic procedure for partitioning graphs. <i>Bell System Technical Journal,</i> 291 - 307.
• 25: KNUTH, D. E. 1993. <i>The Stanford Graphbase.</i> Addison Wesley.
• 26: LEIGHTON, F. T. 1984. New Lower Bound Techniques for VLSI. <i>Math. Systems Theory 17,</i> 47-70.
• 27: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 28: MÄKINEN, E. 1989. A Note on the Median Heuristic for Drawing Bipartite Graphs. <i>Fundamenta Informaticae 12,</i> 563-570.
• 29: MÄKINEN, E. 1990. Experiments on drawing 2-level hierarchical graphs. <i>International Journal of Computer Mathematics 37,</i> 129-135.
• 30: MAREK-SADOWSKA, M. AND SARRAFZADEH, M. 1995. The Crossing Distribution Problem. <i>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 14,</i> 4 (April), 423-433.
• 31: Christian Matuszewski , Robby Schönfeld , Paul Molitor, Using Sifting for k -Layer Straightline Crossing Minimization, Proceedings of the 7th International Symposium on Graph Drawing, p.217-224, September 01, 1999
• 32: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 33: MUTZEL, P. 1998. The AGD-Library: Algorithms for Graph Drawing. Available from http://www.mpi-sb.mpg.de/~mutzel/dfgdraw/agdlib.html.
• 34: MUTZEL, P. 2001. Personal communication.
• 35: N. KAPUR. 1998. Cell Placement and Minimization of Crossing Numbers. Master's thesis, Electrical and Computer Engineering, North Carolina State University, Raleigh, N.C. Also available at http://www.cbl.ncsu.edu/publications/#1998-Thesis-MS-Kapur.
• 36: Edgar M. Palmer, Graphical evolution: an introduction to the theory of random graphs, John Wiley & Sons, Inc., New York, NY, 1985
• 37: Wolfgang Günther , Robby Schönfeld , Bernd Becker , Paul Molitor, k-Layer Straightline Crossing Minimization by Speeding Up Sifting, Proceedings of the 8th International Symposium on Graph Drawing, p.253-258, September 20-23, 2000
• 38: Farhad Shahrokhi , Ondrej Sýkora , László A. Székely , Imrich Vrt'o, A new lower bound for the bipartite crossing number with applications, Theoretical Computer Science, v.245 n.2, p.281-294, Aug. 28, 2000 [doi>10.1016/S0304-3975(99)00285-6]
• 39: Farhad Shahrokhi , Ondrej Sýkora , László A. Székely , Imrich Vrto, On Bipartite Drawings and the Linear Arrangement Problem, SIAM Journal on Computing, v.30 n.6, p.1773-1789, 2001 [doi>10.1137/S0097539797331671]
• 40: SHILOACH, Y. 1979. A minimum linear arrangement algorithm for undirected trees. <i>SIAM J. Computing 8,</i> 1, 15-32.
• 41: J. Spinrad , A. Brandstädt , L. Stewart, Bipartite permutation graphs, Discrete Applied Mathematics, v.18 n.3, p.279-292, Dec. 1987 [doi>10.1016/S0166-218X(87)80003-3]
• 42: STALLMANN, M., BRGLEZ, F., AND GHOSH, D. 1999a. Evaluating Iterative Improvement Heuristics for Bigraph Crossing Minimization. In <i>IEEE 1999 International Symposium on Circuits and Systems - ISCAS'99</i> (May 1999). A reprint also accessible from http://www.cbl.ncsu.edu/publications/#1999-ISCAS-Stallmann.
• 43: Matthias Stallmann , Franc Brglez , Debabrata Ghosh, Heuristics and Experimental Design for Bigraph Crossing Number Minimization, Selected papers from the International Workshop on Algorithm Engineering and Experimentation, p.74-93, January 15-16, 1999
• 44: C. D. Thompson, Area-time complexity for VLSI, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.81-88, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804401]
• 45: TUTTE, W. T. 1960. Convex Representations of Graphs. <i>Proc. London Math. Soc. 10,</i> 304- 320.
• 46: TUTTE, W. T. 1963. How to Draw a Graph. <i>Proc. London Math. Soc. 13,</i> 743-768.
• 47: WARFIELD, J. N. 1977. Crossing Theory and Hierarchy Mapping. <i>IEEE Transactions on Systems, Man, and Cybernetics SMC-7,</i> 7 (July), 505-523.
• 48: WEST, D. B. 1996. <i>Introduction to Graph Theory.</i> Prentice Hall.
• 49: YAMAGUCHI, A. AND SUGIMOTO, A. 1999. An approximation algorithm for the two-layered graph drawing problem. In <i>COCOON,</i> Number 1627 in LNCS (1999), pp. 81-91.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph labeling

General Terms:
Experimentation

Keywords:
crossing number, design of experiments, graph drawing, graph embedding, graph equivalence classes, layout