\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 Petr Hlin\v en\'y}
%
%
\medskip
\noindent
%
%
{\bf New Infinite Families of Almost-Planar Crossing-Critical Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
We show that, for all choices of integers $k>2$ and $m$, there are
simple $3$-connected $k$-crossing-critical graphs containing more
than $m$ vertices of each even degree $\leq2k-2$.  This construction
answers one half of a question raised by Bokal, while the other half
asking analogously about vertices of odd degrees at least $7$ in
crossing-critical graphs remains open.  Furthermore, our newly
constructed graphs have several other interesting properties; for
instance, they are almost planar and their average degree can attain
any rational value in the interval
$\big[3+{1\over5},6-{8\over k+1}\big)$.

\bye

.
