{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T22:16:27Z","timestamp":1770070587406,"version":"3.49.0"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319687049","type":"print"},{"value":"9783319687056","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-68705-6_12","type":"book-chapter","created":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T06:06:22Z","timestamp":1509516382000},"page":"153-166","source":"Crossref","is-referenced-by-count":8,"title":["Intersection Graphs of Rays and Grounded Segments"],"prefix":"10.1007","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Felsner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tillmann","family":"Miltzow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Casey","family":"Tompkins","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Birgit","family":"Vogtenhuber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,11,2]]},"reference":[{"issue":"11","key":"12_CR1","doi-asserted-by":"crossref","first-page":"1607","DOI":"10.1073\/pnas.45.11.1607","volume":"45","author":"S Benzer","year":"1959","unstructured":"Benzer, S.: On the topology of the genetic fine structure. Proc. Nat. Acad. Sci. 45(11), 1607\u20131620 (1959)","journal-title":"Proc. Nat. Acad. Sci."},{"issue":"3","key":"12_CR2","doi-asserted-by":"crossref","first-page":"771","DOI":"10.1007\/s00454-013-9538-5","volume":"50","author":"S Cabello","year":"2013","unstructured":"Cabello, S., Cardinal, J., Langerman, S.: The clique problem in ray intersection graphs. Discrete Comput. Geom. 50(3), 771\u2013783 (2013)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"12_CR3","doi-asserted-by":"crossref","first-page":"P1.33","DOI":"10.37236\/6040","volume":"24","author":"S Cabello","year":"2017","unstructured":"Cabello, S., Jej\u010di\u010d, M.: Refining the hierarchies of classes of geometric intersection graphs. Electron. J. Combin. 24(1), P1.33 (2017)","journal-title":"Electron. J. Combin."},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Canny, J.F.: Some algebraic and geometric computations in PSPACE. In: Proceedings of STOC, pp. 460\u2013467. ACM (1988)","DOI":"10.1145\/62212.62257"},{"issue":"4","key":"12_CR5","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1145\/2852040.2852053","volume":"46","author":"J Cardinal","year":"2015","unstructured":"Cardinal, J.: Computational geometry column 62. ACM SIGACT News 46(4), 69\u201378 (2015)","journal-title":"ACM SIGACT News"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Chalopin, J., Gon\u00e7alves, D.: Every planar graph is the intersection graph of segments in the plane: extended abstract. In: Proceedings of STOC, pp. 631\u2013638. ACM (2009)","DOI":"10.1145\/1536414.1536500"},{"key":"12_CR7","unstructured":"Chaplick, S., Felsner, S., Hoffmann, U., Wiechert, V.: Grid intersection graphs and order dimension. arXiv:1512.02482 (2015)"},{"key":"12_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-319-06089-7_23","volume-title":"Theory and Applications of Models of Computation","author":"S Chaplick","year":"2014","unstructured":"Chaplick, S., Hell, P., Otachi, Y., Saitoh, T., Uehara, R.: Intersection dimension of bipartite graphs. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) TAMC 2014. LNCS, vol. 8402, pp. 323\u2013340. Springer, Cham (2014). doi: 10.1007\/978-3-319-06089-7_23"},{"issue":"1","key":"12_CR9","doi-asserted-by":"crossref","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. Comb. Theory Ser. B 21(1), 8\u201320 (1976)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"12_CR10","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1137\/130945284","volume":"28","author":"S Felsner","year":"2014","unstructured":"Felsner, S.: The order dimension of planar maps revisited. SIAM J. Discrete Math. 28(3), 1093\u20131101 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"12_CR11","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.comgeo.2016.05.001","volume":"60","author":"JM Keil","year":"2017","unstructured":"Keil, J.M., Mitchell, J.S.B., Pradhan, D., Vatshelle, M.: An algorithm for the maximum weight independent set problem on outerstring graphs. Comput. Geom. 60, 19\u201325 (2017)","journal-title":"Comput. Geom."},{"issue":"1","key":"12_CR12","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1006\/eujc.1997.0151","volume":"19","author":"AV Kostochka","year":"1998","unstructured":"Kostochka, A.V., Ne\u0161et\u0159il, J.: Coloring relatives of intervals on the plane, I: chromatic number versus girth. Eur. J. Comb. 19(1), 103\u2013110 (1998)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"12_CR13","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1006\/eujc.2000.0433","volume":"23","author":"AV Kostochka","year":"2002","unstructured":"Kostochka, A.V., Ne\u0161et\u0159il, J.: Colouring relatives of intervals on the plane, II: intervals and rays in two directions. Eur. J. Comb. 23(1), 37\u201341 (2002)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"12_CR14","doi-asserted-by":"crossref","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. J. Comb. Theory Ser. B 52(1), 53\u201366 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"12_CR15","doi-asserted-by":"crossref","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. J. Comb. Theory Ser. B 52(1), 67\u201378 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"12_CR16","doi-asserted-by":"crossref","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. J. Comb. Theory Ser. B 53(1), 1\u20134 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"12_CR17","doi-asserted-by":"crossref","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. J. Comb. Theory Ser. B 62(2), 289\u2013315 (1994)","journal-title":"J. Comb. Theory Ser. B"},{"key":"12_CR18","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002). doi: 10.1007\/978-1-4613-0039-7"},{"key":"12_CR19","unstructured":"Matou\u0161ek, J.: Intersection graphs of segments and $$\\exists \\mathbb{R}$$ \u2203 R . arXiv:1406.2636 (2014)"},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"McKee, T.A., McMorris, F.: Topics in Intersection Graph Theory. Society for Industrial and Applied Mathematics (1999)","DOI":"10.1137\/1.9780898719802"},{"key":"12_CR21","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/j.dam.2015.07.034","volume":"201","author":"I Musta\u0163\u0103","year":"2016","unstructured":"Musta\u0163\u0103, I., Nishikawa, K., Takaoka, A., Tayu, S., Ueno, S.: On orthogonal ray trees. Discrete Appl. Math. 201, 201\u2013212 (2016)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"12_CR22","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0012-365X(85)90117-7","volume":"54","author":"W Naji","year":"1985","unstructured":"Naji, W.: Reconnaissance des graphes de cordes. Discrete Math. 54(3), 329\u2013337 (1985)","journal-title":"Discrete Math."},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Rok, A., Walczak, B.: Outerstring graphs are $$\\chi $$ \u03c7 -bounded. In: Proceedings of SoCG, pp. 136\u2013143. ACM (2014)","DOI":"10.1145\/2582112.2582115"},{"key":"12_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-11805-0_32","volume-title":"Graph Drawing","author":"M Schaefer","year":"2010","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 334\u2013344. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-11805-0_32"},{"issue":"2","key":"12_CR25","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 67(2), 365\u2013380 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Shor, P.W.: Stretchability of pseudolines is NP-hard. In: Applied Geometry and Discrete Mathematics. DIMACS Series in DMTCS, vol. 4, pp. 531\u2013554. AMS (1990)","DOI":"10.1090\/dimacs\/004\/41"},{"issue":"15","key":"12_CR27","doi-asserted-by":"crossref","first-page":"1650","DOI":"10.1016\/j.dam.2010.06.002","volume":"158","author":"AMS Shrestha","year":"2010","unstructured":"Shrestha, A.M.S., Tayu, S., Ueno, S.: On orthogonal ray graphs. Discrete Appl. Math. 158(15), 1650\u20131659 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"9","key":"12_CR28","doi-asserted-by":"crossref","first-page":"1639","DOI":"10.1002\/j.1538-7305.1966.tb01713.x","volume":"45","author":"FW Sinden","year":"1966","unstructured":"Sinden, F.W.: Topology of thin film RC circuits. Bell Syst. Tech. J. 45(9), 1639\u20131662 (1966)","journal-title":"Bell Syst. Tech. J."},{"key":"12_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-642-20807-2_31","volume-title":"Integer Programming and Combinatoral Optimization","author":"JA Soto","year":"2011","unstructured":"Soto, J.A., Telha, C.: Jump number of two-directional orthogonal ray graphs. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 389\u2013403. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-20807-2_31"},{"key":"12_CR30","unstructured":"Wessel, W., P\u00f6schel, R.: On circle graphs. In: Sachs, H. (ed.) Graphs, Hypergraphs and Applications, pp. 207\u2013210. Teubner (1985)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-68705-6_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,20]],"date-time":"2020-10-20T22:53:09Z","timestamp":1603234389000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68705-6_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319687049","9783319687056"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68705-6_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}