{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:20:28Z","timestamp":1761621628179,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":28,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3519984","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"303-316","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A subpolynomial approximation algorithm for graph crossing number in low-degree graphs"],"prefix":"10.1145","author":[{"given":"Julia","family":"Chuzhoy","sequence":"first","affiliation":[{"name":"Toyota Technological Institute at Chicago, USA"}]},{"given":"Zihan","family":"Tan","sequence":"additional","affiliation":[{"name":"University of Chicago, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"M. Ajtai V. Chv\u00e1tal M. Newborn and E. Szemer\u00e9di. 1982. Crossing-free subgraphs. Theory and Practice of Combinatorics 9\u201312.  M. Ajtai V. Chv\u00e1tal M. Newborn and E. Szemer\u00e9di. 1982. Crossing-free subgraphs. Theory and Practice of Combinatorics 9\u201312.","DOI":"10.1016\/S0304-0208(08)73484-4"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1333875.1334206"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9440-6"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.26"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Markus Chimani and Petr Hlin\u011bn\u1ef3. 2011. A tighter insertion-based approximation of the crossing number. In International Colloquium on Automata Languages and Programming. 122\u2013134.  Markus Chimani and Petr Hlin\u011bn\u1ef3. 2011. A tighter insertion-based approximation of the crossing number. In International Colloquium on Automata Languages and Programming. 122\u2013134.","DOI":"10.1007\/978-3-642-22006-7_11"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993678"},{"key":"e_1_3_2_1_8_1","unstructured":"Julia Chuzhoy Vivek Madan and Sepideh Mahabadi. 2016. Private Communication.  Julia Chuzhoy Vivek Madan and Sepideh Mahabadi. 2016. Private Communication."},{"key":"e_1_3_2_1_9_1","volume-title":"Towards Better Approximation of Graph Crossing Number. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). 73\u201384","author":"Chuzhoy Julia","year":"2020","unstructured":"Julia Chuzhoy , Sepideh Mahabadi , and Zihan Tan . 2020 . Towards Better Approximation of Graph Crossing Number. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). 73\u201384 . Julia Chuzhoy, Sepideh Mahabadi, and Zihan Tan. 2020. Towards Better Approximation of Graph Crossing Number. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). 73\u201384."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.80"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.88"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700373520"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0604033"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.09.009"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.77"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 164\u2013175","author":"Anastasios Sidiropoulos Kawarabayashi","year":"2019","unstructured":"Ken-ichi Kawarabayashi and Anastasios Sidiropoulos . 2019 . Polylogarithmic approximation for Euler genus on bounded degree graphs . In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 164\u2013175 . Ken-ichi Kawarabayashi and Anastasios Sidiropoulos. 2019. Polylogarithmic approximation for Euler genus on bounded degree graphs. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 164\u2013175."},{"volume-title":"Complexity issues in VLSI: optimal layouts for the shuffle-exchange graph and other networks","author":"Leighton F. T.","key":"e_1_3_2_1_18_1","unstructured":"F. T. Leighton . 1983. Complexity issues in VLSI: optimal layouts for the shuffle-exchange graph and other networks . MIT Press . F. T. Leighton. 1983. Complexity issues in VLSI: optimal layouts for the shuffle-exchange graph and other networks. MIT Press."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"volume-title":"Lectures on discrete geometry","author":"Matou\u0161ek J.","key":"e_1_3_2_1_20_1","unstructured":"J. Matou\u0161ek . 2002. Lectures on discrete geometry . Springer-Verlag . J. Matou\u0161ek. 2002. Lectures on discrete geometry. Springer-Verlag."},{"key":"e_1_3_2_1_21_1","first-page":"194","article-title":"Thirteen problems on crossing numbers","volume":"9","author":"Pach J.","year":"2000","unstructured":"J. Pach and G. T\u00f3th . 2000 . Thirteen problems on crossing numbers . Geombinatorics , 9 , 4 (2000), 194 \u2013 207 . J. Pach and G. T\u00f3th. 2000. Thirteen problems on crossing numbers. Geombinatorics, 9, 4 (2000), 194\u2013207.","journal-title":"Geombinatorics"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118748.3118943"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"R. B. Richter and G. Salazar. 2009. Crossing numbers. In Topics in Topological Graph Theory L. W. Beineke and R. J. Wilson (Eds.). Cambridge University Press 133\u2013150.  R. B. Richter and G. Salazar. 2009. Crossing numbers. In Topics in Topological Graph Theory L. W. Beineke and R. J. Wilson (Eds.). Cambridge University Press 133\u2013150.","DOI":"10.1017\/CBO9781139087223.010"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Marcus Schaefer. 2012. The graph crossing number and its variants: A survey. The electronic journal of combinatorics DS21\u2013Sep.  Marcus Schaefer. 2012. The graph crossing number and its variants: A survey. The electronic journal of combinatorics DS21\u2013Sep.","DOI":"10.37236\/2713"},{"key":"e_1_3_2_1_27_1","unstructured":"Anastasios Sidiropoulos. 2010. Personal communication.  Anastasios Sidiropoulos. 2010. Personal communication."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190010105"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519984","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519984","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:39Z","timestamp":1750268979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519984"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":28,"alternative-id":["10.1145\/3519935.3519984","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519984","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}