{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:14Z","timestamp":1759638434494},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540748380"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74839-7_23","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T09:55:58Z","timestamp":1196934958000},"page":"238-247","source":"Crossref","is-referenced-by-count":10,"title":["Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete"],"prefix":"10.1007","author":[{"given":"Martin","family":"Pergel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"23_CR1","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1006\/jctb.1994.1008","volume":"60","author":"A. Bouchet","year":"1994","unstructured":"Bouchet, A.: Circle graph obstructions. Journal of Combinatorial Theory, Series B\u00a060(1), 107\u2013144 (1994)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"23_CR2","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. Journal of Combinatorial Theory, Series B\u00a021, 8\u201320 (1976)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"23_CR3","unstructured":"Eschen, E.M., Spinrad, J.: An O(n) algorithm for circular-arc graph recognition. In: SODA, pp. 128\u2013137 (1993)"},{"key":"23_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"issue":"5-6","key":"23_CR5","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-6), 181\u2013188 (2000)","journal-title":"Information Processing Letters"},{"issue":"1","key":"23_CR6","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0166-218X(94)00136-2","volume":"66","author":"F. Gavril","year":"1996","unstructured":"Gavril, F.: Intersection graphs of helly families of subtrees. Discrete Appl. Math.\u00a066(1), 45\u201356 (1996)","journal-title":"Discrete Appl. Math."},{"key":"23_CR7","unstructured":"Gavril, F.: k-interval-filament graphs, Technical report 2004-30, DIMACS, Rutgers University (2004)"},{"key":"23_CR8","unstructured":"Chalopin, J., Goncalves, D., Ochem, P.: On graph classes defined by overlap and intersection models. In: 6th Czech-Slovak International Symposium on Combinatorics. Graph Theory, Algorithms and Applications (2006)"},{"key":"23_CR9","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-circl e graphs. Discrete Math.\u00a0163, 299\u2013305 (1997)","journal-title":"Discrete Math."},{"issue":"2","key":"23_CR10","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(2), 289\u2013315 (1994)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"23_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":"23_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/978-3-540-73545-8_14","volume-title":"Proceedings of COCOON 2007","author":"J. Kratochv\u00edl","year":"2007","unstructured":"Kratochv\u00edl, J., Pergel, M.: Geometric intersection graphs: Do short cycles help? In: Proceedings of COCOON 2007. LNCS, vol.\u00a04598, pp. 118\u2013128. Springer, Heidelberg (2007)"},{"key":"23_CR13","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":"23_CR14","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":"23_CR15","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"G. Lueker","year":"1976","unstructured":"Lueker, G., Rose, D., Tarjan, R.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput.\u00a05, 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"McKee, T.A., McMorris, F.R.: Topics on Intersection Graphs. SIAM (1999)","DOI":"10.1137\/1.9780898719802"},{"issue":"2","key":"23_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., Sedgewick, E., \u0160tefankovi\u010d, D.: Recognizing string graphs in NP. J. Comput. Syst. Sci.\u00a067(2), 365\u2013380 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the tenth annual ACM symposium on Theory of computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"23_CR19","doi-asserted-by":"crossref","unstructured":"Spinrad, J.: Efficient Graph Representations, American Mathematical Society (2003)","DOI":"10.1090\/fim\/019"},{"issue":"2","key":"23_CR20","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1006\/jagm.1994.1012","volume":"16","author":"J. Spinrad","year":"1994","unstructured":"Spinrad, J.: Recognition of circle graphs. J. Algorithms\u00a016(2), 264\u2013282 (1994)","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74839-7_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:42:33Z","timestamp":1619505753000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74839-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540748380"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74839-7_23","relation":{},"subject":[]}}