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

arboricitybook thicknesscrossingdrawingouterthickness

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

(49)

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

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)