{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T02:07:38Z","timestamp":1725502058305},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540775362"},{"type":"electronic","value":"9783540775379"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77537-9_16","type":"book-chapter","created":{"date-parts":[[2008,1,30]],"date-time":"2008-01-30T09:50:55Z","timestamp":1201686655000},"page":"137-158","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of Several Realizability Problems for Abstract Topological Graphs"],"prefix":"10.1007","author":[{"given":"Jan","family":"Kyn\u010dl","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1-2","key":"16_CR1","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s00607-005-0133-3","volume":"76","author":"O. Aichholzer","year":"2006","unstructured":"Aichholzer, O., Aurenhammer, F., Krasser, H.: On the crossing number of complete graphs. Computing\u00a076(1-2), 165\u2013176 (2006)","journal-title":"Computing"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0020-0190(95)00020-D","volume":"54","author":"M. Chrobak","year":"1995","unstructured":"Chrobak, M., Payne, T.H.: A linear-time algorithm for drawing a planar graph on a grid. Information Processing Letters\u00a054, 241\u2013246 (1995)","journal-title":"Information Processing Letters"},{"key":"16_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/11917496_29","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"E. Gassner","year":"2006","unstructured":"Gassner, E., J\u00fcnger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous graph embeddings with fixed edges. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 325\u2013335. Springer, Heidelberg (2006)"},{"key":"16_CR4","first-page":"68","volume":"7","author":"R.K. Guy","year":"1960","unstructured":"Guy, R.K.: A combinatorial problem. Nabla (Bulletin of the Malayan Mathematical Society)\u00a07, 68\u201372 (1960)","journal-title":"Nabla (Bulletin of the Malayan Mathematical Society)"},{"key":"16_CR5","unstructured":"Harborth, H., Mengersen, I.: Drawings of the complete graph with maximum number of crossings. In: Proceedings of the Twenty-third Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Congressus Numerantium, Boca Raton, FL, vol.\u00a088, pp. 225\u2013228 (1992)"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0095-8956(91)90050-T","volume":"53","author":"J. Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: String graphs requiring exponential representations. Journal of Combinatorial Theory Ser. B\u00a053, 1\u20134 (1991)","journal-title":"Journal of Combinatorial Theory Ser. B"},{"issue":"2","key":"16_CR7","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/0404022","volume":"4","author":"J. Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J., Lubiw, A., Ne\u0161et\u0159il, J.: Noncrossing subgraphs in topological layouts. SIAM Journal on Discrete Mathematics\u00a04(2), 223\u2013244 (1991)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0095-8956(91)90090-7","volume":"52","author":"J. Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J.: String graphs I: The number of critical nonstring graphs is infinite. Journal of Combinatorial Theory Ser. B\u00a052, 53\u201366 (1991)","journal-title":"Journal of Combinatorial Theory Ser. B"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0095-8956(91)90091-W","volume":"51","author":"J. Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J.: String graphs II: Recognizing string graphs is NP-hard. Journal of Combinatorial Theory Ser. B\u00a051, 67\u201378 (1991)","journal-title":"Journal of Combinatorial Theory Ser. B"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(94)90143-0","volume":"52","author":"J. Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Applied Mathematics\u00a052, 233\u2013252 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/j.endm.2007.07.051","volume":"29","author":"J. Kyn\u010dl","year":"2007","unstructured":"Kyn\u010dl, J.: Enumeration of simple complete topological graphs. Electronic Notes in Discrete Mathematics\u00a029, 295\u2013299 (2007)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/11618058_25","volume-title":"Graph Drawing","author":"J. Kyn\u010dl","year":"2006","unstructured":"Kyn\u010dl, J., Valtr, P.: On edges crossing few other edges in simple topological complete graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol.\u00a03843, pp. 274\u2013284. Springer, Heidelberg (2006)"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00454-003-0012-9","volume":"30","author":"J. Pach","year":"2003","unstructured":"Pach, J., Solymosi, J., T\u00f3th, G.: Unavoidable configurations in complete topological graphs. Discrete and Computational Geometry\u00a030, 311\u2013320 (2003)","journal-title":"Discrete and Computational Geometry"},{"issue":"4","key":"16_CR14","first-page":"593","volume":"28","author":"J. Pach","year":"2002","unstructured":"Pach, J., T\u00f3th, G.: Recognizing string graphs is decidable. Discrete and computational geometry and graph drawing (Columbia, SC, 2001), Discrete and Computational Geometry\u00a028(4), 593\u2013606 (2002)","journal-title":"Discrete and computational geometry and graph drawing (Columbia, SC, 2001), Discrete and Computational Geometry"},{"key":"16_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/978-3-540-24595-7_5","volume-title":"Graph Drawing","author":"J. Pach","year":"2004","unstructured":"Pach, J., T\u00f3th, G.: How many ways can one draw a graph? In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 47\u201358. Springer, Heidelberg (2004)"},{"issue":"2","key":"16_CR16","doi-asserted-by":"publisher","first-page":"131","DOI":"10.2307\/2974980","volume":"104","author":"R.B. Richter","year":"1997","unstructured":"Richter, R.B., Thomassen, C.: Relations between crossing numbers of complete and complete bipartite graphs. Amer. Math. Monthly\u00a0104(2), 131\u2013137 (1997)","journal-title":"Amer. Math. Monthly"},{"key":"16_CR17","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0022-0000(03)00045-X","volume":"67","author":"M. Schaefer","year":"2003","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Recognizing string graphs in NP. Journal of Computer and System Sciences\u00a067, 365\u2013380 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/j.jcss.2003.07.002","volume":"68","author":"M. Schaefer","year":"2004","unstructured":"Schaefer, M., \u0160tefankovi\u010d, D.: Decidability of string graphs. Journal of Computer and System Sciences\u00a068, 319\u2013334 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/3-540-58950-3_364","volume-title":"Graph Drawing","author":"F. Shahrokhi","year":"1995","unstructured":"Shahrokhi, F., Sz\u00e9kely, L.A., Vrt\u2019o, I.: Crossing Numbers of Graphs, Lower Bound Techniques and Algorithms: A Survey. In: Tamassia, R., Tollis, I(Y.) G. (eds.) GD 1994. LNCS, vol.\u00a0894, pp. 131\u2013142. Springer, Heidelberg (1995)"},{"key":"16_CR20","first-page":"583","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"U. Wagner","year":"2003","unstructured":"Wagner, U.: On the rectilinear crossing number of complete graphs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, pp. 583\u2013588. ACM, New York (2003)"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77537-9_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:15:47Z","timestamp":1619507747000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77537-9_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540775362","9783540775379"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77537-9_16","relation":{},"subject":[]}}