{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T12:43:14Z","timestamp":1725453794049},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387678"},{"type":"electronic","value":"9783642387685"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38768-5_41","type":"book-chapter","created":{"date-parts":[[2013,5,17]],"date-time":"2013-05-17T00:31:28Z","timestamp":1368750688000},"page":"458-468","source":"Crossref","is-referenced-by-count":0,"title":["A Linear Edge Kernel for Two-Layer Crossing Minimization"],"prefix":"10.1007","author":[{"given":"Yasuaki","family":"Kobayashi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hirokazu","family":"Maruta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yusuke","family":"Nakae","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hisao","family":"Tamaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"41_CR1","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"41_CR2","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. Journal of Algorithms\u00a021(2), 358\u2013402 (1996)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"41_CR3","first-page":"1","volume":"3","author":"M. Chimani","year":"2012","unstructured":"Chimani, M., Hungerl\u00e4nder, P., J\u00fcnger, M., Mutzel, P.: An SDP approach to multi-level crossing minimization. Journal of Experimental Algorithmics\u00a03(3), 1\u201316 (2012)","journal-title":"Journal of Experimental Algorithmics"},{"key":"41_CR4","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"2","key":"41_CR5","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00453-005-1181-y","volume":"45","author":"V. Dujmovi\u0107","year":"2006","unstructured":"Dujmovi\u0107, V., Fellows, M.R., Hallet, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Whitesides, S., Wood, D.R.: A fixed parameter approach to two-layer planarization. Algorithmica\u00a045(2), 159\u2013182 (2006)","journal-title":"Algorithmica"},{"issue":"2","key":"41_CR6","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s00453-007-9151-1","volume":"52","author":"V. Dujmovi\u0107","year":"2008","unstructured":"Dujmovi\u0107, V., Fellows, M.R., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Suderman, M., Whitesides, S., Wood, D.R.: On the parameterized complexity of layered graph drawing. Algorithmica\u00a052(2), 267\u2013292 (2008)","journal-title":"Algorithmica"},{"issue":"2","key":"41_CR7","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.jda.2006.12.008","volume":"6","author":"V. Dujmovi\u0107","year":"2008","unstructured":"Dujmovi\u0107, V., Fernau, H., Kaufmann, M.: Fixed parameter algorithms for one-sided crossing minimization revisited. Journal of Discrete Algorithms\u00a06(2), 313\u2013323 (2008)","journal-title":"Journal of Discrete Algorithms"},{"issue":"1","key":"41_CR8","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s00453-004-1093-2","volume":"40","author":"V. Dujmovi\u0107","year":"2004","unstructured":"Dujmovi\u0107, V., Whitesides, S.: An efficient fixed parameter tractable algorithm for 1-sided crossing minimization. Algorithmica\u00a040(1), 15\u201331 (2004)","journal-title":"Algorithmica"},{"key":"41_CR9","unstructured":"Eades, P., McKay, B.D., Wormald, N.C.: On an edge crossing problem. In: Proceedings of 9th Australian Computer Science Conference, pp. 327\u2013334 (1986)"},{"issue":"4","key":"41_CR10","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 drawings of bipartite graphs. Algorithmica\u00a011(4), 379\u2013403 (1994)","journal-title":"Algorithmica"},{"key":"41_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-642-19222-7_34","volume-title":"Combinatorial Algorithms","author":"H. Fernau","year":"2011","unstructured":"Fernau, H., Fomin, F.V., Lokshtanov, D., Mnich, M., Philip, G., Saurabh, S.: Ranking and drawing in subexponential time. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol.\u00a06460, pp. 337\u2013348. Springer, Heidelberg (2011)"},{"issue":"3","key":"41_CR12","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M.R. Garey","year":"1982","unstructured":"Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM. J. on Algebraic and Discrete Methods\u00a04(3), 312\u2013316 (1982)","journal-title":"SIAM. J. on Algebraic and Discrete Methods"},{"key":"41_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1007\/978-3-642-33090-2_59","volume-title":"Algorithms \u2013 ESA 2012","author":"Y. Kobayashi","year":"2012","unstructured":"Kobayashi, Y., Tamaki, H.: A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol.\u00a07501, pp. 683\u2013694. Springer, Heidelberg (2012)"},{"issue":"6","key":"41_CR14","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.A., Vrt\u2019o, I.: On bipartite Drawings and the linear arrangement problem. SIAM Journal on Computing\u00a030(6), 1773\u20131789 (2001)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"41_CR15","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J. Spinrad","year":"1987","unstructured":"Spinrad, J., Brandst\u00e4dt, A., Stewart, L.: Bipartite permutation graphs. Discrete Applied Mathematics\u00a018(3), 279\u2013292 (1987)","journal-title":"Discrete Applied Mathematics"},{"key":"41_CR16","unstructured":"Suderman, M.: Layered graph drawing. PhD thesis, School of Computer Science, McGill University Montr\u00e9al (2005)"},{"key":"41_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-540-73556-4_32","volume-title":"Combinatorial Optimization and Applications","author":"L. Zheng","year":"2007","unstructured":"Zheng, L., Buchheim, C.: A new exact algorithm for the two-sided crossing minimization problem. In: Dress, A.W.M., Xu, Y., Zhu, B. (eds.) COCOA 2007. LNCS, vol.\u00a04616, pp. 301\u2013310. Springer, Heidelberg (2007)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38768-5_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T22:17:10Z","timestamp":1557699430000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38768-5_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387678","9783642387685"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38768-5_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}