2006/01/07 by János Barát, Jiřı́ Matoušek, David R. Wood · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Combinatorics #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Discrete mathematics #Geometric graph theory #Graph #Line graph #Mathematical analysis #Mathematics #Voltage graph
paper · pdf · doi:10.37236/1029
openalex publication_date 2006/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Δ-regular graphs with arbitrarily large geometric thickness. In particular, for all Δ≥9 and for all large n, there exists a Δ-regular graph with geometric thickness at least c√(Δ) n1/2-4/Δ-ε. Analogous results concerning graph drawings with few edge slopes are also presented, thus solving open problems by Dujmović 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].