{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T14:27:00Z","timestamp":1648823220058},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540662273","type":"print"},{"value":"9783540485186","type":"electronic"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48518-x_5","type":"book-chapter","created":{"date-parts":[[2007,11,14]],"date-time":"2007-11-14T18:57:15Z","timestamp":1195066635000},"page":"74-93","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Heuristics and Experimental Design for Bigraph Crossing Number Minimization"],"prefix":"10.1007","author":[{"given":"Matthias","family":"Stallmann","sequence":"first","affiliation":[]},{"given":"Franc","family":"Brglez","sequence":"additional","affiliation":[]},{"given":"Debabrata","family":"Ghosh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,4,19]]},"reference":[{"key":"5_CR1","unstructured":"F. Brglez, Design of Experiments to Evaluate CAD Algorithms: Which Improvements Are Due to Improved Heuristic and Which Are Merely Due to Chance?, Tech. Rep. 1998-TR@CBL-04-Brglez, CBL, CS Dept., NCSU, Box 7550, Raleigh, NC 27695, April 1998. Also available at http:\/\/www.cbl.ncsu.edu\/publications\/#1998-TR@CBL-04-Brglez ."},{"key":"5_CR2","unstructured":"F. Brglez, N. Kapur, and D. Ghosh, A CBL PosterNote: Wire Crossing Problem and Benchmarking, aug 1997. Available from http:\/\/www.cbl.ncsu.edu\/DiscussionGroups\/Benchmark-reviews\/frm00002.html ."},{"key":"5_CR3","unstructured":"F. Brglez (Editor), A Brief Tour From The Home Page on WWW Statistical Experiment Archives: Benchmark Descriptions and Posted Solutions to NP-hard Problems, Tech. Rep. 1998-TR@CBL-01-Brglez, Version 1.0, CBL, CS Dept., NCSU, Box 7550, Raleigh, NC 27695, February 1998. Also available at http:\/\/www.cbl.ncsu.edu\/publications\/#1998-TR@CBL-01-Brglez ."},{"key":"5_CR4","unstructured":"G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999."},{"key":"5_CR5","first-page":"89","volume":"21-A","author":"P. Eades","year":"1986","unstructured":"P. Eades and D. Kelly, Heuristics for reducing crossings in 2-layered networks, Ars Combinatoria, 21-A (1986), pp. 89\u201398.","journal-title":"Ars Combinatoria"},{"key":"5_CR6","volume-title":"On an Edge Crossing Problem","author":"P. Eades","year":"1976","unstructured":"P. Eades, B. D. McKay, and N. C. Wormald, On an Edge Crossing Problem, tech. rep., Department of Computer Science, University of Newcastle, New South Wales 2308, Australia, 1976."},{"key":"5_CR7","first-page":"424","volume":"13","author":"P. Eades","year":"1990","unstructured":"P. Eades and K. Sugiyama, How to Draw a Directed Graph, Journal of Information Processing, 13 (1990), pp. 424\u2013437.","journal-title":"Journal of Information Processing"},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0304-3975(94)90179-1","volume":"131","author":"P. Eades","year":"1994","unstructured":"P. Eades and S. Whiteside, Drawing graphs in two layers, Theoretical Computer Science, 131 (1994), pp. 361\u2013374.","journal-title":"Theoretical Computer Science"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF01187020","volume":"11","author":"P. Eades","year":"1994","unstructured":"P. Eades and N. C. Wormald, Edge Crossings in Drawings of Bipartite Graphs, Algorithmica, 11 (1994), pp. 379\u2013403.","journal-title":"Algorithmica"},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1109\/32.221135","volume":"19","author":"E.R. Gansner","year":"1993","unstructured":"E.R. Gansner, E. Koutsifios, S.C. North and K.P. Vo, A Technique for Drawing Directed Graphs, IEEE Trans. Software Engg., 19 (1993), pp. 214\u2013230. The drawing package dot is available from http:\/\/www.research.att.com\/sw\/tools\/graphviz\/ .","journal-title":"IEEE Trans. Software Engg."},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M. R. Garey","year":"1983","unstructured":"M. R. Garey and D. S. Johnson, Crossing Number is NP-complete, SIAM J. Algebraic Discrete Methods, 4 (1983), pp. 312\u2013316.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"5_CR12","unstructured":"D. Ghosh, F. Brglez, and M. Stallmann, First steps towards experimental design in evaluating layout algorithms: Wire length versus wire crossing in linear placement optimization, Tech. Rep. 1998-TR@CBL-11-Ghosh, CBL, CS Dept., NCSU, Box 7550, Raleigh, NC 27695, October 1998. Also available at http:\/\/www.cbl.ncsu.edu\/publications\/#1998-TR@CBL-11-Ghosh ."},{"key":"5_CR13","unstructured":"\u2014, Hypercrossing number: A new and effective cost function for cell placement optimization, Tech. Rep. 1998-TR@CBL-12-Ghosh, CBL, CS Dept., NCSU, Box 7550, Raleigh, NC 27695, December 1998. Also available at http:\/\/www.cbl.ncsu.edu\/publications\/#1998-TR@CBL-12-Ghosh ."},{"key":"5_CR14","unstructured":"D. Ghosh, N. Kapur, J. E. Harlow, and F. Brglez, Synthesis of Wiring Signature-Invariant Equivalence Class Circuit Mutants and Applications to Benchmarking, in Proceedings, Design Automation and Test in Europe, Feb 1998, pp. 656\u2013663. Also available at http:\/\/www.cbl.ncsu.edu\/publications\/#1998-DATE-Ghosh ."},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1112\/S0025579300008494","volume":"18","author":"F. Harary","year":"1971","unstructured":"F. Harary and A. J. Schwenk, Trees with Hamiltonian Square, Mathematika, 18 (1971), pp. 138\u2013140.","journal-title":"Mathematika"},{"key":"5_CR16","first-page":"203","volume":"1","author":"F. Harary","year":"1972","unstructured":"\u2014, A New Crossing Number for Bipartite Graphs, Utilitas Mathematica, 1 (1972), pp. 203\u2013209.","journal-title":"Utilitas Mathematica"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"J. E. Harlow and F. Brglez, Design of Experiments in BDD Variable Ordering: Lessons Learned, in Proceedings of the International Conference on Computer Aided Design, ACM, Nov. 1998. Also available from http:\/\/www.cbl.ncsu.edu\/publications\/#1998-ICCAD-Harlow .","DOI":"10.1145\/288548.289103"},{"key":"5_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00001","volume":"1","author":"M. J\u00dcnger","year":"1997","unstructured":"M. J\u00dcnger and P. Mutzel, 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms, Journal of Graph Algorithms and Applications (JGAA), 1 (1997), pp. 1\u201325.","journal-title":"Journal of Graph Algorithms and Applications (JGAA)"},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01744433","volume":"17","author":"F. T. Leighton","year":"1984","unstructured":"F. T. Leighton, New Lower Bound Techniques for VLSI, Math. Systems Theory, 17 (1984), pp. 47\u201370.","journal-title":"Math. Systems Theory"},{"key":"5_CR20","doi-asserted-by":"crossref","first-page":"563","DOI":"10.3233\/FI-1989-12408","volume":"12","author":"E. M\u00c4kinen","year":"1989","unstructured":"E. M\u00c4kinen, A Note on the Median Heuristic for Drawing Bipartite Graphs, Fundamenta Informaticae, 12 (1989), pp. 563\u2013570.","journal-title":"Fundamenta Informaticae"},{"key":"5_CR21","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1080\/00207169008803941","volume":"37","author":"E. M\u00c4kinen","year":"1990","unstructured":"\u2014, Experiments on drawing 2-level hierarchical graphs, International Journal of Computer Mathematics, 37 (1990), pp. 129\u2013135.","journal-title":"International Journal of Computer Mathematics"},{"key":"5_CR22","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1109\/43.372368","volume":"14","author":"M. Marek-Sadowska","year":"1995","unstructured":"M. Marek-Sadowska and M. Sarrafzadeh, The Crossing Distribution Problem, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 14 (1995), pp. 423\u2013433.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"5_CR23","unstructured":"P. Mutzel, The AGD-Library: Algorithms for Graph Drawing, 1998. Available from http:\/\/www.mpi-sb.mpg.de\/~mutzel\/dfgdraw\/agdlib.html ."},{"key":"5_CR24","unstructured":"S. Yang, Logic Synthesis and Optimization Benchmarks User Guide, Tech. Rep. 1991-IWLS-UG-Saeyang, MCNC, Research Triangle Park, NC, January 1991. Now available from http:\/\/www.cbl.ncsu.edu\/publications\/#1991-IWLS-UG-Saeyang and benchmarks from http:\/\/www.cbl.ncsu.edu\/benchmarks\/Benchmarks-upto-1996.html ."},{"key":"5_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/3-540-63307-3_48","volume-title":"On bipartite drawings and the linear arrangement problem","author":"F. Shahrokhi","year":"1997","unstructured":"F. Shahrokhi, O. S\u00ddkora, L. A. SZ\u00c9kely, and I. Vrt\u2019o, On bipartite drawings and the linear arrangement problem, in Lecture Notes in Computer Science, no. 1467, Springer Verlag, 1997, pp. 55\u201368."},{"key":"5_CR26","doi-asserted-by":"crossref","unstructured":"C. D. Thompson, Area-Time complexity for VLSI, in Proceedings, 11th Annual ACM Symposium on Theory of Computing, May 1979, pp. 81\u201388.","DOI":"10.1145\/800135.804401"},{"key":"5_CR27","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1112\/plms\/s3-10.1.304","volume":"10","author":"W. T. Tutte","year":"1960","unstructured":"W. T. Tutte, Convex Representations of Graphs, Proc. London Math. Soc., 10 (1960), pp. 304\u2013320.","journal-title":"Proc. London Math. Soc."},{"key":"5_CR28","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1112\/plms\/s3-13.1.743","volume":"13","author":"W. T. Tutte","year":"1963","unstructured":"\u2014, How to Draw a Graph, Proc. London Math. Soc., 13 (1963), pp. 743\u2013768.","journal-title":"Proc. London Math. Soc."},{"key":"5_CR29","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1109\/TSMC.1977.4309760","volume":"SMC-7","author":"J. N. Warfield","year":"1977","unstructured":"J. N. Warfield, Crossing Theory and Hierarchy Mapping, IEEE Transactions on Systems, Man, and Cybernetics, SMC-7 (1977), pp. 505\u2013523.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics"}],"container-title":["Algorithm Engineering and Experimentation","Lecture Notes in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48518-X_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,27]],"date-time":"2021-08-27T18:20:18Z","timestamp":1630088418000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48518-X_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662273","9783540485186"],"references-count":29,"URL":"http:\/\/dx.doi.org\/10.1007\/3-540-48518-x_5","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"published":{"date-parts":[[1999]]},"assertion":[{"value":"19 April 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}