Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness

Matoušek, Jiří and Barát, János and Wood, David R. (2005) Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness. [Preprint]

[img] PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (209kB)

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\geq9$ and for all large n, there exists a $\Delta$-regular graph with geometric thickness at least $c\sqrt{\Delta}\,n^{1/2-4/\Delta-\epsilon}$. Analogous results concerning graph drawings with few edge slopes are also presented, thus solving open problems by Dujmovi{\'c} 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].

Item Type: Preprint
Additional Information: This paper is submitted for publication.
Classifications: Z Theory > Z.500 Representations
URI: http://gdea.informatik.uni-koeln.de/id/eprint/652

Actions (login required)

View Item View Item