Relating Graph Thickness to Planar Layers and Bend Complexity
SIAM Journal on Discrete Mathematics · 2018-01 · 32 (4) · 2703-2719
DOI: 10.1137/16m1110042 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 27.11.2018. Verfasst von Stephane Durocher und 1 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 29 Literaturangaben.
Abstract (Originalsprache)
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áry'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>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áry's theorem to draw graphs of thickness $t>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>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.
Zitieren
APA
Durocher, S., & Mondal, D. (2018). Relating Graph Thickness to Planar Layers and Bend Complexity. SIAM Journal on Discrete Mathematics, 32(4), 2703-2719. https://doi.org/10.1137/16m1110042
Vancouver
Durocher S, Mondal D. Relating Graph Thickness to Planar Layers and Bend Complexity. SIAM Journal on Discrete Mathematics. 2018;32(4):2703-2719. doi:10.1137/16m1110042
BibTeX
@article{Durocher2018,
author = {Durocher, Stephane and Mondal, Debajyoti},
title = {Relating Graph Thickness to Planar Layers and Bend Complexity},
journal = {SIAM Journal on Discrete Mathematics},
year = {2018},
volume = {32},
number = {4},
pages = {2703--2719},
doi = {10.1137/16m1110042}
}
EUVIMED