\documentclass[a4paper,titlepage,12pt,normalheadings,makeidx]{article}
\usepackage{graphicx} 
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{T. Dissaux, G. Ducoffe, N. Nisse et S. Nivelle  :  Longueur arborescente des graphes s\'erie-parall\`eles}
%

% Pour le sommaire
\addcontentsline{toc}{section}{T. Dissaux, G. Ducoffe, N. Nisse et S. Nivelle  :  Longueur arborescente des graphes s\'erie-parall\`eles}
%

% Pour la liste des auteurs
\index{Dissaux, T.}\index{Ducoffe, G.}\index{Nisse, N.}\index{Nivelle, S.}
%

% Citer un par un les auteurs et leur affiliation
\underline{Thomas Dissaux}, Universit\'e C\^ote d'Azur, CNRS, Inria, I3S, Sophia Antipolis, France, {\tt thomas.dissaux@inria.fr}\\ %souligner l'orateur
\indent
Guillaume Ducoffe, University of Bucharest \& National Institute of Research and Development in Informatics, Roumanie, {\tt guillaume.ducoffe@ici.ro}\\ 
\indent
Nicolas Nisse, Universit\'e C\^ote d'Azur, CNRS, Inria, I3S, Sophia Antipolis, France, {\tt nicolas.nisse@inria.fr}\\ 
\indent
Simon Nivelle, INSPE Paris, Sorbonne universit\'e, France, {\tt simon.nivelle@free.fr}\\ 
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le r\'esum\'e

\vspace{-0.5cm}
Les d\'ecompositions arborescentes repr\'esentent un graphe comme des sous ensembles de sommets, appel\'es sacs, et structur\'es comme un arbre. La mesure classique de telles d\'ecompositions est leur {\it largeur} (taille du plus grand sac) et il est bien connue que de nombreux probl\`emes NP-difficiles peuvent \^etre r\'esolus en temps lin\'eaire dans la classe des graphes de largeur born\'ee. Une autre mesure, la {\it longueur} d'une d\'ecomposition, correspond au plus grand diam\`etre d'un sac~\cite{DG} et a \'egalement des applications algorithmiques (probl\`eme du voyageur de commerce, calcul de tables de routage compactes ...). La {\it longueur arborescente} (treelength) d'un graphe est la plus petite longueur de ses d\'ecompositions.
D\'ecider si la longueur arborescente d'un graphe est au plus $2$ est NP-complet~\cite{lok}, la longueur arborescente ne peut être approch\'ee par un rapport d'approximation inf\'erieur à $\frac{3}{2}$~\cite{lok} et le meilleur algorithme d'approximation connu a un rapport d'approximation de $3$~\cite{DG}.

Dans le cas des graphes planaires, il est seulement connu que les graphes planaires ext\'erieurs ont une longueur arborescente \'egale au tiers d'un plus grand cycle isom\'etrique~\cite{DG}.
Nous initions l'\'etude de la complexit\'e du calcul de la longueur arborescente dans une autre sous-classe des graphes planaires, les graphes s\'erie-parall\`eles.
Nous pr\'esentons tout d'abord un algorithme d'approximation de rapport $\frac{3}{2}$ dans cette classe. Notre r\'esultat principal est la caract\'erisation en terme de sous graphes isom\'etriques interdits des graphes s\'erie-parall\`eles de longueur arborescente $2$.
Cette caract\'erisation conduit \`a un algorithme polynomial pour la reconnaissance de ces graphes. 

Ces travaux ont \'et\'e accept\'es \`a la conf\'erence LAGOS 2021.

\vspace{-0.5cm}
{\small
\begin{thebibliography}{99}

\bibitem{DG}
Y.~Dourisboure and C.~Gavoille,\emph{Tree-decompositions with bags of small diameter}, Discrete Maths {\bf 307 (16)} (2007), 2008-2029.

\bibitem{lok}
D.~Lokshtanov, \emph{On the complexity of computing treelength}, Discrete Applied Mathematics {\bf 158} (2010), 820-827.

\end{thebibliography}
}

\vfill
\end{document}
