\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 Intersection Graphs of Non-crossing Paths}

%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 Steven Chaplick -- {\small Universit\"at W\"urzburg}


\vspace{2ex}

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

Intersection representations of graphs are ubiquitous in graph theory and covered in many graph theory textbooks (see, e.g., \cite{MckeeM1999,Golumbic2004}). For a given graph $G$, a collection $\mathcal{S}$ of sets, $\{S_v\}_{v \in V(G)}$, is an \emph{intersection representation} of $G$ when $S_u \cap S_v \neq \emptyset$ iff $uv \in E(G)$. Similarly, we say that $G$ is the intersection graph of $\mathcal{S}$. 
%One quickly sees that all graphs have intersection representations (e.g., by choosing, for every $v \in V(G)$, $S_v$ as the edges incident to $v$). Thus, one often considers restrictions either on the \emph{host} set (i.e., the domain from which the elements of the $S_v$'s can be chosen), collection $\mathcal{S}$, and/or on the individual sets $S_v$. These restrictions are usually inspired by applications and/or algorithmic motivations. 

In this work we consider classes of intersection graphs where the sets are taken from a topological space, are \emph{arc-connected}, and are pairwise \emph{non-crossing}. A set $S$ is \emph{arc-connected} when any two of its points can be connected by a \emph{curve} within the set (note: a \emph{curve} is  a homeomorphic image of a closed interval). Notice that when the topological space is a graph, arc-connectedness is precisely the usual connectedness of a graph and curves are precisely paths.  
Two connected sets $S_1,S_2$ are said to be \emph{non-crossing} when both $S_1 \setminus S_2$ and $S_2 \setminus S_1$ are arc-connected. The most general case of intersection graphs of non-crossing sets which have been studied are those of non-crossing arc-connected (NC-AC) sets in the plane~\cite{Kratochvil1997}. These were considered together with the intersection graphs of disks in the plane, or simply \emph{disk} graphs -- another non-crossing class. In particular, it has been shown that the recognition of both NC-AC graphs and disk graphs is NP-hard~\cite{Kratochvil1997}.

Our focus is on intersection graphs of non-crossing paths. Note that the class of non-crossing subpaths of a path is precisely the well-studied class of proper interval graphs. We study the graph classes listed below. 

\begin{itemize}
\item NC paths in a tree. 
\item NC directed paths in a directed tree. 
\item NC directed paths in a rooted tree. 
\end{itemize} 

These graph classes naturally generalize the algorithmically convenient structure of proper interval graphs. For example, we will also show that the dominating set problem can be solved in polynomial time on the intersection graphs of non-crossing paths in a tree. This contrasts the fact that the dominating set problem is NP-complete on intersection graphs of paths in a tree (i.e., where paths are allowed to cross)~\cite{BoothJ1982}. 
We further characterize all of these classes by finite forbidden induced subgraph characterizations. 


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

\bibitem{BoothJ1982}
Kellogg S. Booth and J. Howard Johnson,
\newblock {Dominating Sets in Chordal Graphs}
\newblock {\em SIAM Journal on Computing} 11(1):191-199, 1982.
%year = {1982},
%doi = {10.1137/0211015},
%URL = {http://dx.doi.org/10.1137/0211015},
%eprint = {http://dx.doi.org/10.1137/0211015}

\bibitem{Golumbic2004}
Martin C. Golumbic.
\newblock{ Algorithmic graph theory and perfect graphs.}
\newblock{ \em Annals of discrete mathematics.} Elsevier 2004. 

\bibitem{Kratochvil1997}
Jan Kratochv\'il.
\newblock{Intersection graphs of noncrossing arc-connected sets in the plane},
\newblock{\em In Graph Drawing, LNCS 1190:257-270,} 1997.

\bibitem{MckeeM1999}
T.A. McKee, T.A. and F.R. McMorris.
\newblock {Topics in Intersection Graph Theory.}
\newblock{\em Monographs on Discrete Mathematics and Applications.} SIAM 1999. 

\end{thebibliography}


\end{document}