{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:28:22Z","timestamp":1759638502768},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540735441"},{"type":"electronic","value":"9783540735458"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-73545-8_14","type":"book-chapter","created":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T09:44:11Z","timestamp":1187343851000},"page":"118-128","source":"Crossref","is-referenced-by-count":3,"title":["Geometric Intersection Graphs: Do Short Cycles Help?"],"prefix":"10.1007","author":[{"given":"Jan","family":"Kratochv\u00edl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Pergel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1\u20132","key":"14_CR1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H. Breu","year":"1998","unstructured":"Breu, H., Kirkpatrick, D.G.: Unit Disk Graph Recognition is NP-Hard. Comput. Geom. Theory and Applications\u00a09(1\u20132), 3\u201324 (1998)","journal-title":"Comput. Geom. Theory and Applications"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Brandstaedt, A., Le, V.B., Spinrad, J.: Graph Classes: A Survey. SIAM (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"14_CR3","unstructured":"Chalopin, J., Goncalves, D., Ochem, P.: Planar graphs are in 1-STRING. In: Proceedings of SODA 2007 (to appear)"},{"key":"14_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-540-70904-6_21","volume-title":"Graph Drawing","author":"C. Dangelmayr","year":"2007","unstructured":"Dangelmayr, C., Felsner, S.: Chordal Graphs as Intersection Graphs of Pseudosegments. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol.\u00a04372, pp. 208\u2013219. Springer, Heidelberg (2007)"},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/0095-8956(76)90022-8","volume":"21","author":"G. Ehrlich","year":"1976","unstructured":"Ehrlich, G., Even, S., Tarjan, R.E.: Intersection graphs of curves in the plane. J. Combin. Theory Ser. B.\u00a021, 8\u201320 (1976)","journal-title":"J. Combin. Theory Ser. B."},{"issue":"5\u20136","key":"14_CR6","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0020-0190(00)00025-9","volume":"73","author":"F. Gavril","year":"2000","unstructured":"Gavril, F.: Maximum weight independent sets and cliques in intersection graphs of filaments. Information Processing Letters\u00a073(5\u20136), 181\u2013188 (2000)","journal-title":"Information Processing Letters"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitriou, C.H.: The complexity of coloring circular arcs and chords. SIAM Journal of Algebraic and Discrete Methods 1(2) (1980)","DOI":"10.1137\/0601025"},{"key":"14_CR8","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1006\/jctb.1998.1846","volume":"74","author":"P. Hlin\u011bn\u00fd","year":"1998","unstructured":"Hlin\u011bn\u00fd, P.: Classes and recognition of curve contact graphs. J. Combin. Theory ser. B.\u00a074, 87\u2013103 (1998)","journal-title":"J. Combin. Theory ser. B."},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Koebe, M.: On a New Class of Intersection Graphs. In: Proceedings of the Fourth Czechoslovak Symposium on Combinatorics Prachatice, pp. 141\u2013143 (1990)","DOI":"10.1016\/S0167-5060(08)70618-6"},{"key":"14_CR10","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0012-365X(96)00344-5","volume":"163","author":"A. Kostochka","year":"1997","unstructured":"Kostochka, A., Kratochv\u00edl, J.: Covering and coloring polygon-circle graphs. Discrete Math.\u00a0163, 299\u2013305 (1997)","journal-title":"Discrete Math."},{"key":"14_CR11","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0095-8956(91)90091-W","volume":"52","author":"J. Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J.: String graphs. II. Recognizing string graphs is NP-hard. Journal of Combinatorial Theory, Series B\u00a052, 67\u201378 (1991)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"14_CR12","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. Discr. Appl. Math.\u00a052, 233\u2013252 (1994)","journal-title":"Discr. Appl. Math."},{"key":"14_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/3-540-62495-3_53","volume-title":"Graph Drawing","author":"J. Kratochv\u00edl","year":"1997","unstructured":"Kratochv\u00edl, J.: Intersection Graphs of Noncrossing Arc-Connected Sets in the Plane. In: North, S.C. (ed.) GD 1996. LNCS, vol.\u00a01190, pp. 257\u2013270. Springer, Heidelberg (1997)"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1006\/jctb.1994.1071","volume":"62","author":"J. Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: Intersection Graphs of Segments. Journal of Combinatorial Theory, Series B\u00a062, 289\u2013315 (1994)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"14_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/978-3-540-24595-7_6","volume-title":"Graph Drawing","author":"J. Kratochv\u00edl","year":"2004","unstructured":"Kratochv\u00edl, J., Pergel, M.: Two Results on Intersection Graphs of Polygons. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 59\u201370. Springer, Heidelberg (2004)"},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"McKee, T.A., McMorris, F.R.: Topics on Intersection Graphs, SIAM (1999)","DOI":"10.1137\/1.9780898719802"},{"key":"14_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/3-540-45848-4_20","volume-title":"Graph Drawing","author":"J. Pach","year":"2002","unstructured":"Pach, J., T\u00f3th, G.: Recognizing string graphs is decidable. In: Mutzel, P., J\u00fcnger, M., Leipert, S. (eds.) GD 2001. LNCS, vol.\u00a02265, pp. 247\u2013260. Springer, Heidelberg (2002)"},{"key":"14_CR18","unstructured":"Pergel, M.: Recognition of Polygon-circle Graphs and Graphs of Interval Filaments is NP-complete, in preparation"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Schaefer, M., \u0160tefankovi\u010d, D.: Decidability of string graphs, In: STOC, pp. 241\u2013 246 (2001)","DOI":"10.1145\/380752.380807"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Recognizing String Graphs in NP. In: STOC 2002, pp. 1\u20136 (2002)","DOI":"10.1145\/509907.509910"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Sinden, F.W.: Topology of thin film RC-circuits. Bell System Technological Journal, 1639\u20131662 (1966)","DOI":"10.1002\/j.1538-7305.1966.tb01713.x"},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Spinrad, J.: Efficient Graph Representations, Fields Institute Monographs 19, American Mathematical Society (2003)","DOI":"10.1090\/fim\/019"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73545-8_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T11:37:50Z","timestamp":1578483470000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73545-8_14"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540735441","9783540735458"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73545-8_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}