Relating graph thickness to planar layers and bend complexity

DOI10.1137/16M1110042zbMATH Open1400.05063arXiv1602.07816OpenAlexW2963980127MaRDI QIDQ4556953FDOQ4556953

Authors: Stephane Durocher, Debajyoti Mondal 

Publication date: 28 November 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: 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. 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'{a}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$ layers with bend complexity 2 (resp., $3n+O(1)$). However, allowing a higher number of layers may reduce the bend complexity, e.g., complete graphs require $Theta(n)$ layers to be drawn using 0 bends per edge. In this paper we present an elegant extension of F'{a}ry's theorem to draw graphs of thickness $t>2$. We first prove that thickness-$t$ graphs can be drawn on $t$ layers with $2.25n+O(1)$ bends per edge. We then develop another technique to draw thickness-$t$ graphs on $t$ layers with bend complexity, i.e., $$, where $$. 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 $frac3(k-1)n(4k-2)$.

Full work available at URL: https://arxiv.org/abs/1602.07816

Recommendations

• Relating graph thickness to planar layers and bend complexity
• Geometric thickness in a grid
• Graph treewidth and geometric thickness parameters
• On graph thickness, geometric thickness, and separator theorems

zbMATH Keywords

planar graphsgraph drawinggeometric thicknessbend complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Title not available (Why is that?)
• SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES
• On simultaneous planar graph embeddings
• Embedding planar graphs at fixed vertex locations
• Drawing colored graphs on colored points
• Bounded-degree graphs have arbitrarily large geometric thickness
• Simultaneous Embedding of Planar Graphs with Few Bends
• Graph treewidth and geometric thickness parameters
• Partitioning a sequence into few monotone subsequences
• Geometric Thickness of Complete Graphs
• Title not available (Why is that?)
• The geometric thickness of low degree graphs
• Monotonic Subsequences
• On graph thickness, geometric thickness, and separator theorems
• Thickness and colorability of geometric graphs
• Geometric thickness in a grid
• Curve-constrained drawings of planar graphs
• Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
• Relating graph thickness to planar layers and bend complexity
• Colored Point-Set Embeddings of Acyclic Graphs
• Simultaneous embeddings with vertices mapping to pre-specified points
• Simultaneous embeddings with few bends and crossings
• Monotone simultaneous embeddings of paths in \(d\) dimensions

Cited In (3)

• Relating graph thickness to planar layers and bend complexity
• Simultaneous embedding of colored graphs
• On the 3-tree core of plane graphs

This page was built for publication: Relating graph thickness to planar layers and bend complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4556953)