Relating graph thickness to planar layers and bend complexity

DOI10.1137/16M1110042MaRDI QIDQ4556953zbMATH OpenOpenAlexFDO

Authors Stephane Durocher, Debajyoti Mondal

Publication date 28 November 2018

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

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

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)

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)$.

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

Cites work

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

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)