{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T06:24:10Z","timestamp":1790749450346,"version":"4.1.0"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100013873","name":"Government of Ontario","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100013873","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["CCF-1228639"],"award-info":[{"award-number":["CCF-1228639"]}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an $n$-vertex graph embedded on a surface of genus $g$ with at most $k$ crossings per edge has treewidth $O(\\sqrt{(g+1)(k+1)n})$ and layered treewidth $O((g+1)k)$ and that these bounds are tight up to a constant factor. In the special case of $g=0$, so-called $k$-planar graphs, the treewidth bound is $O(\\sqrt{(k+1)n})$, which is tight and improves upon a known $O((k+1)^{3\/4}n^{1\/2})$ bound. Analogous results are proved for map graphs defined with respect to any surface. Finally, we show that for $g&lt;m$, every $m$-edge graph can be embedded on a surface of genus $g$ with $O((m\/(g+1))\\log^2 g)$ crossings per edge, which is tight to a polylogarithmic factor.<\/jats:p>","DOI":"10.1137\/16m1062879","type":"journal-article","created":{"date-parts":[[2017,4,25]],"date-time":"2017-04-25T11:42:19Z","timestamp":1493120539000},"page":"805-824","source":"Crossref","is-referenced-by-count":33,"title":["Structure of Graphs with Locally Restricted Crossings"],"prefix":"10.1137","volume":"31","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Eppstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,4,25]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.09.007"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1178"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20237"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506148"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, \u0141. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103433410"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077468"},{"key":"atypb10","unstructured":"E. D. Demaine and M.T. Hajiaghayi,\n                      Equivalence of local treewidth and linear local treewidth and its algorithmic applications\n                      , in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '04), 2004, SIAM, Philadelphia, pp. 840-849,http:\/\/dl.acm.org\/citation.cfm?id=982792.982919."},{"key":"atypb11","first-page":"511","author":"Dujmovic\u0301 V.","year":"2016","journal-title":"New York"},{"key":"atypb12","unstructured":"V. Dujmovic\u0301, P. Morin, and D. R. Wood,\n                      Layered Separators in Minor-Closed Graph Classes with Applications\n                      , preprint, arXiv:1306.1595, 2013."},{"key":"atypb13","volume":"2016","author":"Dujmovic\u0301 V.","year":"2015","journal-title":"Chic. J. Theoret. Comput. Sci."},{"key":"atypb14","unstructured":"Z. Dvora\u0301k and S. Norin,\n                      Treewidth of Graphs with Balanced Separations\n                      , preprint, arXiv:1408.3869, 2014."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.124"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-0010-x"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0037-9"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.06.004"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(68)80063-8"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"atypb23","first-page":"439","volume":"43","author":"Hoory S.","year":"2006","journal-title":"S.)"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.02.019"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215922"},{"key":"atypb27","first-page":"87","author":"Reed B. A.","year":"1997","journal-title":"Cambridge"},{"key":"atypb28","first-page":"85","author":"Reed B. A.","year":"2003","journal-title":"New York"},{"key":"atypb29","unstructured":"N. Robertson and P. D. Seymour,\n                      Graph minors\n                      I-XXIII, J. Combin. Theory Ser. B, 1983-2012."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"atypb31","volume":"2014","author":"Schaefer M.","journal-title":"Electron. J. Combin., DS21"},{"key":"atypb32","unstructured":"F. Shahrokhi,\n                      New representation results for planar graphs\n                      , in Proceedings of 29th European Workshop on Computational Geometry (EuroCG 2013), 2013, pp. 177-180."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/BF02086611"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1062879","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:24:19Z","timestamp":1787322259000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1062879"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1062879"],"URL":"https:\/\/doi.org\/10.1137\/16m1062879","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}