{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:33Z","timestamp":1740122373383,"version":"3.37.3"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,5,1]],"date-time":"2024-05-01T00:00:00Z","timestamp":1714521600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,5]],"date-time":"2024-05-05T00:00:00Z","timestamp":1714867200000},"content-version":"vor","delay-in-days":4,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["20K21827","20H05967"],"award-info":[{"award-number":["20K21827","20H05967"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["21H04871"],"award-info":[{"award-number":["21H04871"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJCR1402JST"],"award-info":[{"award-number":["JPMJCR1402JST"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004721","name":"The University of Tokyo","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004721","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the vertex proper coloring problem for highly restricted instances of geometric intersection graphs of line segments embedded in the plane. Provided a graph in the class UNIT-PURE-<jats:italic>k<\/jats:italic>-DIR, corresponding to intersection graphs of unit length segments lying in at most <jats:italic>k<\/jats:italic> directions with all parallel segments disjoint, and provided explicit coordinates for segments whose intersections induce the graph, we show for <jats:inline-formula><jats:alternatives><jats:tex-math>$$k = 4$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>4<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that it is <jats:italic>NP<\/jats:italic>-complete to decide if a proper 3-coloring exists, and moreover, <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\#P$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>#<\/mml:mo>\n                    <mml:mi>P<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete under many-one counting reductions to determine the number of such colorings. In addition, under the more relaxed constraint that segments have at most two distinct lengths, we show these same hardness results hold for finding and counting proper <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\left( k-1\\right) $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mfenced>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mfenced>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-colorings for every <jats:inline-formula><jats:alternatives><jats:tex-math>$$k \\ge 5$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>5<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. More generally, we establish that the problem of proper 3-coloring an arbitrary graph with <jats:italic>m<\/jats:italic> edges can be reduced in <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {O}}\\left( m^2\\right) $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mfenced>\n                      <mml:msup>\n                        <mml:mi>m<\/mml:mi>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:msup>\n                    <\/mml:mfenced>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time to the problem of proper 3-coloring a UNIT-PURE-4-DIR graph. This can then be shown to imply that no <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{o\\left( \\sqrt{n}\\right) }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mrow>\n                      <mml:mi>o<\/mml:mi>\n                      <mml:mfenced>\n                        <mml:msqrt>\n                          <mml:mi>n<\/mml:mi>\n                        <\/mml:msqrt>\n                      <\/mml:mfenced>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time algorithm can exist for proper 3-coloring PURE-4-DIR graphs under the Exponential Time Hypothesis (ETH), and by a slightly more elaborate construction, that no <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{o\\left( \\sqrt{n}\\right) }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mrow>\n                      <mml:mi>o<\/mml:mi>\n                      <mml:mfenced>\n                        <mml:msqrt>\n                          <mml:mi>n<\/mml:mi>\n                        <\/mml:msqrt>\n                      <\/mml:mfenced>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time algorithm can exist for counting the such colorings under the Counting Exponential Time Hypothesis (#ETH). Finally, we prove an <jats:italic>NP<\/jats:italic>-hardness result for the optimization problem of finding a maximum order proper 3-colorable induced subgraph of a UNIT-PURE-4-DIR graph.\n<\/jats:p>","DOI":"10.1007\/s10878-024-01149-3","type":"journal-article","created":{"date-parts":[[2024,5,5]],"date-time":"2024-05-05T13:01:36Z","timestamp":1714914096000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Proper colorability of segment intersection graphs"],"prefix":"10.1007","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5207-0375","authenticated-orcid":false,"given":"Robert D.","family":"Barish","sequence":"first","affiliation":[]},{"given":"Tetsuo","family":"Shibuya","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,5]]},"reference":[{"issue":"1","key":"1149_CR1","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10479-007-0178-0","volume":"153","author":"KI Aardal","year":"2007","unstructured":"Aardal KI, van Hoesel SPM, Koster AMCA, Mannino C, Sassano A (2007) Models and solution techniques for frequency assignment problems. Ann Oper Res 153(1):79\u2013129. https:\/\/doi.org\/10.1007\/s10479-007-0178-0","journal-title":"Ann Oper Res"},{"key":"1149_CR2","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.ipl.2018.05.002","volume":"137","author":"P Angelini","year":"2018","unstructured":"Angelini P, Lozzo GD (2018) 3-coloring arrangements of line segments with 4 slopes is hard. Inf Process Lett 137:47\u201350. https:\/\/doi.org\/10.1016\/j.ipl.2018.05.002","journal-title":"Inf Process Lett"},{"key":"1149_CR3","volume-title":"Antenna theory: analysis and design","author":"CA Balanis","year":"2016","unstructured":"Balanis CA (2016) Antenna theory: analysis and design. Wiley, Hoboken"},{"key":"1149_CR4","doi-asserted-by":"publisher","unstructured":"Barish RD, Shibuya T (2022) Proper colorability of segment intersection graphs. Proc 28th COCOON pp 573\u2013584, https:\/\/doi.org\/10.1007\/978-3-031-22105-7_51","DOI":"10.1007\/978-3-031-22105-7_51"},{"key":"1149_CR5","doi-asserted-by":"publisher","unstructured":"Biedl T, Kant G (1998) A better heuristic for orthogonal graph drawings. Comput Geom 9(3):159\u2013180. https:\/\/doi.org\/10.1016\/S0925-7721(97)00026-6","DOI":"10.1016\/S0925-7721(97)00026-6"},{"key":"1149_CR6","doi-asserted-by":"crossref","unstructured":"Bir\u00f3 C, Bonnet E, Marx D, Miltzow T, Rza\u0327$$\\dot{z}$$ewski, (2018) Fine-grained complexity of coloring unit disks and balls. J Comput Geom 9(2):47\u201380","DOI":"10.1007\/s00453-017-0387-0"},{"key":"1149_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph theory with applications","author":"JA Bondy","year":"1976","unstructured":"Bondy JA, Murty USR (1976) Graph theory with applications, 1st edn. New York, NY, Macmillan Press","edition":"1"},{"key":"1149_CR8","doi-asserted-by":"publisher","unstructured":"Bonnet E, Rza\u0327$$\\dot{\\rm z}$$ewski P, (2019) Optimality program in segment and string graphs. Algorithmica 81:3047\u20133073. https:\/\/doi.org\/10.1007\/s00453-019-00568-7","DOI":"10.1007\/s00453-019-00568-7"},{"issue":"1\u20132","key":"1149_CR9","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H Breu","year":"1998","unstructured":"Breu H, Kirkpatrick DG (1998) Unit disk graph recognition is NP-hard. Comput Geom 9(1\u20132):3\u201324. https:\/\/doi.org\/10.1016\/S0925-7721(97)00014-X","journal-title":"Comput Geom"},{"issue":"1","key":"1149_CR10","first-page":"1","volume":"24","author":"S Cabello","year":"2017","unstructured":"Cabello S, Jej\u010di\u010d M (2017) Refining the hierarchies of classes of geometric intersection graphs. Electron J Comb 24(1):1\u201319","journal-title":"Electron J Comb"},{"issue":"3","key":"1149_CR11","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 (2013) The clique problem in ray intersection graphs. Discrete Comput Geom 50(3):771\u2013783. https:\/\/doi.org\/10.1007\/s00454-013-9538-5","journal-title":"Discrete Comput Geom"},{"key":"1149_CR12","doi-asserted-by":"publisher","unstructured":"Chaplick S, Hell P, Otachi Y, Saitoh T, Uehara R (2014) Intersection dimension of bipartite graphs. Proc 11th TAMC pp 323\u2013340, https:\/\/doi.org\/10.1007\/978-3-319-06089-7_23","DOI":"10.1007\/978-3-319-06089-7_23"},{"issue":"1\u20133","key":"1149_CR13","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark BN, Colbourn CJ, Johnson DS (1990) Unit disk graphs. Discrete Math 86(1\u20133):165\u2013177. https:\/\/doi.org\/10.1016\/0012-365X(90)90358-O","journal-title":"Discrete Math"},{"issue":"3","key":"1149_CR14","doi-asserted-by":"publisher","first-page":"635","DOI":"10.7155\/jgaa.00265","volume":"16","author":"S Cornelsen","year":"2012","unstructured":"Cornelsen S, Karrenbauer A (2012) Accelerated bend minimization. J Graph Algorithms Appl 16(3):635\u2013650. https:\/\/doi.org\/10.7155\/jgaa.00265","journal-title":"J Graph Algorithms Appl"},{"key":"1149_CR15","unstructured":"Creignou N, Hermann M (1993) On #P-completeness of some counting problems. Research Report (RR-2144, INRIA) pp 1\u201310, https:\/\/hal.science\/inria-00074528\/"},{"key":"1149_CR16","doi-asserted-by":"publisher","unstructured":"Cygan M, Fomin FV, Golovnev A, Kulikov AS, Mihajlin I, Pachocki J, Soca\u0142a A (2016) Tight bounds for graph homomorphism and subgraph isomorphism. Proc 27th SODA pp 1643\u20131649, https:\/\/doi.org\/10.1137\/1.9781611974331.ch112","DOI":"10.1137\/1.9781611974331.ch112"},{"issue":"4","key":"1149_CR17","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1002\/dac.1348","volume":"26","author":"HN Dai","year":"2011","unstructured":"Dai HN, Ng KW, Li M, Wu MY (2011) An overview of using directional antennas in wireless networks. Int J Commun Syst 26(4):413\u2013448. https:\/\/doi.org\/10.1002\/dac.1348","journal-title":"Int J Commun Syst"},{"issue":"3","key":"1149_CR18","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0012-365X(80)90236-8","volume":"30","author":"DP Dailey","year":"1980","unstructured":"Dailey DP (1980) Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete. Discrete Math 30(3):289\u2013293. https:\/\/doi.org\/10.1016\/0012-365X(80)90236-8","journal-title":"Discrete Math"},{"issue":"4","key":"1149_CR19","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/2635812","volume":"10","author":"H Dell","year":"2014","unstructured":"Dell H, Husfeldt T, Marx D, Taslaman N, Wahl\u00e9n M (2014) Exponential time complexity of the permanent and the Tutte polynomial. ACM Trans Algorithms 10(4):21:1-21:32","journal-title":"ACM Trans Algorithms"},{"key":"1149_CR20","doi-asserted-by":"publisher","unstructured":"Deniz Z, Galby E, Munaro A, Ries B (2018) On contact graphs of paths on a grid. In: Proc 26th GD pp 317\u2013330, https:\/\/doi.org\/10.1007\/978-3-030-04414-5_22","DOI":"10.1007\/978-3-030-04414-5_22"},{"issue":"2","key":"1149_CR21","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1080\/00207168208803302","volume":"11","author":"AK Dewdney","year":"1982","unstructured":"Dewdney AK (1982) Linear time transformations between combinatorial problems. Int J Comput Math 11(2):91\u2013110. https:\/\/doi.org\/10.1080\/00207168208803302","journal-title":"Int J Comput Math"},{"key":"1149_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph theory","author":"R Diestel","year":"2017","unstructured":"Diestel R (2017) Graph theory, 5th edn. Heidelberg, Springer-Verlag","edition":"5"},{"issue":"1","key":"1149_CR23","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 RE (1976) Intersection graphs of curves in the plane. J Comb Theory Ser B 21(1):8\u201320. https:\/\/doi.org\/10.1016\/0095-8956(76)90022-8","journal-title":"J Comb Theory Ser B"},{"issue":"1","key":"1149_CR24","doi-asserted-by":"publisher","first-page":"51","DOI":"10.7151\/dmgt.1158","volume":"22","author":"A Eisenbl\u00e4tter","year":"2002","unstructured":"Eisenbl\u00e4tter A, Gr\u00f6tschel M, Koster AMCA (2002) Frequency planning and ramifications of coloring. Discuss Math Graph Theory 22(1):51\u201388. https:\/\/doi.org\/10.7151\/dmgt.1158","journal-title":"Discuss Math Graph Theory"},{"issue":"2","key":"1149_CR25","doi-asserted-by":"publisher","first-page":"15:1","DOI":"10.1145\/1497290.1497291","volume":"5","author":"D Eppstein","year":"2009","unstructured":"Eppstein D (2009) Testing bipartiteness of geometric intersection graphs. ACM Trans Algorithms 5(2):15:1-15:35. https:\/\/doi.org\/10.1145\/1497290.1497291","journal-title":"ACM Trans Algorithms"},{"key":"1149_CR26","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness, 1st edn. W. H. Freeman: New York, NY"},{"issue":"4","key":"1149_CR27","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"RL Graham","year":"1972","unstructured":"Graham RL (1972) An efficient algorith for determining the convex hull of a finite planar set. Inf Process Lett 1(4):132\u2013133. https:\/\/doi.org\/10.1016\/0020-0190(72)90045-2","journal-title":"Inf Process Lett"},{"issue":"12","key":"1149_CR28","doi-asserted-by":"publisher","first-page":"1497","DOI":"10.1109\/PROC.1980.11899","volume":"68","author":"WK Hale","year":"1980","unstructured":"Hale WK (1980) Frequency assignment: theory and applications. Proc IEEE 68(12):1497\u20131514. https:\/\/doi.org\/10.1109\/PROC.1980.11899","journal-title":"Proc IEEE"},{"issue":"2","key":"1149_CR29","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R (2001) On the complexity of k-SAT. J Comput Syst Sci 62(2):367\u2013375. https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"1149_CR30","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"DG Kirkpatrick","year":"1986","unstructured":"Kirkpatrick DG, Seidel R (1986) The ultimate planar convex hull algorithm? SIAM J Comput 15(1):287\u2013299. https:\/\/doi.org\/10.1137\/0215021","journal-title":"SIAM J Comput"},{"key":"1149_CR31","unstructured":"Knuth DE (2000) Dancing links. arXiv:cs\/0011047 pp 1\u201326"},{"key":"1149_CR32","doi-asserted-by":"publisher","unstructured":"Kratochv\u00edl J (1991) String graphs. II. Recognizing string graphs is NP-hard. J Comb Theory Ser B 52(1):67\u201378, https:\/\/doi.org\/10.1016\/0095-8956(91)90091-W","DOI":"10.1016\/0095-8956(91)90091-W"},{"issue":"3","key":"1149_CR33","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 (1994) A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl Math 52(3):233\u2013252. https:\/\/doi.org\/10.1016\/0166-218X(94)90143-0","journal-title":"Discrete Appl Math"},{"issue":"1\u20133","key":"1149_CR34","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 (1998) On intersection representations of co-planar graphs. Discrete Math 178(1\u20133):251\u2013255. https:\/\/doi.org\/10.1016\/S0012-365X(97)81834-1","journal-title":"Discrete Math"},{"issue":"2","key":"1149_CR35","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 (1994) Intersection graphs of segments. J Comb Theory Ser B 62(2):289\u2013315. https:\/\/doi.org\/10.1006\/jctb.1994.1071","journal-title":"J Comb Theory Ser B"},{"key":"1149_CR36","unstructured":"Kratochv\u00edl J, Ne\u0161et\u0159il J (1990) INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs. Comment Math Univ Carolinae 31(1):85\u201393, 10338.dmlcz\/106821"},{"issue":"3","key":"1149_CR37","first-page":"1","volume":"96","author":"J Kratochv\u00edl","year":"1986","unstructured":"Kratochv\u00edl J, Goljan M, Ku\u010dera P (1986) String graphs. Rozpr \u010cesk Akad V\u011bd, \u0158ada Mat P\u0159\u00edr V\u011bd 96(3):1\u201396","journal-title":"Rozpr \u010cesk Akad V\u011bd, \u0158ada Mat P\u0159\u00edr V\u011bd"},{"issue":"2","key":"1149_CR38","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis JM, Yannakakis M (1980) The node-deletion problem for hereditary properties is NP-complete. J Comput Syst Sci 20(2):219\u2013230. https:\/\/doi.org\/10.1016\/0022-0000(80)90060-4","journal-title":"J Comput Syst Sci"},{"issue":"2","key":"1149_CR39","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 (2008) Constructive generation of very hard 3-colorability instances. Discrete Appl Math 156(2):218\u2013229. https:\/\/doi.org\/10.1016\/j.dam.2006.07.015","journal-title":"Discrete Appl Math"},{"issue":"17","key":"1149_CR40","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 (2007) Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs. Discrete Appl Math 155(17):2383\u20132390. https:\/\/doi.org\/10.1016\/j.dam.2007.07.010","journal-title":"Discrete Appl Math"},{"issue":"1\u20132","key":"1149_CR41","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 IG (1998) Algorithms for area-efficient orthogonal drawings. Comput Geom 9(1\u20132):83\u2013110. https:\/\/doi.org\/10.1016\/S0925-7721(97)00017-5","journal-title":"Comput Geom"},{"key":"1149_CR42","volume-title":"Recent progress in combinatorics (W","author":"FS Roberts","year":"1969","unstructured":"Roberts FS (1969) On the boxicity and cubicity of a graph. In: Tutte T (ed) Recent progress in combinatorics (W. Academic Press, New York, NY"},{"key":"1149_CR43","unstructured":"Shamos MI (1978) Computational geometry. PhD thesis, Yale University"},{"issue":"9","key":"1149_CR44","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 FW (1966) Topology of thin film RC circuits. Bell Syst Tech J 45(9):1639\u20131662. https:\/\/doi.org\/10.1002\/j.1538-7305.1966.tb01713.x","journal-title":"Bell Syst Tech J"},{"issue":"2","key":"1149_CR45","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1002\/jgt.3190090210","volume":"9","author":"JE Steif","year":"1985","unstructured":"Steif JE (1985) The frame dimension and the complete overlap dimension of a graph. J Graph Theory 9(2):285\u2013299. https:\/\/doi.org\/10.1002\/jgt.3190090210","journal-title":"J Graph Theory"},{"issue":"4","key":"1149_CR46","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s00493-014-2942-5","volume":"34","author":"A Suk","year":"2014","unstructured":"Suk A (2014) Coloring intersection graphs of $$\\chi $$-monotone curves in the plane. Combinatorica 34(4):487\u2013505. https:\/\/doi.org\/10.1007\/s00493-014-2942-5","journal-title":"Combinatorica"},{"issue":"3","key":"1149_CR47","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"R Tamassia","year":"1987","unstructured":"Tamassia R (1987) On embedding a graph in the grid with the minimum number of bends. SIAM J Comput 16(3):421\u2013444. https:\/\/doi.org\/10.1137\/0216030","journal-title":"SIAM J Comput"},{"key":"1149_CR48","unstructured":"Toussaint G (1983) Solving geometric problems with the rotating calipers. Proc IEEE 1983 MELECON pp 1\u20138"},{"issue":"2","key":"1149_CR49","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant LG (1979) The complexity of computing the permanent. Theoret Comput Sci 8(2):189\u2013201","journal-title":"Theoret Comput Sci"},{"issue":"3","key":"1149_CR50","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant LG (1979) The complexity of enumeration and reliability problems. SIAM J Comput 8(3):410\u2013421","journal-title":"SIAM J Comput"},{"key":"1149_CR51","doi-asserted-by":"publisher","unstructured":"Vlasie DR (1995) Systematic generation of very hard cases for graph 3-colorability. Proc 7th ICTAI pp 114\u2013119, https:\/\/doi.org\/10.1109\/TAI.1995.479412","DOI":"10.1109\/TAI.1995.479412"},{"key":"1149_CR52","unstructured":"W A Stein et al (The SAGE Development Team) (2020) Sage Mathematics Software (Version 9.2.0). http:\/\/www.sagemath.org"},{"issue":"1\u20133","key":"1149_CR53","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 (1994) Chromatic scheduling and frequency assignment. Discrete Appl Math 49(1\u20133):165\u2013174. https:\/\/doi.org\/10.1016\/0166-218X(94)90207-0","journal-title":"Discrete Appl Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01149-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01149-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01149-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,17]],"date-time":"2024-05-17T13:11:50Z","timestamp":1715951510000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01149-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5]]},"references-count":53,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1149"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01149-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,5]]},"assertion":[{"value":"18 March 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors have not disclosed any competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"70"}}