{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:26Z","timestamp":1781031446733,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"University of warsaw","award":["Excellence Initiative \u2013 Research University (IDUB)"],"award-info":[{"award-number":["Excellence Initiative \u2013 Research University (IDUB)"]}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2517033"],"award-info":[{"award-number":["CCF-2517033"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2237288"],"award-info":[{"award-number":["CCF-2237288"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"French National Research Agency","award":["ANR-21-CE48- 0014"],"award-info":[{"award-number":["ANR-21-CE48- 0014"]}]},{"DOI":"10.13039\/100018694","name":"HORIZON EUROPE Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["101206430"],"award-info":[{"award-number":["101206430"]}],"id":[{"id":"10.13039\/100018694","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","award":["54451"],"award-info":[{"award-number":["54451"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100020975","name":"Basic Algorithms Research Copenhagen, University of Copenhagen","doi-asserted-by":"publisher","award":["not available"],"award-info":[{"award-number":["not available"]}],"id":[{"id":"10.13039\/501100020975","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2021\/43\/D\/ST6\/03312"],"award-info":[{"award-number":["2021\/43\/D\/ST6\/03312"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800727","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"61-71","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Separator Theorem for Minor-Free Graphs in Linear Time"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1653-5822","authenticated-orcid":false,"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[{"name":"CNRS, ENS de Lyon, Universit\u00e9 Claude Bernard Lyon 1, Lyon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0861-6515","authenticated-orcid":false,"given":"Tuukka","family":"Korhonen","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8223-9944","authenticated-orcid":false,"given":"Hung","family":"Le","sequence":"additional","affiliation":[{"name":"University of Massachusetts at Amherst, Amherst, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3644-0879","authenticated-orcid":false,"given":"Jason","family":"Li","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8524-4036","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Masa\u0159\u00edk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Institute of Informatics, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/JGT.22937"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100254"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/s0894-0347-1990-1065053-0"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706593"},{"key":"e_1_3_2_1_5_1","unstructured":"\u00c9douard Bonnet Tuukka Korhonen Hung Le Jason Li and Tom\u00e1\u0161 Masa\u0159\u00edk. 2025. Separator Theorem for Minor-Free Graphs in Linear Time. arxiv:2512.01587."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718252"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/120866725"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"e_1_3_2_1_9_1","unstructured":"Kenichi Kawarabayashi. 2011. A separator theorem in minor-closed class of graphs. https:\/\/youtu.be\/xTEwQ6KgBdU?si=ZFII4GZWAIC_ywfj&t=1470 Talk at KAIST Graph Theory Day. Accessed: 2025-11-03"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.53"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.22"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746583"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538903"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167261"},{"key":"e_1_3_2_1_15_1","unstructured":"Philip N Klein and Shay Mozes. 2024. Optimization Algorithms for Planar Graphs. Book draft available at https:\/\/planarity.org\/"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.188"},{"key":"e_1_3_2_1_17_1","first-page":"37","article-title":"A lower bound for the Hadwiger number of a graph as a function of the average degree of its vertices","volume":"38","author":"Kostochka Alexandr","year":"1982","unstructured":"Alexandr Kostochka. 1982. A lower bound for the Hadwiger number of a graph as a function of the average degree of its vertices. Diskret. Analiz. Novosibirsk, 38 (1982), 37\u201358.","journal-title":"Diskret. Analiz. Novosibirsk"},{"key":"e_1_3_2_1_18_1","unstructured":"Richard Lipton and Ken Regan. 2010. Galactic Algorithms. https:\/\/rjlipton.com\/2010\/10\/23\/galactic-algorithms\/ Accessed: 2025-10-26"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00098"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Gary L. Miller. 1986. Finding small simple cycle separators for 2-connected planar graphs. J. Comput. System Sci. 265\u2013279. https:\/\/doi.org\/10.1016\/0022-0000(86)90030-9 Announced at STOC \u201984\u2019 10.1016\/0022-0000(86)90030-9","DOI":"10.1016\/0022-0000(86)90030-9"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237986"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch130"},{"key":"e_1_3_2_1_26_1","volume-title":"Smith","author":"Plotkin Serge","year":"1994","unstructured":"Serge Plotkin, Satish Rao, and Warren D. Smith. 1994. Shallow excluded minors and improved graph decompositions. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201994). 462\u2013470."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.17"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1597036.1597043"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.36"},{"key":"e_1_3_2_1_31_1","unstructured":"Jack Spalding-Jamieson. 2025. Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes. arxiv:2506.01228."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90006-0"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-26.4.256"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01594196"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.15"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","unstructured":"Christian Wulff-Nilsen. 2014. Faster separators for shallow minor-free graphs via dynamic approximate distance oracles. In International Colloquium on Automata Languages and Programming (ICALP \u201914). 1063\u20131074. https:\/\/doi.org\/10.1007\/978-3-662-43948-7_88 10.1007\/978-3-662-43948-7_88","DOI":"10.1007\/978-3-662-43948-7_88"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800727","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800727","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:03:48Z","timestamp":1781028228000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800727"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":37,"alternative-id":["10.1145\/3798129.3800727","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800727","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}