article

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

Authors:

Matthias Stallmann,

Debabrata GhoshAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 6

Pages 8 - es

https://doi.org/10.1145/945394.945402

Published: 31 December 2001 Publication History

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

Supplementary Material

Software Suite (a8-stallmannn-software.tar)

The software suite accompanying the article is a Unix tar file, which includes the source code and the test files used in the article.

Download
1.77 MB

PS File (p8-stallmann.ps)

Download
2.87 MB

References

[1]

BETZ, V. AND ROSE, J. 1997. VPR: A New Packing, Placement and Routing Tool for FPGA Research. In <i>Proceedings of the 7th International Workshop on Field_Programmable Logic</i> (August 1997), pp. 213-222. Software and postscript of paper can be downloaded from http://www.eecg.toronto.edu/~vaughn/vpr/vpr.html.]]

Digital Library

[2]

BRGLEZ, F. AND LAVANA, H. 2001. A Universal Client for Distributed Networked Design and Computing. In <i>Proceedings of the 38th Design Automation Conference</i> (June 2001). Also available at http://www.cbl.ncsu.edu/publications/#2001-DAC-Brglez.]]

Digital Library

[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]

DI BATTISTA, G., EADES, P., TAMASSIA, R., AND TOLLIS, I. G. 1999. <i>Graph Drawing: Algorithms for the Visualization of Graphs.</i> Prentice Hall.]]

Digital Library

[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]

EADES, P. AND SUGIYAMA, K. 1990. How to Draw a Directed Graph. <i>Journal of Information Processing 13,</i> 424-437.]]

Digital Library

[9]

EADES, P. AND WHITESIDE, S. 1994. Drawing graphs in two layers. <i>Theoretical Computer Science 131,</i> 361-374.]]

Digital Library

[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. KOUTSIFIOS, S.C. NORTH AND K.P. VO. 1993. A Technique for Drawing Directed Graphs. <i>IEEE Trans. Software Engg. 19,</i> 214-230. The drawing package dot is available from http://www.research.att.com/sw/tools/graphviz/.]]

Digital Library

[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]

GHOSH, D. 2000. <i>Generation of Tightly Controlled Equivalence Classes for Experimental Design of Heuristics for Graph-Based NP-hard Problems.</i> Ph.D. thesis, Electrical and Computer Engineering, North Carolina State University, Raleigh, N.C. Also available at http://www.cbl.ncsu.edu/publications/#2000-Thesis-PhD-Ghosh.]]

Digital Library

[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]

GHOSH, D., KAPUR, N., HARLOT, J. E., AND BRGLEZ, F. 1998. Synthesis of Wiring Signature-Invariant Equivalence Class Circuit Mutants and Applications to Benchmarking. In <i>Proceedings, Design Automation and Test in Europe</i> (Feb 1998), pp. 656-663. Also available at http://www.cbl.ncsu.edu/publications/#1998-DATE-Ghosh.]]

Digital Library

[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]

HEALY, P., KUUSIK, A., AND LEIPERT, S. 2000. Characterization of level non-planar graphs by minimal patterns. In <i>COCOON,</i> Number 1858 in LNCS (2000), pp. 74-84.]]

Digital Library

[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]

KAPUR, N., GHOSH, D., AND BRGLEZ, F. 1997. Towards A New Benchmarking Paradigm in EDA: Analysis of Equivalence Class Mutant Circuit Distributions. In <i>ACM International Symposium on Physical Design</i> (April 1997).]]

Digital Library

[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]

LEIGHTON, F. T. 1992. <i>Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes.</i> Morgan Kaufmann.]]

Digital Library

[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]

MATUSZEWSKI, C., SCHÖNFELD, R., AND MOLITOR, P. 1999. Using sifting for k-layer straightline crossing minimization. In <i>Proc. 7th Graph Drawing Conference,</i> Number 1731 in LNCS (1999), pp. 217-224.]]

[32]

MEHLHORN, K. AND NÄHER, S. 1999. <i>LEDA: A Platform for Combinatorial and Geometric Computing.</i> Cambridge University Press.]]

Digital Library

[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]

PALMER, E. M. 1985. <i>Graphical Evolution: An Introduction to the Theory of Random Graphs.</i> John Wiley and Sons.]]

Digital Library

[37]

SCHÖNFELD, R., GÜNTER, W., BECKER, B., AND MOLITOR, P. 2000. K-layer straightline crossing minimization by soeeding up sifting. In <i>Proc. 8th Graph Drawing Conference,</i> Number 1984 in LNCS (2000), pp. 253-258.]]

Digital Library

[38]

SHAHROKHI, F., SÝKORA, O., SZÉKELY, L. A., AND VRTO, I. 2000. A new lower bound for bipartite crossing number with applications. <i>Theoretical Computer Science.</i> To appear.]]

Digital Library

[39]

SHAHROKHI, F., SÝKORA, O., SZÉKELY, L. A., AND VRTO, I. 2001. On bipartite drawing and the linear arrangement problem. <i>SIAM J. Computing.</i> To appear. Preliminary version was published in WADS'97.]]

Digital Library

[40]

SHILOACH, Y. 1979. A minimum linear arrangement algorithm for undirected trees. <i>SIAM J. Computing 8,</i> 1, 15-32.]]

[41]

