{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:16Z","timestamp":1759638196440},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540433095"},{"type":"electronic","value":"9783540458487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45848-4_10","type":"book-chapter","created":{"date-parts":[[2007,8,11]],"date-time":"2007-08-11T14:47:53Z","timestamp":1186843673000},"page":"115-123","source":"Crossref","is-referenced-by-count":22,"title":["One Sided Crossing Minimization Is NP-Hard for Sparse Graphs"],"prefix":"10.1007","author":[{"given":"Xavier","family":"Mu\u00f1oz","sequence":"first","affiliation":[]},{"given":"W.","family":"Unger","sequence":"additional","affiliation":[]},{"given":"Imrich","family":"Vrt\u2019o","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,2,21]]},"reference":[{"key":"10_CR1","unstructured":"Demetrescu, C., Finocchi, I.: Removing Cycles for Minimizing Crossings. J. Experimental Algorithmics. To appear"},{"key":"10_CR2","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for Visualization of Graphs. Prentice Hall (1999)"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF01187020","volume":"11","author":"P. Eades","year":"1994","unstructured":"Eades, P. Wormald, N.C.: Edge Crossings in Drawing Bipartite Graphs. Algorithmica 11 (1994) 379\u2013403","journal-title":"Algorithmica"},{"key":"10_CR4","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0304-3975(94)90179-1","volume":"131","author":"P. Eades","year":"1994","unstructured":"Eades, P., Whitesides, S.: Drawing Graphs in Two Layers. Theoretical Computer Science 131 (1994) 361\u2013374","journal-title":"Theoretical Computer Science"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M.R. Garey","year":"1983","unstructured":"Garey, M.R., and Johnson, D.S.: Crossing Number is NP-Complete. SIAM J. Algebraic and Discrete Methods 4 (1983) 312\u2013316","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"10_CR6","unstructured":"Gavril, F.: Some NP-Complete Problems on Graphs. In: 11th Conf. on Information Sciences and Systems. John Hopkins University Press, Baltimore (1977) 91\u201395"},{"key":"10_CR7","first-page":"11","volume":"1","author":"M. J\u00fcnger","year":"1999","unstructured":"J\u00fcnger, M., Mutzel, P.: 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms. J. Graph Algorithms and Algorithms 1 (1999) 11\u201325","journal-title":"J. Graph Algorithms and Algorithms"},{"key":"10_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/3-540-46648-7_22","volume-title":"Using Sifting for k-Layer Crossing Minimization","author":"C. Matuszewski","year":"1999","unstructured":"Matuszewski, C., Sch\u00f6nfeld, R., Molitor, P.: Using Sifting for k-Layer Crossing Minimization. In: 7th Intl. Symp. on Graph Drawing. Lecture Notes in Computer Science, Vol. 1731. Springer-Verlag, Berlin (1999) 217\u2013224"},{"key":"10_CR9","volume-title":"Encyclopedia of Optimization","author":"P. Mutzel","year":"2001","unstructured":"Mutzel, P.: Optimization in Leveled Graphs. In: Pardalos, M., Floudas, C.A. (eds.): Encyclopedia of Optimization. Kluwer, Dordrecht (2001)"},{"key":"10_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/3-540-63938-1_67","volume-title":"Which Aesthetic Has the Greatest Effect on Human Understanding?","author":"H. Purchase","year":"1997","unstructured":"Purchase, H.: Which Aesthetic Has the Greatest Effect on Human Understanding? In: 5th Intl. Symposium on Graph Drawing. Lecture Notes in Computer Science, Vol. 1353. Springer-Verlag, Berlin (1997) 248\u2013261"},{"key":"10_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-1697-8","volume-title":"VLSI Placement and Global Routing Using Simulated Annealing","author":"C. Sechen","year":"1988","unstructured":"Sechen, C.: VLSI Placement and Global Routing Using Simulated Annealing, Kluwer, Dordrecht (1988)"},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"1773","DOI":"10.1137\/S0097539797331671","volume":"30","author":"F. Shahrokhi","year":"2000","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L.A., Vrt\u2019o, I.: On Bipartite Drawings and the Linear Arrangement Problem. SIAM J. Computing 30 (2000) 1773\u20131789","journal-title":"SIAM J. Computing"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Stallmann, M., Brglez, F., Ghosh, D.: Heuristics, Experimental Subjects, and Treatment Evaluation in Bigraph Crossing Minimization. J. Experimental Algorithmics. To appear","DOI":"10.1145\/945394.945402"},{"key":"10_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-9763-6","volume-title":"Enumerative Combinatorics","author":"R. H. Stanley","year":"1986","unstructured":"Stanley, R. H.: Enumerative Combinatorics. Wadsworth & Brooks, Monterey (1986)"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"11","author":"K. Sugiyama","year":"1981","unstructured":"Sugiyama, K., Tagawa, S., Toda, M.: Methods for Visual Understanding of Hierarchical System Structures. IEEE Transactions on Systems, Man, and Cybernetics SMC-11 (1981) 109\u2013125","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics SMC"},{"key":"10_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/3-540-48686-0_8","volume-title":"An Approximation Algorithm for the Two-Layered Graph Drawing Problem","author":"A. Yamaguchi","year":"1999","unstructured":"Yamaguchi, A., Sugimoto, A.: An Approximation Algorithm for the Two-Layered Graph Drawing Problem. In: 5th Annual Intl. Conf. on Computing and Combinatorics. Lecture Notes in Computer Science, Vol. 1627. Springer-Verlag, Berlin (1999) 81\u201391"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45848-4_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T18:10:53Z","timestamp":1550772653000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45848-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540433095","9783540458487"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-45848-4_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}