\documentclass[11pt]{article}
\usepackage[russian,greek,english]{babel}
\usepackage{amsmath,ifthen,color,eurosym}
\usepackage{wrapfig,hyperref,cite}
\usepackage{latexsym,amsthm,amsmath,amssymb,url,cite}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{stmaryrd,wasysym}
\usepackage{colortbl}
\usepackage[lined,boxed,commentsnumbered]{algorithm2e}
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}

\def\baselinestretch{1}


\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{observation}{Observation}
\newtheorem{proposition}{Proposition}

\setlength{\textheight}{22cm}
\setlength{\topmargin}{-1cm}
\setlength{\textwidth}{165mm}
\setlength{\oddsidemargin}{-3mm}
\setlength{\unitlength}{1mm}


%\renewcommand{\refname}{\small References}
\addto{\captionsenglish}{\renewcommand{\refname}{\normalsize
    References}}



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%
%Put here the package you need, new commands, ...



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%

\begin{document}
%1 page max !! 

%Write your title here: 
\noindent{\bf\Large A Fixed Parameter Tractable Approximation Scheme for the
  Optimal Cut Graph of a Surface}

%List the authors as follows (you may underline the speaker, or just
%name the speaker, and mention your co-authors at the end, up to you):  


\noindent \underline{Vincent Cohen-Addad} -- {\small École Normale Supérieure, Paris}

\noindent Arnaud de Mesmay -- {\small IST Austria, Klosterneuburg, Austria}


\vspace{2ex}

\noindent{\bf Abstract:} %Here write your abstract
Given a graph $G$ cellularly embedded on a surface $\Sigma$ of genus $g$, a cut graph is a
subgraph of $G$ such that cutting $\Sigma$ along $G$ yields a topological
disk. We provide a fixed parameter tractable approximation scheme for
the problem of computing the shortest cut graph, that is, for any
$\varepsilon >0$, we show how to compute a $(1+ \varepsilon)$ approximation
of the shortest cut graph in time $f(\varepsilon, g)n^3$. 

Our techniques first rely on the computation of a spanner for the
problem using the technique of brick decompositions, to reduce the problem to the
case of bounded tree-width. Then, to solve the bounded tree-width case, we
introduce a variant of the surface-cut decomposition, 
which may be of independent interest.

\end{document}