SPINRAD, J., BRANDSTÄDT, A., AND STEWART, L. 1987. Bipartite permutation graphs. <i>Discrete Applied Mathematics 19,</i> 279-292.]]

[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]

STALLMANN, M., BRGLEZ, F., AND GHOSH, D. 1999b. Heuristics and Experimental Design for Bigraph Crossing Number Minimization. In <i>Algorithm Engineering and Experimentation (ALENEX'99),</i> Number 1619 in Lecture Notes in Computer Science (1999), pp. 74-93. Springer Verlag. Also available at http://www.cbl.ncsu.edu/publications/- #1999-ALENEX-Stallmann.]]

Digital Library

[44]

THOMPSON, C. D. 1979. Area-Time complexity for VLSI. In <i>Proceedings, 11th Annual ACM Symposium on Theory of Computing</i> (May 1979), pp. 81-88.]]

Digital Library

[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.]]

Cited By

Peng BLiu DLü ZMartí RDing J(2020)Adaptive memory programming for the dynamic bipartite drawing problemInformation Sciences: an International Journal10.1016/j.ins.2019.12.077517:C(183-197)Online publication date: 1-May-2020
https://dl.acm.org/doi/10.1016/j.ins.2019.12.077
Palubeckis GTomkevičius AOstreika A(2019)Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimizationApplied Mathematics and Computation10.1016/j.amc.2018.11.051348(84-101)Online publication date: May-2019
https://doi.org/10.1016/j.amc.2018.11.051
(2018)Tabu search for the dynamic Bipartite Drawing ProblemComputers and Operations Research10.1016/j.cor.2017.10.01191:C(1-12)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1016/j.cor.2017.10.011
Show More Cited By

Index Terms

Heuristics, Experimental Subjects, and Treatment Evaluation in Bigraph Crossing Minimization
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph enumeration

Recommendations

Improvement on the Crossing Number of Crossing-Critical Graphs
Abstract
The crossing number of a graph G is the minimum number of edge crossings over all drawings of G in the plane. A graph G is k-crossing-critical if its crossing number is at least k, but if we remove any edge of G, its crossing number drops below k. ... $\sqrt{}$
Adding one edge to planar graphs makes crossing number hard
SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometry

A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show that it is NP-hard to compute the crossing number of near-planar graphs. The main idea in the reduction is to consider the problem of simultaneously drawing two ...
Crossing-number critical graphs have bounded path-width

The crossing number of a graph G, denoted by cr(G), is defined as the smallest possible number of edge-crossings in a drawing of G in the plane. A graph G is crossing-critical if cr(G - e)<cr(G) for all edges e of G. We prove that crossing-critical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 6, Issue

2001

313 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/945394

Issue’s Table of Contents

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 December 2001

Published in JEA Volume 6

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
780
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)3

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Peng BLiu DLü ZMartí RDing J(2020)Adaptive memory programming for the dynamic bipartite drawing problemInformation Sciences: an International Journal10.1016/j.ins.2019.12.077517:C(183-197)Online publication date: 1-May-2020
https://dl.acm.org/doi/10.1016/j.ins.2019.12.077
Palubeckis GTomkevičius AOstreika A(2019)Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimizationApplied Mathematics and Computation10.1016/j.amc.2018.11.051348(84-101)Online publication date: May-2019
https://doi.org/10.1016/j.amc.2018.11.051
(2018)Tabu search for the dynamic Bipartite Drawing ProblemComputers and Operations Research10.1016/j.cor.2017.10.01191:C(1-12)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1016/j.cor.2017.10.011
Stallmann M(2012)A heuristic for bottleneck crossing minimization and its performance on general crossing minimizationACM Journal of Experimental Algorithmics10.1145/2133803.221231417(1.1-1.30)Online publication date: 19-Jul-2012
https://dl.acm.org/doi/10.1145/2133803.2212314
Khan SBilal MSharif MKhan F(2011)A solution to bipartite drawing problem using genetic algorithmProceedings of the Second international conference on Advances in swarm intelligence - Volume Part I10.5555/2026282.2026355(530-538)Online publication date: 12-Jun-2011
https://dl.acm.org/doi/10.5555/2026282.2026355
Bae JWatson B(2011)Developing and Evaluating Quilts for the Depiction of Large Layered GraphsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2011.18717:12(2268-2275)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1109/TVCG.2011.187
Khan SBilal MSharif MKhan F(2011)A Solution to Bipartite Drawing Problem Using Genetic AlgorithmAdvances in Swarm Intelligence10.1007/978-3-642-21515-5_63(530-538)Online publication date: 2011
https://doi.org/10.1007/978-3-642-21515-5_63
Erten CSözdinler M(2010)Improving performances of suboptimal greedy iterative biclustering heuristics via localizationBioinformatics10.1093/bioinformatics/btq47326:20(2594-2600)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1093/bioinformatics/btq473
Çakıroglu OErten CKarataş ÖSözdinler M(2009)Crossing minimization in weighted bipartite graphsJournal of Discrete Algorithms10.1016/j.jda.2008.08.0037:4(439-452)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1016/j.jda.2008.08.003
Çakiroğlu OErten CKaratas ÖSözdinler M(2007)Crossing minimization in weighted bipartite graphsProceedings of the 6th international conference on Experimental algorithms10.5555/1768570.1768584(122-135)Online publication date: 6-Jun-2007
https://dl.acm.org/doi/10.5555/1768570.1768584
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents