{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T10:13:25Z","timestamp":1775470405758,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1994,4,1]],"date-time":"1994-04-01T00:00:00Z","timestamp":765158400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1994,4]]},"DOI":"10.1007\/bf01187020","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T14:04:39Z","timestamp":1108735479000},"page":"379-403","source":"Crossref","is-referenced-by-count":201,"title":["Edge crossings in drawings of bipartite graphs"],"prefix":"10.1007","volume":"11","author":[{"given":"Peter","family":"Eades","sequence":"first","affiliation":[]},{"given":"Nicholas C.","family":"Wormald","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"CR2","first-page":"277","volume-title":"Lecture Notes in Computer Science, Vol. 246","author":"G. Di Battista","year":"1987","unstructured":"G. Di Battista and E. Nardelli,An Algorithm for Testing Planarity of Hierarchical Graphs, Lecture Notes in Computer Science, Vol. 246, Springer-Verlag, Berlin, 1987, pp. 277?289."},{"key":"CR3","unstructured":"B. Berger and P. Shor, Approximation Algorithms for the Maximum Acyclic Subgraph Problem,Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 1990, pp. 236?243."},{"key":"CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J. A. Bondy","year":"1976","unstructured":"J. A. Bondy and U. S. R. Murty,Graph Theory with Applications, Macmillan, New York, 1976."},{"key":"CR5","first-page":"89","volume":"21A","author":"P. Eades","year":"1986","unstructured":"P. Eades and D. Kelly, Heuristics for Reducing Crossings in 2-Layered Networks,Ars Combinatoria 21A (1986), 89?98.","journal-title":"Ars Combinatoria"},{"issue":"1","key":"CR6","first-page":"26-1","volume":"13","author":"P. Eades","year":"1991","unstructured":"P. Eades and X. Lin, Notes on the Layer Assignment Problem for Drawing Directed Graphs,Australian Computer Science Communications 13 (1) (1991), 26-1?26-10.","journal-title":"Australian Computer Science Communications"},{"key":"CR7","unstructured":"P. Eades, B. D. McKay, and N. Wormald, On an Edge Crossing Problem,Proceedings of the Ninth Australian Computer Science Conference, Australian National University, 1986, pp. 327?334."},{"key":"CR8","unstructured":"P. Eades, W. Smyth, and X. Lin, Heuristics for the Feedback Arc Set Problem, Technical Report 1-1989, School of Computing Science, Curtin University of Technology, 1989."},{"issue":"4","key":"CR9","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(4) (1990), 424?437.","journal-title":"Journal of Information Processing"},{"key":"CR10","unstructured":"P. Eades, R. Tamassia, G. Di Battista, and I. Tollis, Algorithms for Drawing Graphs: an Annotated Bibliography, available as \/pub\/gdbiblio.tex.z from wilma.cs.brown.edu (to appear inComputational Geometry: Theory and Applications)."},{"key":"CR11","unstructured":"P. Eades and N. Wormald, The Median Heuristic for Drawing 2-Layered Networks, Technical Report 69, Department of Computer Science, University of Queensland, 1986."},{"key":"CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979."},{"issue":"3","key":"CR13","doi-asserted-by":"crossref","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 Journal on Algebraic and Discrete Methods 4(3) (1983), 312?316.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"issue":"11","key":"CR14","doi-asserted-by":"crossref","first-page":"1047","DOI":"10.1002\/spe.4380181104","volume":"18","author":"E. R. Gasner","year":"1988","unstructured":"E. R. Gasner, S. C. North, and K. P. Vo, DAG-A Program that Draws Directed Graphs,Software Practice and Experience 18(11) (1988), 1047?1062.","journal-title":"Software Practice and Experience"},{"key":"CR15","unstructured":"D. Kelly, A View to Graph Layout Problems, Masters Thesis, Department of Computer Science, University of Queensland, 1987."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0012-365X(87)90008-2","volume":"63","author":"D. Kelly","year":"1987","unstructured":"D. Kelly, Fundamentals of Planar Ordered Sets,Discrete Mathematics 63 (1987), 197?216.","journal-title":"Discrete Mathematics"},{"key":"CR17","volume-title":"Technical Report A-1988-1","author":"E. Makinen","year":"1988","unstructured":"E. Makinen, Experiments of Drawing 2-Level Hierarchical Graphs, Technical Report A-1988-1. Department of Computer Science, University of Tampere, Finland, 1988."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"D. J. Rosencrantz","year":"1977","unstructured":"D. J. Rosencrantz, R. E. Stearns, and P. M. Lewis, An Analysis of Several Heuristics for the Traveling Salesman Problem,SIAM Journal of Computing 6 (1977), 563?581.","journal-title":"SIAM Journal of Computing"},{"issue":"1","key":"CR19","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/spe.4380170107","volume":"17","author":"L. A. Rowe","year":"1987","unstructured":"L. A. Rowe, M. Davis, E. Messinger, C. Meyer, C. Spirakis, and A. Tuan, A Browser for Directed Graphs,Software Practice and Experience 17(1) (1987), 61?76.","journal-title":"Software Practice and Experience"},{"key":"CR20","volume-title":"Research Report 45","author":"K. Sugiyama","year":"1984","unstructured":"K. Sugiyama, A Readability Requirement in Drawing Digraphs: Level Assignment and Edge Removal for Reducing the Total Length of Lines, Research Report 45, International Institute for Advanced Study of Social Information Science, Numazu, Japan, 1984."},{"key":"CR21","first-page":"52","volume-title":"Working Paper WP-82-97","author":"K. Sugiyama","year":"1982","unstructured":"K. Sugiyama, Drawing and Understanding Systems Structures: An Introduction to the SKETCH System, Working Paper WP-82-97, International Institute for Systems Analysis, Laxenburg, Austria, p. 52, 1982."},{"issue":"2","key":"CR22","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"11","author":"K. Sugiyama","year":"1981","unstructured":"K. Sugiyama, S. Tagawa, and M. Toda, Methods for Visual Understanding of Hierarchical System Structures,IEEE Transactions on Systems, Man and Cybernetics 11(2) (1981), 109?125.","journal-title":"IEEE Transactions on Systems, Man and Cybernetics"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1109\/21.87055","volume":"18","author":"R. Tamassia","year":"1988","unstructured":"R. Tamassia, C. Batini, and G. Di Battista, Automatic Graph Drawing and Readability of Diagrams,IEEE Transactions on Systems, Man and Cybernetics 18 (1988), 61?79.","journal-title":"IEEE Transactions on Systems, Man and Cybernetics"},{"key":"CR24","first-page":"217","volume":"2","author":"R. Tamassia","year":"1990","unstructured":"R. Tamassia, Drawing Algorithms for Planar st-Graphs,Australian Journal of Combinatorics 2 (1990), 217?236.","journal-title":"Australian Journal of Combinatorics"},{"key":"CR25","first-page":"171","volume-title":"Document Manipulation and Typography","author":"H. Trickey","year":"1988","unstructured":"H. Trickey, DRAG: A Graph Drawing System, inDocument Manipulation and Typography (Proceedings of the International Conference on Electronic Publishing, Nice, 1988) (ed. J. C. van Vliet), Cambridge University Press, Cambridge, 1988, pp. 171?182."},{"key":"CR26","first-page":"502","volume":"7","author":"J. N. Warfield","year":"1977","unstructured":"J. N. Warfield, Crossing Theory and Hierarchy Mapping,IEEE Transactions on Systems, Man and Cybernetics 7 (1977), 502?523.","journal-title":"IEEE Transactions on Systems, Man and Cybernetics"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01187020.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01187020\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01187020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T16:35:44Z","timestamp":1556728544000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01187020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,4]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1994,4]]}},"alternative-id":["BF01187020"],"URL":"https:\/\/doi.org\/10.1007\/bf01187020","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,4]]}}}