{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,14]],"date-time":"2025-11-14T03:51:08Z","timestamp":1763092268950},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401039"},{"type":"electronic","value":"9783642401046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40104-6_9","type":"book-chapter","created":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T01:36:30Z","timestamp":1373506590000},"page":"97-108","source":"Crossref","is-referenced-by-count":12,"title":["Parameterized Complexity of 1-Planarity"],"prefix":"10.1007","author":[{"given":"Michael J.","family":"Bannister","sequence":"first","affiliation":[]},{"given":"Sergio","family":"Cabello","sequence":"additional","affiliation":[]},{"given":"David","family":"Eppstein","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"9_CR1","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1016\/j.jtbi.2006.09.023","volume":"244","author":"T. Akutsu","year":"2007","unstructured":"Akutsu, T., Hayashida, M., Ching, W.-K., Ng, M.K.: Control of Boolean networks: Hardness results and algorithms for tree structured networks. J. Theor. Biol.\u00a0244(4), 670\u2013679 (2007), doi:10.1016\/j.jtbi.2006.09.023","journal-title":"J. Theor. Biol."},{"key":"9_CR2","unstructured":"Borodin, O.V.: Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs. Metody Diskret. Analiz.\u00a0(41), 12\u201326, 108 (1984)"},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-642-36763-2_29","volume-title":"Graph Drawing","author":"F.J. Brandenburg","year":"2013","unstructured":"Brandenburg, F.J., Eppstein, D., Glei\u00dfner, A., Goodrich, M.T., Hanauer, K., Reislhuber, J.: On the density of maximal 1-planar graphs. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol.\u00a07704, pp. 327\u2013338. Springer, Heidelberg (2013)"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing number and 1-planarity hard. CoRR abs\/1203.5944 (2012)","DOI":"10.1137\/120872310"},{"issue":"40-42","key":"9_CR5","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J. Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoretical Computer Science\u00a0411(40-42), 3736\u20133756 (2010), doi:10.1016\/j.tcs.2010.06.026","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"9_CR6","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s00453-004-1134-x","volume":"43","author":"Z.-Z. Chen","year":"2005","unstructured":"Chen, Z.-Z., Kouno, M.: A linear-time algorithm for 7-coloring 1-plane graphs. Algorithmica\u00a043(3), 147\u2013177 (2005), doi:10.1007\/s00453-004-1134-x","journal-title":"Algorithmica"},{"issue":"4-5","key":"9_CR7","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1016\/j.dam.2011.11.014","volume":"160","author":"J. Czap","year":"2012","unstructured":"Czap, J., Hud\u00e1k, D.: 1-planarity of complete multipartite graphs. Discrete Applied Mathematics\u00a0160(4-5), 505\u2013512 (2012), doi:10.1016\/j.dam.2011.11.014","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"9_CR8","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1002\/jgt.3190140406","volume":"14","author":"P. Damaschke","year":"1990","unstructured":"Damaschke, P.: Induced subgraphs and well-quasi-ordering. J. Graph Th.\u00a014(4), 427\u2013435 (1990), doi:10.1002\/jgt.3190140406","journal-title":"J. Graph Th."},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer (1999), doi:10.1007\/978-1-4612-0515-9","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"9_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-642-36763-2_30","volume-title":"Graph Drawing","author":"P. Eades","year":"2013","unstructured":"Eades, P., Hong, S.-H., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: Testing maximal 1-planarity of graphs with a rotation system in linear time. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol.\u00a07704, pp. 339\u2013345. Springer, Heidelberg (2013)"},{"key":"9_CR11","series-title":"Lecture Notes in Computer Science","first-page":"148","volume-title":"GD 2011","author":"P. Eades","year":"2011","unstructured":"Eades, P., Liotta, G.: Right angle crossing graphs and 1-planarity. In: Speckmann, B. (ed.) GD 2011. LNCS, vol.\u00a07034, pp. 148\u2013153. Springer, Heidelberg (2011)"},{"issue":"11","key":"9_CR12","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1109\/32.41334","volume":"15","author":"D. Fernandez-Baca","year":"1989","unstructured":"Fernandez-Baca, D.: Allocating modules to processors in a distributed system. IEEE Transactions on Software Engineering\u00a015(11), 1427\u20131436 (1989), doi:10.1109\/32.41334","journal-title":"IEEE Transactions on Software Engineering"},{"key":"9_CR13","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer (2006)"},{"issue":"1","key":"9_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-0010-x","volume":"49","author":"A. Grigoriev","year":"2007","unstructured":"Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica\u00a049(1), 1\u201311 (2007), doi:10.1007\/s00453-007-0010-x","journal-title":"Algorithmica"},{"key":"9_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/11534273_5","volume-title":"Algorithms and Data Structures","author":"J. Guo","year":"2005","unstructured":"Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of generalized vertex cover problems. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 36\u201348. Springer, Heidelberg (2005)"},{"issue":"3","key":"9_CR16","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1145\/828.322439","volume":"31","author":"Y. Gurevich","year":"1984","unstructured":"Gurevich, Y., Stockmeyer, L., Vishkin, U.: Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems. J. ACM\u00a031(3), 459\u2013473 (1984), doi:10.1145\/828.322439","journal-title":"J. ACM"},{"key":"9_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-642-32241-9_29","volume-title":"Computing and Combinatorics","author":"S.-H. Hong","year":"2012","unstructured":"Hong, S.-H., Eades, P., Liotta, G., Poon, S.-H.: F\u00e1ry\u2019s theorem for 1-planar graphs. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol.\u00a07434, pp. 335\u2013346. Springer, Heidelberg (2012)"},{"issue":"7","key":"9_CR18","doi-asserted-by":"publisher","first-page":"1319","DOI":"10.1016\/j.disc.2007.04.009","volume":"308","author":"V.P. Korzhik","year":"2008","unstructured":"Korzhik, V.P.: Minimal non-1-planar graphs. Discrete Mathematics\u00a0308(7), 1319\u20131327 (2008), doi:10.1016\/j.disc.2007.04.009","journal-title":"Discrete Mathematics"},{"issue":"1","key":"9_CR19","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1002\/jgt.21630","volume":"72","author":"V.P. Korzhik","year":"2013","unstructured":"Korzhik, V.P., Mohar, B.: Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing. J. Graph Th.\u00a072(1), 30\u201371 (2013), doi:10.1002\/jgt.21630","journal-title":"J. Graph Th."},{"issue":"3","key":"9_CR20","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"G.L. Miller","year":"1986","unstructured":"Miller, G.L.: Finding Small Simple Cycle Separators for 2-Connected Planar Graphs. J. Comput. Syst. Sci.\u00a032(3), 265\u2013279 (1986), doi:10.1016\/0022-0000(86)90030-9","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/978-3-642-27875-4_6","volume":"28","author":"J. Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics\u00a028, 115\u2013144 (2012), doi:10.1007\/978-3-642-27875-4","journal-title":"Algorithms and Combinatorics"},{"issue":"3","key":"9_CR22","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/BF01215922","volume":"17","author":"J. Pach","year":"1997","unstructured":"Pach, J., T\u00f3th, G.: Graphs drawn with few crossings per edge. Combinatorica\u00a017(3), 427\u2013439 (1997), doi:10.1007\/BF01215922","journal-title":"Combinatorica"},{"key":"9_CR23","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF02996313","volume":"29","author":"G. Ringel","year":"1965","unstructured":"Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg\u00a029, 107\u2013117 (1965), doi:10.1007\/BF02996313","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg"},{"key":"9_CR24","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/mana.19861250122","volume":"125","author":"H. Schumacher","year":"1986","unstructured":"Schumacher, H.: Zur Struktur 1-planarer Graphen. Mathematische Nachrichten\u00a0125, 291\u2013300 (1986)","journal-title":"Mathematische Nachrichten"},{"issue":"3","key":"9_CR25","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0378-8733(83)90028-X","volume":"5","author":"S.B. Seidman","year":"1983","unstructured":"Seidman, S.B.: Network structure and minimum degree. Social Networks\u00a05(3), 269\u2013287 (1983), doi:10.1016\/0378-8733(83)90028-X","journal-title":"Social Networks"},{"issue":"1","key":"9_CR26","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.disc.2009.07.016","volume":"310","author":"Y. Suzuki","year":"2010","unstructured":"Suzuki, Y.: Optimal 1-planar graphs which triangulate other surfaces. Discrete Mathematics\u00a0310(1), 6\u201311 (2010), doi:10.1016\/j.disc.2009.07.016","journal-title":"Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40104-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T14:22:59Z","timestamp":1557930179000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40104-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401039","9783642401046"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40104-6_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}