{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T08:00:12Z","timestamp":1743062412434,"version":"3.40.3"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031221040"},{"type":"electronic","value":"9783031221057"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-22105-7_51","type":"book-chapter","created":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T02:36:12Z","timestamp":1672540572000},"page":"573-584","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Proper Colorability of\u00a0Segment Intersection Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5207-0375","authenticated-orcid":false,"given":"Robert D.","family":"Barish","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1514-5766","authenticated-orcid":false,"given":"Tetsuo","family":"Shibuya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,1]]},"reference":[{"issue":"1","key":"51_CR1","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10479-007-0178-0","volume":"153","author":"KI Aardal","year":"2007","unstructured":"Aardal, K.I., van Hoesel, S.P.M., Koster, A.M.C.A., Mannino, C., Sassano, A.: Models and solution techniques for frequency assignment problems. Ann. Oper. Res. 153(1), 79\u2013129 (2007)","journal-title":"Ann. Oper. Res."},{"key":"51_CR2","volume-title":"Antenna Theory: Analysis and Design","author":"CA Balanis","year":"2016","unstructured":"Balanis, C.A.: Antenna Theory: Analysis and Design, 4th edn. Wiley, Hoboken (2016)","edition":"4"},{"issue":"3","key":"51_CR3","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0925-7721(97)00026-6","volume":"9","author":"T Biedl","year":"1998","unstructured":"Biedl, T., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159\u2013180 (1998)","journal-title":"Comput. Geom."},{"issue":"3","key":"51_CR4","doi-asserted-by":"publisher","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. Discret. Comput. Geom. 50(3), 771\u2013783 (2013)","journal-title":"Discret. Comput. Geom."},{"key":"51_CR5","doi-asserted-by":"crossref","unstructured":"Cabello, S., Jej\u010di\u010d, M.: Refining the hierarchies of classes of geometric intersection graphs. Electron. J. Comb. 24(1)(P1.33), 1\u201319 (2017)","DOI":"10.37236\/6040"},{"issue":"1","key":"51_CR6","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0096-0551(81)90048-5","volume":"6","author":"GJ Chaitin","year":"1981","unstructured":"Chaitin, G.J., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins, M.E., Markstein, P.W.: Register allocation via coloring. Comput. Lang. 6(1), 47\u201357 (1981)","journal-title":"Comput. Lang."},{"key":"51_CR7","doi-asserted-by":"crossref","unstructured":"Chaplick, S., Hell, P., Otachi, Y., Saitoh, T., Uehara, R.: Intersection dimension of bipartite graphs. In: Proceedings of TAMC, pp. 323\u2013340 (2014)","DOI":"10.1007\/978-3-319-06089-7_23"},{"issue":"3","key":"51_CR8","doi-asserted-by":"publisher","first-page":"635","DOI":"10.7155\/jgaa.00265","volume":"16","author":"S Cornelsen","year":"2012","unstructured":"Cornelsen, S., Karrenbauer, A.: Accelerated bend minimization. J. Graph Algorithms Appl. 16(3), 635\u2013650 (2012)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"51_CR9","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1002\/dac.1348","volume":"26","author":"HN Dai","year":"2011","unstructured":"Dai, H.N., Ng, K.W., Li, M., Wu, M.Y.: An overview of using directional antennas in wireless networks. Int. J. Commun. Syst. 26(4), 413\u2013448 (2011)","journal-title":"Int. J. Commun. Syst."},{"issue":"3","key":"51_CR10","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0012-365X(80)90236-8","volume":"30","author":"DP Dailey","year":"1980","unstructured":"Dailey, D.P.: Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete. Discret. Math. 30(3), 289\u2013293 (1980)","journal-title":"Discret. Math."},{"issue":"4B","key":"51_CR11","doi-asserted-by":"publisher","first-page":"3260","DOI":"10.1143\/JJAP.45.3260","volume":"45","author":"J Deguchi","year":"2006","unstructured":"Deguchi, J., Sugimura, T., Nakatani, Y., Fukushima, T., Koyanagi, M.: Quantitative derivation and evaluation of wire length distribution in three-dimensional integrated circuits using simulated quenching. Jpn. J. Appl. Phys. 45(4B), 3260\u20133265 (2006)","journal-title":"Jpn. J. Appl. Phys."},{"key":"51_CR12","doi-asserted-by":"crossref","unstructured":"Deniz, Z., Galby, E., Munaro, A., Ries, B.: On contact graphs of paths on a grid. In: Proceedings of GD, pp. 317\u2013330 (2018)","DOI":"10.1007\/978-3-030-04414-5_22"},{"issue":"1","key":"51_CR13","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. Comb. Theory. Ser. B 21(1), 8\u201320 (1976)","journal-title":"J. Comb. Theory. Ser. B"},{"key":"51_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st edn. W. H. Freeman, New York (1979)","edition":"1"},{"issue":"4","key":"51_CR15","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"RL Graham","year":"1972","unstructured":"Graham, R.L.: An efficient algorithm for determining the convex hull of a finite planar set. Inf. Process. Lett. 1(4), 132\u2013133 (1972)","journal-title":"Inf. Process. Lett."},{"issue":"12","key":"51_CR16","doi-asserted-by":"publisher","first-page":"1497","DOI":"10.1109\/PROC.1980.11899","volume":"68","author":"WK Hale","year":"1980","unstructured":"Hale, W.K.: Frequency assignment: theory and applications. Proc. IEEE 68(12), 1497\u20131514 (1980)","journal-title":"Proc. IEEE"},{"key":"51_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"issue":"1","key":"51_CR18","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"DG Kirkpatrick","year":"1986","unstructured":"Kirkpatrick, D.G., Seidel, R.: The ultimate planar convex hull algorithm? SIAM J. Comput. 15(1), 287\u2013299 (1986)","journal-title":"SIAM J. Comput."},{"key":"51_CR19","unstructured":"Knuth, D.E.: Dancing links. arXiv:cs\/0011047, pp. 1\u201326 (2000)"},{"key":"51_CR20","doi-asserted-by":"crossref","unstructured":"Kratochv\u00edl, J.: String graphs. II. Recognizing string graphs is NP-hard. J. Comb. Theory. Ser. B 52(1), 67\u201378 (1991)","DOI":"10.1016\/0095-8956(91)90091-W"},{"issue":"3","key":"51_CR21","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. Discret. Appl. Math. 52(3), 233\u2013252 (1994)","journal-title":"Discret. Appl. Math."},{"key":"51_CR22","unstructured":"Kratochv\u00edl, J., Goljan, M., Ku\u010dera, P.: String graphs. Rozpr. \u010cesk. Akad. V\u011bd, \u0158ada Mat. P\u0159\u00edr. V\u011bd 96(3), 1\u201396 (1986)"},{"issue":"1\u20133","key":"51_CR23","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0012-365X(97)81834-1","volume":"178","author":"J Kratochv\u00edl","year":"1998","unstructured":"Kratochv\u00edl, J., Kub\u011bna, A.: On intersection representations of co-planar graphs. Discret. Math. 178(1\u20133), 251\u2013255 (1998)","journal-title":"Discret. Math."},{"issue":"2","key":"51_CR24","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. J. Comb. Theory. Ser. B 62(2), 289\u2013315 (1994)","journal-title":"J. Comb. Theory. Ser. B"},{"issue":"1","key":"51_CR25","first-page":"85","volume":"31","author":"J Kratochv\u00edl","year":"1990","unstructured":"Kratochv\u00edl, J., Ne\u0161et\u0159il, J.: Independent set and clique problems in intersection-defined classes of graphs. Comment. Math. Univ. Carolinae 31(1), 85\u201393 (1990)","journal-title":"Comment. Math. Univ. Carolinae"},{"issue":"2","key":"51_CR26","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.dam.2006.07.015","volume":"156","author":"K Mizuno","year":"2008","unstructured":"Mizuno, K., Nishihara, S.: Constructive generation of very hard 3-colorability instances. Discret. Appl. Math. 156(2), 218\u2013229 (2008)","journal-title":"Discret. Appl. Math."},{"key":"51_CR27","doi-asserted-by":"crossref","unstructured":"Nahman, A., Fan, A., Chung, J., Reif, R.: Wire-length distribution of three-dimensional integrated circuits. In: Proceedings of IITC, pp. 233\u2013235 (1999)","DOI":"10.1109\/IITC.1999.787131"},{"issue":"17","key":"51_CR28","doi-asserted-by":"publisher","first-page":"2383","DOI":"10.1016\/j.dam.2007.07.010","volume":"155","author":"Y Otachi","year":"2007","unstructured":"Otachi, Y., Okamoto, Y., Yamazaki, K.: Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs. Discret. Appl. Math. 155(17), 2383\u20132390 (2007)","journal-title":"Discret. Appl. Math."},{"issue":"1\u20132","key":"51_CR29","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0925-7721(97)00017-5","volume":"9","author":"A Papakostas","year":"1998","unstructured":"Papakostas, A., Tollis, I.G.: Algorithms for area-efficient orthogonal drawings. Comput. Geom. 9(1\u20132), 83\u2013110 (1998)","journal-title":"Comput. Geom."},{"key":"51_CR30","volume-title":"Recent Progress in Combinatorics","author":"FS Roberts","year":"1969","unstructured":"Roberts, F.S.: On the boxicity and cubicity of a graph. In: Tutte, W.T. (ed.) Recent Progress in Combinatorics. Academic Press, New York (1969)"},{"key":"51_CR31","unstructured":"Shamos, M.I.: Computational geometry. Ph.D. thesis, Yale University (1978)"},{"issue":"9","key":"51_CR32","doi-asserted-by":"publisher","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."},{"issue":"2","key":"51_CR33","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1002\/jgt.3190090210","volume":"9","author":"JE Steif","year":"1985","unstructured":"Steif, J.E.: The frame dimension and the complete overlap dimension of a graph. J. Graph Theory 9(2), 285\u2013299 (1985)","journal-title":"J. Graph Theory"},{"issue":"4","key":"51_CR34","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s00493-014-2942-5","volume":"34","author":"A Suk","year":"2014","unstructured":"Suk, A.: Coloring intersection graphs of $$\\chi $$-monotone curves in the plane. Combinatorica 34(4), 487\u2013505 (2014)","journal-title":"Combinatorica"},{"key":"51_CR35","unstructured":"Toussaint, G.: Solving geometric problems with the rotating calipers. In: Proceedings of MELECON, pp. 1\u20138 (1983)"},{"key":"51_CR36","doi-asserted-by":"crossref","unstructured":"Vlasie, D.R.: Systematic generation of very hard cases for graph 3-colorability. In: Proceedings of ICTAI, pp. 114\u2013119 (1995)","DOI":"10.1109\/TAI.1995.479412"},{"key":"51_CR37","unstructured":"Stein, W.A., et. al. (The SAGE Development Team): Sage Mathematics Software (Version 9.2.0) (2020). http:\/\/www.sagemath.org"},{"issue":"1\u20133","key":"51_CR38","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0166-218X(94)90207-0","volume":"49","author":"D de Werra","year":"1994","unstructured":"de Werra, D., Gay, Y.: Chromatic scheduling and frequency assignment. Discret. Appl. Math. 49(1\u20133), 165\u2013174 (1994)","journal-title":"Discret. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-22105-7_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,11]],"date-time":"2024-10-11T09:38:13Z","timestamp":1728639493000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22105-7_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031221040","9783031221057"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22105-7_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shenzhen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 October 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 October 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon-conference.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"101","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"39","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"39% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}