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
204Kb

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.
Keywords:graph drawing, geometric graph, thickness, geometric thickness, book embedding, book thickness, slope-number, slope-parameter
Classifications:Z Theory > Z.500 Representations
ID Code:652
Alternative Locations:http://www.cs.mcgill.ca/~wood/papers/Barat-Matousek-Wood.pdf

Repository Staff Only: item control page

References

Miklós Ajtai, Va\check{s}ek Chvátal, Monroe M. Newborn, and Endre Szemerédi. Crossing-free subgraphs. In Theory and practice of combinatorics, vol. 60 of North-Holland Math. Stud., pp. 9-12. North-Holland, 1982.

Noga Alon. The number of polytopes, configurations and real matroids. Mathematika, 33(1):62-71, 1986.

Gergely Ambrus, János Barát, and Péter Hajnal. The slope parameter of graphs. Submitted. See Tech. Rep. MAT-2005-07, Department of Mathematics, Technical University of Denmark, Lyngby, Denmark, 2005.

Edward A. Bender and E. Rodney Canfield. The asymptotic number of labeled graphs with given degree sequences. J. Combin. Theory Ser. A, 24:296-307, 1978.

Robin Blankenship. Book Embeddings of Graphs. Ph.D. thesis, Department of Mathematics, Louisiana State University, U.S.A., 2003.

Robin Blankenship and Bogdan Oporowski. Drawing subdivisions of complete and complete bipartite graphs on books. Tech. Rep. 1999-4, Department of Mathematics, Louisiana State University, 1999.

Michael B. Dillencourt, David Eppstein, and Daniel S. Hirschberg. Geometric thickness of complete graphs. J. Graph Algorithms Appl., 4(3):5-17, 2000.

Vida Dujmovic´, Matthew Suderman, and David R. Wood. Really straight graph drawings. In János Pach, ed., Proc. 12th International Symp. on Graph Drawing (GD '04), vol. 3383 of Lecture Notes in Comput. Sci., pp. 122-132. Springer, 2004.

Vida Dujmovic´ and David R. Wood. On linear layouts of graphs. Discrete Math. Theor. Comput. Sci., 6(2):339-358, 2004.

Vida Dujmovic´ and David R. Wood. Graph treewidth and geometric thickness parameters. In Proc. 13th International Symp. on Graph Drawing (GD '05), Lecture Notes in Comput. Sci. Springer, to appear.

Christian A. Duncan, David Eppstein, and Stephen G. Kobourov. The geometric thickness of low degree graphs. In Proc. 20th ACM Symp. on Computational Geometry (SoCG '04), pp. 340-346. ACM Press, 2004.

David Eppstein. Separating geometric thickness from book thickness. 2001.

David Eppstein. Separating thickness from geometric thickness. In János Pach, ed., Towards a Theory of Geometric Graphs, vol. 342 of Contemporary Mathematics, pp. 75-86. Amer. Math. Soc., 2004.

John H. Halton. On the thickness of graphs of given degree. Inform. Sci., 54(3):219-238, 1991.

Joan P. Hutchinson, Thomas C. Shermer, and Andrew Vince. On representations of some thickness-two graphs. Comput. Geom., 13(3):161-171, 1999.

Robert E. Jamison. Few slopes without collinearity. Discrete Math., 60:199-206, 1986.

Stasys Jukna. Extremal combinatorics. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2001. With applications in computer science.

Paul C. Kainen. Thickness and coarseness of graphs. Abh. Math. Sem. Univ. Hamburg, 39:88-95, 1973.

Seth M. Malitz. Graphs with E edges have pagenumber O(\sqrt{E}). J. Algorithms, 17(1):71-84, 1994.

Ji\check{r}í Matou\check{s}ek. Lectures on Discrete Geometry, vol. 212 of Graduate Texts in Mathematics. Springer, 2002.

Brendan D. McKay. Asymptotics for symmetric 0-1 matrices with prescribed row sums. Ars Combin., 19(A):15-25, 1985.

John Milnor. On the Betti numbers of real varieties. Proc. Amer. Math. Soc., 15:275-280, 1964.

Petra Mutzel, Thomas Odenthal, and Mark Scharbrodt. The thickness of graphs: a survey. Graphs Combin., 14(1):59-73, 1998.

János Pach and Rephael Wenger. Embedding planar graphs at fixed vertex locations. Graphs Combin., 17(4):717-728, 2001.

Ivan G. Petrovski\breve{i} and Olga A. Ole\breve{i}nik. On the topology of real algebraic surfaces. Izvestiya Akad. Nauk SSSR. Ser. Mat., 13:389-402, 1949.

Richard Pollack and Marie-Franc¸oise Roy. On the number of cells defined by a set of polynomials. C. R. Acad. Sci. Paris Sér. I Math., 316(6):573-577, 1993.

Herbert Robbins. A remark on Stirling's formula. Amer. Math. Monthly, 62:26-29, 1955.

Lajos Rónyai, László Babai, and Murali K. Ganapathy. On the number of zero-patterns of a sequence of polynomials. J. Amer.Math. Soc., 14(3):717-735, 2001.

Francisco Santos and Raimund Seidel. A better upper bound on the number of triangulations of a planar point set. J. Combin. Theory Ser. A, 102(1):186-193, 2003.

Ondrej S´ykora, László A. Székely, and Imrich Vr\check{t}o. A note on Halton's conjecture. Inform. Sci., 164(1-4):61-64, 2004.

René Thom. Sur l'homologie des variétés algébriques réelles. In S. S. Cairns, ed., Differential and Combinatorial Topology, pp. 255-265. Princeton Univ. Press, 1965.

Greg A. Wade and Jiang-Hsing Chu. Drawability of complete graphs using a minimal slope set. The Computer Journal, 37(2):139-142, 1994.

Nicholas Wormald. Some problems in the enumeration of labelled graphs. Ph.D. thesis, Newcastle-upon-Tyne, United Kingdom, 1978.