{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,7]],"date-time":"2026-11-07T05:26:18Z","timestamp":1794029178785,"version":"4.8.0"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>The thickness of a graph $G=(V,E)$ with $n$ vertices is the minimum number of planar subgraphs of $G$ whose union is $G$. A polyline drawing of $G$ in $\\mathbb{R}^2$ is a drawing $\\Gamma$ of $G$, where each vertex is mapped to a point and each edge is mapped to a polygonal chain between the corresponding endpoints. Bend and layer complexities are two important aesthetics of such a drawing. The bend complexity of $\\Gamma$ is the maximum number of bends per edge in $\\Gamma$, and the layer complexity of $\\Gamma$ is the minimum integer $r$ such that the set of polygonal chains in $\\Gamma$ can be partitioned into $r$ disjoint sets, where each set corresponds to a planar polyline drawing. Let $G$ be a graph of thickness $t$. By F\u00e1ry's theorem, if $t=1$, then $G$ can be drawn on a single layer with bend complexity $0$. A few extensions to higher thickness are known, e.g., if $t=2$ (resp., $t&gt;2$), then $G$ can be drawn on $t$ planar layers with bend complexity 2 (resp., $3n+O(1)$). In this paper we present an elegant extension of F\u00e1ry's theorem to draw graphs of thickness $t&gt;2$. We first prove that thickness-$t$ graphs can be drawn on $t$ planar layers with $2.25n+O(1)$ bends per edge. We then develop another technique to draw thickness-$t$ graphs on $t$ planar layers with bend complexity $O(\\sqrt{2}^{t} \\cdot n^{1-(1\/\\beta)})$, where $\\beta = 2^{\\lceil (t-2)\/2 \\rceil }$. If $t$ is fixed, then this gives a sublinear bound on the bend complexity. Previously, the bend complexity was not known to be sublinear for any $t&gt;2$. Finally, we show that graphs with linear arboricity $k$ can be drawn on $k$ planar layers with bend complexity $\\frac{3(k-1)n}{(4k-2)}$. Note that we do not compute the edge-partition of the given graph into $t$ planar subgraphs or into $k$ linear forests, but we assume that such a partition is given as an input to our algorithm.<\/jats:p>","DOI":"10.1137\/16m1110042","type":"journal-article","created":{"date-parts":[[2018,11,27]],"date-time":"2018-11-27T14:59:35Z","timestamp":1543330775000},"page":"2703-2719","source":"Crossref","is-referenced-by-count":4,"title":["Relating Graph Thickness to Planar Layers and Bend Complexity"],"prefix":"10.1137","volume":"32","author":[{"given":"Stephane","family":"Durocher","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Debajyoti","family":"Mondal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,11,27]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.004"},{"key":"atypb2","unstructured":"Y. Bahoo, A. Biniaz, P. Cano, F. Chanchary, J. Iacono, K. Jain, E. Khramtcova, A. Lubiw, D. Mondal, K. Sheikhan, and C. D. Toth,\n                      Compatible paths on labelled point sets\n                      , in Proceedings of the 30th Canadian Conference on Computational Geometry, 2018."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050126"},{"key":"atypb4","first-page":"13","author":"Bar\u00e1t J.","year":"2006","journal-title":"Electron. J. Combin."},{"key":"atypb5","first-page":"349","author":"Bl\u00e4sius T.","year":"2013","journal-title":"Boca Raton, FL"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.05.006"},{"key":"atypb7","first-page":"20","author":"Bremner D.","year":"2018","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"key":"atypb8","unstructured":"I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, and D. Sangiorgi, EDS.\n                      Relating Graph Thickness to Planar Layers and Bend Complexity\n                      , LIPIcs Leibniz Int. Proc. Inform. 55, Schloss Dagstuhl, Leibniz-Zentrum f\u00fcr Informatik, 2016."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195907002276"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00023"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-1318-7"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.09.005"},{"key":"atypb13","first-page":"340","author":"Duncan C. A.","year":"2004","journal-title":"ACM"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2016.03.003"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195280319"},{"key":"atypb16","first-page":"75","author":"Eppstein D.","year":"2004","journal-title":"RI"},{"key":"atypb17","first-page":"463","volume":"2","author":"Erd\u00f6s P.","year":"1935","journal-title":"Compos. Math."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00113"},{"key":"atypb19","first-page":"229","volume":"11","author":"F\u00e1ry I.","year":"1948","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"atypb20","first-page":"166","author":"Frati F.","year":"2015","journal-title":"New York"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.04.002"},{"key":"atypb22","first-page":"413","author":"Giacomo E. Di","year":"2017","journal-title":"New York"},{"key":"atypb23","first-page":"299","author":"Gordon T.","year":"2012","journal-title":"New York"},{"key":"atypb24","first-page":"257","author":"Gutwenger C.","year":"2004","journal-title":"New York"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1953-0053256-2"},{"key":"atypb26","unstructured":"A. Lubiw and D. Mondal,\n                      On compatible triangulations with a minimum number of Steiner points\n                      , in Proceedings of the 29th Canadian Conference on Computational Geometry, J. Gudmundsson and M. H. M. Smid, eds., 2017, pp. 101-106."},{"key":"atypb27","unstructured":"D. Mondal,\n                      Visualizing Graphs: Optimization and Trade-Offs\n                      , Ph.D. thesis, University of Manitoba, Winnipeg, Canada, 2016."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007258"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00240-1"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1110042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:54:05Z","timestamp":1787316845000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1110042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1110042"],"URL":"https:\/\/doi.org\/10.1137\/16m1110042","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}