\documentclass[oneside,final,12pt]{book}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{xunicode}

\usepackage{hyperref}
\usepackage{xstring}
\def\rooturl{https://www.math.bgu.ac.il/}
\hyperbaseurl{\rooturl}
\let\hhref\href
\providecommand{\extrahref}[2][]{\LTRfootnote{\LR{\IfBeginWith*{#2}{http}{\nolinkurl{#2}}{\nolinkurl{\rooturl#2}}}}}
\renewcommand{\href}[2]{\IfBeginWith*{#1}{http}{\hhref{#1}{#2}}{\hhref{\rooturl#1}{#2}}\extrahref{#1}}

\usepackage{polyglossia}
\usepackage{longtable}
%% even in English, we sometimes have Hebrew (as in course hours), and we
%% can't add it in :preamble, since it comes after hyperref
%%\usepackage{bidi}
\setdefaultlanguage{english}
\setotherlanguage{hebrew}
%%\setmainfont[Ligatures=TeX]{Libertinus Serif}
\setmainfont[Script=Hebrew,Ligatures=TeX]{LibertinusSerif}[
  UprightFont = *-Regular,
  BoldFont = *-Bold,
  ItalicFont = *-Italic,
  BoldItalicFont = *-BoldItalic,
  Extension = .otf]

\SepMark{‭.}
\robustify\hebrewnumeral
\robustify\Hebrewnumeral
\robustify\Hebrewnumeralfinal

% vim: ft=eruby.tex:



\begin{document}
\pagestyle{empty}
\pagenumbering{gobble}

\begin{center}
\vspace*{\baselineskip}

{\Large Department of Mathematics, BGU}

\vspace*{\baselineskip}

\rule{\textwidth}{1.6pt}\vspace*{-\baselineskip}\vspace*{2pt}
\rule{\textwidth}{0.4pt}\\[\baselineskip]

{\Huge Combinatorics Seminar}\\[0.2\baselineskip]

\rule{\textwidth}{0.4pt}\vspace*{-\baselineskip}\vspace{3.2pt}
\rule{\textwidth}{1.6pt}\\[\baselineskip]

\textbf{On} \emph{Tuesday, January 15, 2019}
\bigskip

\textbf{At} \emph{10:45 -- 11:45}
\bigskip

\textbf{In} \emph{-101}

\vspace*{2\baselineskip}

{\large\scshape Csaba Toth 
  %
  (CSUN)
}
\bigskip

will talk about
\bigskip

{\Large\bfseries Polygonizations for Disjoint Line Segments\par}
\bigskip

\end{center}
\vfill

\textsc{Abstract:}
Given a planar straight-line graph \$G=(V,E)\$ in \$\textbackslash{}mathbb\{R\}\^{}2\$, a 
\emph{circumscribing polygon} of \$G\$ is a simple polygon \$P\$ whose vertex
set is \$V\$, and every edge in \$E\$ is either an edge or an internal 
diagonal of \$P\$. A circumscribing polygon is a \textbackslash{}emph\{polygonization\} for
\$G\$ if every edge in \$E\$ is an edge of \$P\$.

We prove that every arrangement of \$n\$ disjoint line segments in the 
plane (i.e., a geometric perfect matching) has a subset of size
\$\textbackslash{}Omega(\textbackslash{}sqrt\{n\})\$ that admits a circumscribing polygon, which is the 
first improvement on this bound in 20 years. We explore relations
between circumscribing polygons and other problems in combinatorial 
geometry, and generalizations to \$\textbackslash{}mathbb\{R\}\^{}3\$.

We show that it is NP-complete to decide whether a given graph \$G\$ 
admits a circumscribing polygon, even if \$G\$ is 2-regular. Settling a
30-year old conjecture by Rappaport, we also show that it is 
NP-complete  to determine whether a geometric matching admits a 
polygonization.
(Joint work with Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, and 
Diane L. Souvaine.)





\bigskip
\begin{center}
{\bfseries Please Note the Unusual Time!}
\end{center}



% vim: ft=eruby.tex:


\end{document}

% vim: ft=eruby.tex:
