\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf J{\'a}nos Bar{\'a}t, Ji{\v{r}}{\'i} Matou{\v{s}}ek and David R. Wood}
%
%
\medskip
\noindent
%
%
{\bf Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness}
%
%
\vskip 5mm
\noindent
%
%
%
%
The {\it 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 {\it Towards a Theory of
Geometric Graphs}, vol.\ 342 of {\it 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 {\it Proc.\ 12th International Symp.\ on Graph
Drawing} (GD '04), vol.\ 3383 of {\it 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].
\bye