{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T13:29:08Z","timestamp":1747402148191},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642190933"},{"type":"electronic","value":"9783642190940"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-19094-0_9","type":"book-chapter","created":{"date-parts":[[2011,2,10]],"date-time":"2011-02-10T06:21:40Z","timestamp":1297318900000},"page":"70-76","source":"Crossref","is-referenced-by-count":1,"title":["k-Level Crossing Minimization Is NP-Hard for Trees"],"prefix":"10.1007","author":[{"given":"Martin","family":"Harrigan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick","family":"Healy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"9_CR1","first-page":"1","volume":"1","author":"E. Albacea","year":"2006","unstructured":"Albacea, E.: A Linear Algorithm for Bipartite Drawing with Minimum Edge Crossings of Complete Binary Trees. Philippine Computing Journal\u00a01(1), 1\u20135 (2006)","journal-title":"Philippine Computing Journal"},{"key":"9_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/3-540-44969-8_5","volume-title":"Drawing Graphs","author":"O. Bastert","year":"2001","unstructured":"Bastert, O., Matuszewski, C.: Layered Drawings of Digraphs. In: Kaufmann, M., Wagner, D. (eds.) Drawing Graphs. LNCS, vol.\u00a02025, pp. 87\u2013120. Springer, Heidelberg (2001)"},{"issue":"1","key":"9_CR3","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0898-1221(84)90085-3","volume":"10","author":"F. Chung","year":"1984","unstructured":"Chung, F.: On Optimal Linear Arrangements of Trees. Computers and Mathematics with Applications\u00a010(1), 43\u201360 (1984)","journal-title":"Computers and Mathematics with Applications"},{"key":"9_CR4","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/945394.945396","volume":"6","author":"Camil Demestrescu","year":"2001","unstructured":"Demestrescu, C., Finocchi, I.: Breaking Cycles for Minimizing Crossings. Journal of Experimental Algorithmics\u00a06(2) (2001)","journal-title":"Journal of Experimental Algorithmics"},{"issue":"4","key":"9_CR5","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF01187020","volume":"11","author":"P. Eades","year":"1994","unstructured":"Eades, P., Wormald, N.: Edge Crossings in Drawings of Bipartite Graphs. Algorithmica\u00a011(4), 379\u2013403 (1994)","journal-title":"Algorithmica"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/3-540-36151-0_27","volume-title":"Graph Drawing","author":"T. Eschbach","year":"2002","unstructured":"Eschbach, T., G\u00fcnther, W., Drechsler, R., Becker, B.: Crossing Reduction by Windows Optimization. In: Kobourov, S., Goodrich, M. (eds.) GD 2002. LNCS, vol.\u00a02528, pp. 285\u2013294. Springer, Heidelberg (2002)"},{"issue":"3","key":"9_CR7","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M. Garey","year":"1983","unstructured":"Garey, M., Johnson, D.: Crossing Number is NP-complete. SIAM Journal on Algebraic and Discrete Methods\u00a04(3), 312\u2013316 (1983)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/3-540-46648-7_22","volume-title":"Graph Drawing","author":"C. Matuszewski","year":"1999","unstructured":"Matuszewski, C., Sch\u00f6nfeld, R., Molitor, P.: Using Sifting for k-Layer Straightline Crossing minimization. In: Kratochv\u00edl, J. (ed.) GD 1999. LNCS, vol.\u00a01731, pp. 217\u2013224. Springer, Heidelberg (1999)"},{"key":"9_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/3-540-45848-4_10","volume-title":"Graph Drawing","author":"X. Mu\u00f1oz","year":"2002","unstructured":"Mu\u00f1oz, X., Unger, W., Vr\u0165o, I.: One Sided Crossing Minimization is NP-Hard for Sparse Graphs. In: Kobourov, S., Goodrich, M. (eds.) GD 2002. LNCS, vol.\u00a02528, pp. 115\u2013123. Springer, Heidelberg (2002)"},{"issue":"6","key":"9_CR10","doi-asserted-by":"publisher","first-page":"1773","DOI":"10.1137\/S0097539797331671","volume":"30","author":"F. Shahrokhi","year":"2001","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L., Vr\u0165o, I.: On Bipartite Drawings and the Linear Arrangement Problem. SIAM Journal on Computing (SICOMP)\u00a030(6), 1773\u20131789 (2001)","journal-title":"SIAM Journal on Computing (SICOMP)"},{"issue":"3","key":"9_CR11","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1137\/0208033","volume":"8","author":"Y. Shiloach","year":"1979","unstructured":"Shiloach, Y.: A Minimum Linear Arrangement Algorithm for Undirected Trees. SIAM Journal on Computing (SICOMP)\u00a08(3), 422\u2013430 (1979)","journal-title":"SIAM Journal on Computing (SICOMP)"},{"issue":"2","key":"9_CR12","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 Systems. IEEE Transactions on Systems, Man, and Cybernetics\u00a011(2), 109\u2013125 (1981)","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19094-0_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,10,8]],"date-time":"2018-10-08T22:36:37Z","timestamp":1539038197000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19094-0_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642190933","9783642190940"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19094-0_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}