Bounded-degree graphs have arbitrarily large geometric thickness

Authors János Barát, David R. Wood, Jiří Matoušek

Publication date 17 January 2006

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0509150, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r3.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

geometric graphs geometric thickness slope number straight-line drawing of graphs

Mathematics Subject Classification ID

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

Abstract: The geometric thickness of a graph G is the minimum integer k such that there is a straight line drawing of G with its edge set partitioned into k plane subgraphs. Eppstein [Separating thickness from geometric thickness. In: Towards a Theory of Geometric Graphs, vol. 342 of Contemp. Math., AMS, 2004] asked whether every graph of bounded maximum degree has bounded geometric thickness. We answer this question in the negative, by proving that there exists Delta-regular graphs with arbitrarily large geometric thickness. In particular, for all Delta >= 9 and for all large n, there exists a Delta-regular graph with geometric thickness at least c Delta^{1/2} n^{1/2 - 4/Delta - epsilon}. Analogous results concerning graph drawings with few edge slopes are also presented, thus solving open problems by Dujmovic' et al. [Really straight graph drawings. In: Proc. 12th International Symp. on Graph Drawing (GD '04), vol. 3383 of Lecture Notes in Comput. Sci., Springer, 2004] and Ambrus et al. [The slope parameter of graphs. Tech. Rep. MAT-2005-07, Department of Mathematics, Technical University of Denmark, 2005].

Review text

A straight-line drawing or a geometric graph of a graph \(G\) is a layout of \(G\) in the plane such that the vertices are represented by distinct points, the edges are represented by (possibly crossing) line segments connecting the corresponding point pairs and not passing though any other point that represents a vertex. The geometric thickness of \(G\) is the minimum number of planar subgraphs \(D\) of a geometric graph \(G\) whose union is \(D\). The slope number of \(G\) is the smallest number of distinct edge slopes used in a straight-line drawing \(D\) of \(G\). The authors prove that, for all \(\Delta\geq 9\) and \(\varepsilon>0\), for all large \(n>n(\varepsilon)\) and \(n\geq c\Delta\), there exists a \(\Delta\)-regular \(n\)-vertex graph with geometric thickness at least \(c\sqrt{\Delta}n^{1/2-4/\Delta -\varepsilon}\), for some absolute constant \(c\). This solves an open problem posed by \textit{D.~Epptein} [Contemp. Math. 342, 75--86 (2004; Zbl 1067.05022)]. The authors also prove that, for all \(\Delta\geq 5\), there exists a \(\Delta\)-regular graph with arbitrarily large slope number, solving an open problem posed by \textit{V. Dujmović} et al. [Lect. Notes Comput. Sci. 3383, 122--132 (2005; Zbl 1111.68571)]. This result on the slope number of bounded-degree graphs has been improved by \textit{J.~Pach} and \textit{D.~Pálvölgyi} [Electron. J. Comb. 13, No. 1, Research paper N1 (2006; Zbl 1080.05064)]. They show that, for all \(\Delta\geq 5\), there exists a \(\Delta\)-regular \(n\)-vertex graph whose slope number is at least \(n^{1/2-1/(\Delta-2)-o(1)}\).

Recommendations

Cited in

(27)

This page was built for publication: Bounded-degree graphs have arbitrarily large geometric thickness

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