{"docId":10163,"paperId":8877,"url":"https:\/\/dmtcs.episciences.org\/8877","doi":"10.46298\/dmtcs.8877","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":658,"name":"vol. 24, no 2"}],"section":[{"sid":9,"title":"Graph Theory","description":[]}],"repositoryName":"arXiv","repositoryIdentifier":"2112.10025","repositoryVersion":5,"repositoryLink":"https:\/\/arxiv.org\/abs\/2112.10025v5","dateSubmitted":"2021-12-21 07:22:31","dateAccepted":"2022-09-26 08:40:49","datePublished":"2022-10-21 09:59:07","titles":["Improved product structure for graphs on surfaces"],"authors":["Distel, Marc","Hickingbotham, Robert","Huynh, Tony","Wood, David R."],"abstracts":["Dujmovi\\'c, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every graph $G$ with Euler genus $g$ there is a graph $H$ with treewidth at most 4 and a path $P$ such that $G\\subseteq H \\boxtimes P \\boxtimes K_{\\max\\{2g,3\\}}$. We improve this result by replacing \"4\" by \"3\" and with $H$ planar. We in fact prove a more general result in terms of so-called framed graphs. This implies that every $(g,d)$-map graph is contained in $ H \\boxtimes P\\boxtimes K_\\ell$, for some planar graph $H$ with treewidth $3$, where $\\ell=\\max\\{2g\\lfloor \\frac{d}{2} \\rfloor,d+3\\lfloor\\frac{d}{2}\\rfloor-3\\}$. It also implies that every $(g,1)$-planar graph (that is, graphs that can be drawn in a surface of Euler genus $g$ with at most one crossing per edge) is contained in $H\\boxtimes P\\boxtimes K_{\\max\\{4g,7\\}}$, for some planar graph $H$ with treewidth $3$."],"keywords":["Mathematics - Combinatorics"]}