\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 Partial Representation Extension Problem of Interval Graphs}

%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{Pavel Klav\'{\i}k} -- {\small Charles University in Prague}

\vspace{2ex}

\noindent{\bf Abstract:} %Here write your abstract

The recognition problems were studied for many graph classes, e.g., for interval graphs several
linear-time algorithms are known. In this talk, I will describe a generalization of recognition
called \emph{partial representation extension}, introduced in~\cite{kkv}. For interval graphs, the
input also gives several intervals which are \emph{pre-drawn}, forming a partial representation. We
ask whether we can add the remaining intervals to create an extending interval representation; see
Figure~\ref{fig:int_example}.

\begin{figure}[h!]
\centering
\includegraphics{int_example}
\caption{(a) An interval graph $G$ with one of its interval representations.  (b) A partial
representation with pre-drawn intervals $x$, $y$ and $z$. It is non-extendible since $u$
cannot be placed.}
\label{fig:int_example}
\end{figure}

I will give an overview of known results and techniques. For interval graphs, there are two
linear-time algorithms solving partial representation extension~\cite{kkosv,blas_rutter}. Extendible
representations were characterized by partial orderings of maximal cliques~\cite{kkv,kkosv}. Also
minimal obstructions are known~\cite{ks}, generalizing minimal induced subgraphs of interval graphs
of Lekkerkerker and Boland. We will also discuss other variations of the problem~\cite{kkorssv}.

%^% you need a ref section, do it more or less like that : 
\small
\begin{thebibliography}{1}

\bibitem{kkv}
P.~Klav\'{\i}k, J.~Kratochv\'{\i}l, and T.~Vysko\v{c}il.
\newblock Extending partial representations of interval graphs.
\newblock In {\em TAMC}, volume 6648 of {\em Lecture Notes in Computer Science}, pages 276--285. Springer,
  2011.

\bibitem{blas_rutter}
T.~Bl{\"a}sius and I.~Rutter.
\newblock Simultaneous {PQ}-ordering with applications to constrained embedding
  problems.
\newblock In {\em SODA'13}, pages 1030--1043, 2013.

\bibitem{kkosv}
P.~Klav\'{\i}k, J.~Kratochv\'{\i}l, Y.~Otachi, T.~Saitoh, and T.~Vysko\v{c}il.
\newblock Extending partial representations of interval graphs.
\newblock {\em CoRR}, abs/1306.2182, 2013.

\bibitem{kkorssv}
P.~Klav\'{\i}k, J.~Kratochv\'{\i}l, Y.~Otachi, I.~Rutter, T.~Saitoh,
  M.~Saumell, and T.~Vysko\v{c}il.
\newblock Extending partial representations of proper and unit interval graphs.
\newblock In {\em SWAT}, volume 8503 of {\em Lecture Notes in Computer Science}, pages 253--264. Springer,
  2014.

\bibitem{ks}
P.~Klav\'{\i}k and M.~Saumell.
\newblock Minimal obstructions for partial representations of interval graphs.
\newblock In {\em ISAAC}, volume 8889 of {\em Lecture Notes in Computer
  Science}, pages 401--413, 2014.

\end{thebibliography}


\end{document}
