Graph treewidth and geometric thickness parameters

DOI10.1007/S00454-007-1318-7zbMATH Open1118.05018DBLPjournals/dcg/DujmovicW07arXivmath/0503553OpenAlexW2070606919WikidataQ56689193 ScholiaQ56689193MaRDI QIDQ2369933FDOQ2369933

Authors: David R. Wood, Vida Dujmović 

Publication date: 21 June 2007

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

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.

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

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

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)

Cited In (44)

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