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)

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

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)