Graph treewidth and geometric thickness parameters

DOI10.1007/S00454-007-1318-7MaRDI QIDQ2369933zbMATH OpenOpenAlexDBLPWikidataFDO

Authors David R. Wood, Vida Dujmović

Publication date 21 June 2007

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

book thicknessarboricityouterthicknesscrossingdrawing

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Consider a drawing of a graph $G$ in the plane such that crossing edges are coloured differently. The minimum number of colours, taken over all drawings of $G$, is the classical graph parameter "thickness". By restricting the edges to be straight, we obtain the "geometric thickness". By further restricting the vertices to be in convex position, we obtain the "book thickness". This paper studies the relationship between these parameters and treewidth. Our first main result states that for graphs of treewidth $k$, the maximum thickness and the maximum geometric thickness both equal $lceilk/2ceil$. This says that the lower bound for thickness can be matched by an upper bound, even in the more restrictive geometric setting. Our second main result states that for graphs of treewidth $k$, the maximum book thickness equals $k$ if $kleq2$ and equals $k+1$ if $kgeq3$. This refutes a conjecture of Ganley and Heath [Discrete Appl. Math. 109(3):215-221, 2001]. Analogous results are proved for outerthickness, arboricity, and star-arboricity.

Recommendations

• Graph Drawing
• On graph thickness, geometric thickness, and separator theorems
• Thickness and colorability of geometric graphs
• Geometric Thickness of Complete Graphs
• scientific article; zbMATH DE number 2145231

Cited in

(41)

• Geodesic obstacle representation of graphs
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• A self-stabilizing algorithm for cut problems in synchronous networks
• scientific article; zbMATH DE number 1953110 (Why is no real title available?)
• Threshold Treewidth and Hypertree Width
• Graph Drawing
• Induced and weak induced arboricities
• Layouts of Expander Graphs
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• On the upward book thickness problem: combinatorial and complexity results
• Drawing Cubic Graphs with the Four Basic Slopes
• Parameterized algorithms for book embedding problems
• A survey on book-embedding of planar graphs
• scientific article; zbMATH DE number 2145231 (Why is no real title available?)
• Book embedding of graphs on the projective plane
• Relating graph thickness to planar layers and bend complexity
• Stack-number is not bounded by queue-number
• Book embedding of locally planar graphs on orientable surfaces
• Parameterized algorithms for book embedding problems
• Compact navigation and distance oracles for graphs with small treewidth
• On graph thickness, geometric thickness, and separator theorems
• Thickness and colorability of geometric graphs
• Treewidth, Circle Graphs, and Circular Drawings
• Book embeddings of \(k\)-framed graphs and \(k\)-map graphs
• Treewidth, circle graphs and circular drawings
• 1-page and 2-page drawings with bounded number of crossings per edge
• On the biplanarity of blowups
• Parameterized analysis and crossing minimization problems
• Three ways to cover a graph
• On exteriority notions in book embeddings and treewidth
• Proximity drawings of high-degree trees
• Compact navigation and distance oracles for graphs with small treewidth
• On the upward book thickness problem: combinatorial and complexity results
• Graphs of linear growth have bounded treewidth
• scientific article; zbMATH DE number 7071193 (Why is no real title available?)
• Coloring drawings of graphs
• scientific article; zbMATH DE number 7029306 (Why is no real title available?)
• Embedding planar 5-graphs in three pages
• Planar graphs that need four pages
• Local and union page numbers
• Geodesic obstacle representation of graphs

This page was built for publication: Graph treewidth and geometric thickness parameters

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