Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness

Simple item page
dc.creatorBarat, Janos
dc.creatorMatousek, Jiri
dc.creatorWood, David R.
dc.date2005-09-07
dc.date2005-09-09
dc.date.accessioned2026-07-07T06:24:40Z
dc.date.available2026-07-07T06:24:40Z
dc.descriptionThe 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].
dc.identifierhttps://arxiv.org/abs/math/0509150
dc.identifierhttp://arxiv.org/abs/math/0509150
dc.identifierThe Electronic Journal of Combinatorics, 13(1):R3, 2006.
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/96625
dc.subjectCombinatorics
dc.subject05C62
dc.titleBounded-Degree Graphs have Arbitrarily Large Geometric Thickness
dc.typetext

Files

Collections

arXiv