tailieunhanh - Báo cáo toán học: "Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness. | Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness János Barát Bolyai Institute University of Szeged Szeged Hungary barat@ Jiri Matousek Department of Applied Mathematics and Institute for Theoretical Computer Science Charles University Prague Czech Republic matousek@ David R. Woodt Departament de Matematica Aplicada II Universitat Politecnica de Catalunya Barcelona Spain Submitted Sep 9 2005 Accepted Dec 22 2005 Published Jan 7 2006 Mathematics Subject Classification 05C62 05C10 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 A-regular graphs with Research of János Barát was supported by a Marie Curie Fellowship of the European Community under contract number HPMF-CT-2002-01868 and by the OTKA Grant . Research of David Wood is supported by the Government of Spain grant MEC SB2003-0270 and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R3 1 arbitrarily large geometric thickness. In particular for all A 9 and for all large n there exists a A-regular graph with geometric thickness at least Cy A n1 2 4 e. 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 . 1 Introduction A