English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The thickness of a graph $G=(V,E)$ with $n$ vertices is the minimum number ofplanar 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 apoint and each edge is mapped to a polygonal chain. Bend and layer complexitiesare 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 complexityof $\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 correspondsto a planar polyline drawing. Let $G$ be a graph of thickness $t$. ByF\'{a}ry's theorem, if $t=1$, then $G$ can be drawn on a single layer with bendcomplexity $0$. A few extensions to higher thickness are known, e.g., if $t=2$(resp., $t>2$), then $G$ can be drawn on $t$ layers with bend complexity 2(resp., $3n+O(1)$). However, allowing a higher number of layers may reduce thebend complexity, e.g., complete graphs require $\Theta(n)$ layers to be drawnusing 0 bends per edge.  In this paper we present an elegant extension of F\'{a}ry's theorem to drawgraphs of thickness $t>2$. We first prove that thickness-$t$ graphs can bedrawn on $t$ layers with $2.25n+O(1)$ bends per edge. We then develop anothertechnique to draw thickness-$t$ graphs on $t$ layers with bend complexity,i.e., $O(\sqrt{2}^{t} \cdot n^{1-(1/\beta)})$, where $\beta = 2^{\lceil (t-2)/2\rceil }$. Previously, the bend complexity was not known to be sublinear for$t>2$. Finally, we show that graphs with linear arboricity $k$ can be drawn on$k$ layers with bend complexity $\frac{3(k-1)n}{(4k-2)}$.

Relating Graph Thickness to Planar Layers and Bend Complexity