%Compiler avec pdflatex, le résultat ne doit pas dépasser une page
%Merci de respecter scrupuleusement ce modèle.
\documentclass[a4paper,titlepage,12pt,normalheadings,makeidx]{article}
\usepackage{graphicx} 
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{amssymb}
\begin{document}
\newpage

\def\leq{\leqslant}\def\le{\leq}
\def\geq{\geqslant}\def\ge{\geq}

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{C. Gavoille et C. Hilaire : Grilles majeures de graphes déssinés}
%

% Pour le sommaire
\addcontentsline{toc}{section}{C. Gavoille et C. Hilaire : Grilles majeures de graphes déssinés}
%

% Pour la liste des auteurs
\index{Gavoille, C.}\index{Hilaire, C.}
%

% Citer un par un les auteurs et leur affiliation
Cyrille Gavoille, LaBRI, Bordeaux, {\tt gavoille@labri.fr}\\
\indent
\underline{Claire Hilaire} LaBRI, Bordeaux, {\tt claire.hilaire@labri.fr}\\ %souligner l'orateur
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé
Nous considérons le problème suivant, motivé par le théorème d'exclusion de grille comme mineur de Robertson et Seymour :

\begin{quote}
\emph{Étant donné un graphe $H$ possédant un dessin planaire en lignes brisées sur une grille $p\times q$, quelle est la plus petite aire $A = A(p,q)$ d'une grille majeure de $H$? C'est-à-dire d'une grille possédant $H$ comme mineur.}
\end{quote}

Cette version du problème a été soulevée par Dieng et Gavoille~\cite{DG20}, qui ont montré que $A(p,q) = O(p^2 q)$. Comme $A(p,q) \ge pq$ pour certains graphes $H$ comme une grille $p \times q$ par exemple, on se demande légitimement si la borne supérieure $A(p,q) = O(pq)$ est envisageable pour tout $H$.

Dans cette étude, nous prouvons que déterminer la plus petite aire d'une grille majeure de $H$ est NP-dificile, mais obtenons la borne voulue pour de nombreuses familles de graphes planaires. Notamment, par un résultat classique de la théorie des mineurs de graphes, $H$ est mineur d'une grille carrée de côté $2|V(H)|-4$, donc la borne est trivialement vraie si $pq = \Omega(|V(H)|^2)$, c'est-à-dire si le dessin est peu dense. De plus, grâce à un résultat de Dolev, Leighton et Trickey~\cite{DLT94}, nous montrons que si $H$ est $k$-planaire extérieur, alors $A = O(kpq)$. La borne $O(pq)$ est donc vraie pour $k$ constant. Enfin, nous proposons une technique qui s'applique à des graphes ayant un dessin dense, c'est-à-dire d'aire $O(|V(H)|)$, sans être $O(1)$-planaire extérieurs.

\begin{thebibliography}{99}

\bibitem{DG20}%
  Y.~Dieng and C.~Gavoille, \emph{On the treewidth of planar minor
    free graphs}, in 4th EAI Int'nl Conf. on Innov. and
  Interdisciplinary Sol. for Underserved Areas (InterSol), vol.~321 of
  LNICST series, Springer, Cham, Mar. 2020, pp.~238--250.

\bibitem{DLT94}%
  D.~Dolev and F.~T.~Leighton, and H~.W.~Trickey, \emph{Planar
    embedding of planar graphs}, Advances in Computer Research, 2
  (1994), 147--161.

\end{thebibliography}


\vfill
\end{document}
