Shortest path embeddings of graphs on surfaces\thanks{The project was partially supported by the Czech-French collaboration project EMBEDS (CZ: 7AMB15FR003, FR: 33936TF). The research of A.~H. was funded by GUDHI, geometric understanding in higher dimensions. The research of A.~dM. leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme (FP7/2007-2013) under REA grant agreement n° [291734]. V.~K.~and M.~T. were partially supported by the project CE-ITI (GA\v{C
%Martin Tancer\thanks{ %Department of Applied Mathematics and Institute for Theoretical Computer Science (supported by project 1M0545 %of The Ministry of Education of the Czech Republic)
Faculty of Mathematics %and Physics
Charles University
Malostransk\'e n\'am.~25
118~00 Prague
%Czech Republic. Partially supported by project GAUK 49209. %This work was done during the author's stay at KTH
Stockholm; and the author %would like to thank to Anders Bj\"orner for this opportunity. %E-mail: {\tt tancer@kam.mff.cuni.cz
Alfredo Hubard\thanks{INRIA Sophia-Antipolis and Universit\'e Paris-Est Marne-la-Vall\'ee
France
\protect\url{alfredo.hubard@inria.fr
%We introduce a notion of strong $d$-collapsibility. Using this notion, we %simplify the proof of Matou\v{sek and the author~\cite{matousek-tancer08 showing that the nerve of a %family of sets of size at most $d$ is $d$-collapsible. %
arXiv.tex
\documentclass[11pt]{article}
\usepackage[twoside,a4paper,margin=1in]{geometry}
\usepackage{microtype}
%\documentclass[11pt]{article}
%\usepackage{a4wide}
\usepackage{graphicx,url,amsmath,amsthm,amsfonts,amssymb,subfigure,bbm,bm}

%\usepackage{wasysym}
\usepackage[dvips]{epsfig}
%\usepackage[usenames,dvipsnames]{color}
\usepackage{thm-restate}
\usepackage{cutwin}
\usepackage{float}
\usepackage{color}



\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{observation}[theorem]{Observation}
\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{question}{Question}
%\theoremstyle{remark}
%\newtheorem{remark}[theorem]{Remark}


\newcommand{\executeiffilenewer}[3]{%
\ifnum\pdfstrcmp{\pdffilemoddate{#1}}%
{\pdffilemoddate{#2}}>0%
{\immediate\write18{#3}}\fi%
}
%\newcommand{\includesvg}[1]{\includegraphics{#1}}
%\newcommand{\includesvg}[1]{%
%\executeiffilenewer{#1.svg}{#1.pdf}%
%{inkscape -z -D --file=fig/#1.svg %
%--export-pdf=fig/#1.pdf --export-latex}%
%\input{#1.pdf_tex}%
%}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\K}{{\sf K}}
\renewcommand{\L}{{\sf{L}}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\M}{\sf M}
\newcommand{\V}{\mathcal V}

\newcommand{\RP}{\mathbb{R}P}

\newcommand{\tw}[1]{\bar{ #1}}

\newcommand{\pp}{\mathbf{p}}
\newcommand{\qq}{\mathbf{q}}
\newcommand{\rr}{\mathbf{r}}
\newcommand{\vv}{\mathbf{v}}
\newcommand{\ww}{\mathbf{w}}
\newcommand{\xx}{\mathbf{x}}
\newcommand{\uni}{universal shortest path metric}


\newcommand{\blue}[1]{{\color{blue}\bf #1}}
\newcommand{\gray}[1]{{\color{gray}\bf #1}}
\newcommand{\red}[1]{{\color{red}\bf #1}}
\newcommand{\magenta}[1]{{\color{magenta}\bf #1}}
\newcommand{\green}[1]{{\color{green}\bf #1}}
\newcounter{sideremark}
\newcommand{\marrow}{\stepcounter{sideremark}\marginpar{$\boldsymbol{\longleftarrow\scriptstyle\arabic{sideremark}}$}}

\newif\ifappendix
\appendixtrue % Proof of the theorem of Yves CdV in the appendix
%\appendixfalse % Proof of the theorem of Yves CdV in the main body

\newif\ifcomments
%\commentstrue % Comments ON
\commentsfalse %Comments OFF
\ifcomments
\newcommand{\martin}[1]{{\vskip 5pt\textsf{\magenta{*** (Martin) \marrow #1}\vskip 5pt}}
}
\newcommand{\alfredo}[1]{{\vskip 5pt\textsf{\blue{*** (Alfredo) \marrow #1}\vskip5pt}}
}

\newcommand{\arnaud}[1]{{\vskip 5pt\textsf{\red{*** (Arnaud) \marrow #1}\vskip 5pt}}
}

\newcommand{\vojta}[1]{{\vskip 5pt\textsf{\green{*** (Vojta) \marrow #1}\vskip 5pt}}
}
\else
\newcommand{\martin}[1]{}
\newcommand{\alfredo}[1]{}
\newcommand{\arnaud}[1]{}
\newcommand{\vojta}[1]{}
\fi

\def\note#1{\GenericWarning{}%
  {AUTHOR WARNING: Unresolved annotation}%
  {\marginpar%
    [\hfill\llap{\textcircled{\small{$\circledcirc$}}$\!\Longrightarrow$}]%
    {\rlap{$\Longleftarrow\!$\textcircled{\small{$\circledcirc$}}}}}%
  \textsf{$\langle\!\langle${#1}$\rangle\!\rangle$}%
}
\newcommand{\heading}[1]{\medskip\par\noindent{\bf #1}}

\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\lk}{lk}


\title{Shortest path embeddings of graphs on surfaces\thanks{The project was
    partially supported by the Czech-French collaboration project EMBEDS (CZ: 7AMB15FR003, FR: 33936TF). 
    The research of A.~H. was funded by GUDHI, geometric understanding in higher dimensions.
    The
    research of A.~dM. leading to these results has
    received funding from the People Programme (Marie Curie Actions)
    of the European Union's Seventh Framework Programme
    (FP7/2007-2013) under REA grant agreement n° [291734]. V.~K.~and M.~T. were
partially supported by the project CE-ITI (GA\v{C}R P202/12/G061).}}
%\author{
%Martin Tancer\thanks{
%Department of Applied Mathematics and Institute for Theoretical Computer Science (supported by project 1M0545
%of The Ministry of Education of the Czech Republic), Faculty of Mathematics
%and Physics, Charles University, Malostransk\'e n\'am.~25, 118~00 Prague,
%Czech Republic. Partially supported by project GAUK 49209.
%This work was done during the author's stay at KTH, Stockholm; and the author
%would like to thank to Anders Bj\"orner for this opportunity.
%E-mail: {\tt tancer@kam.mff.cuni.cz}
%}}

\author{Alfredo Hubard\thanks{INRIA Sophia-Antipolis and Universit\'e
    Paris-Est Marne-la-Vall\'ee, France,\protect\url{alfredo.hubard@inria.fr}}\and Vojt\v{e}ch Kalu\v{z}a\thanks{Department of Applied Mathematics, Charles
    University, Malostransk\'{e} n\'{a}m\v{e}st\'{\i} 25, Prague 1,
    Czech Republic, \protect\url{kaluza@kam.mff.cuni.cz}}\and Arnaud de Mesmay\thanks{CNRS, Gipsa-Lab, 11 rue des Math\'ematiques, 38 400 Saint Martin d'Hères, France,\protect\url{arnaud.de-mesmay@gipsa-lab.fr}}\and Martin Tancer\thanks{Department of Applied Mathematics and Institute of
    Theoretical Computer Science, Charles University, Malostransk\'{e}
    n\'{a}m\v{e}st\'{\i} 25, Prague 1, Czech Republic,
    \protect\url{tancer@kam.mff.cuni.cz}}
}





\begin{document}

\maketitle
%\centerline{\'{E}ric Colin de Verdi\`{e}re, Alfredo Hubard, Vojt\v{e}ch
%Kalu\v{z}a,}
%  \centerline{Pavel Pat\'{a}k and Zuzana
%  Pat\'{a}kov\'{a}, and Martin Tancer}
%\centerline{Remarks/working notes}

\begin{abstract}
  The classical theorem of F\'{a}ry states that every planar graph can be
  represented by an embedding in which every edge is represented by a straight
  line segment. We consider generalizations of F\'{a}ry's theorem to 
  surfaces equipped with Riemannian metrics. In this setting, we require that
  every edge is drawn as a shortest path between its two endpoints and we
  call an embedding with this property a \emph{shortest path embedding}. The
  main question addressed in this paper is whether given a closed surface
  $S$, there exists a Riemannian metric for which every topologically
  embeddable graph admits a shortest path embedding. This question is also
  motivated by various problems regarding crossing numbers on surfaces.

  We observe that the round metrics on the sphere and the projective plane have
  this property. We provide flat metrics on the torus and the Klein bottle
  which also have this property.

  Then we show that for the unit square flat metric on the Klein bottle there
  exists a graph without shortest path embeddings. We show, moreover, that for
  large $g$, there exist graphs $G$ embeddable into the orientable surface of
  genus $g$, such that with large probability a random hyperbolic metric does
  not admit a shortest path embedding of $G$, where the probability measure is
  proportional to the Weil-Petersson volume on moduli space.

  Finally, we construct a hyperbolic metric on every orientable surface $S$ of
  genus $g$, such that every graph embeddable into $S$ can be embedded so that 
  every edge is a concatenation of at most $O(g)$ shortest paths.


  
  %of genus $g$, a 

  %On one hand, we show that if we consider a surface $S$ which is the sphere,
  %the real projective plane, the torus, or the Klein bottle, then $S$ admits a
 % metric such that every graph embeddable in $S$ admits a shortest path
 % drawing. In addition, for every surface $S_g$ of genus $g$ there is a metric
  %on $S_g$ such that every graph embeddable in $S_g$ can be drawn so that every
  %edge is a concatenation of at most $O(g)$ shortest paths.

 % On the other hand, we show that the most of the metrics on $S_g$ cannot serve
  %for shortest path drawings in certain natural probabilistic model. 
%\arnaud{Settle the uniqueness issue}

%\martin{It is not very clear from the statements whether $g$ is only orientable
%genus, or possibly non-orientable genus in general.}
 
\end{abstract}


\bigskip
%AMS Subject Classification: 05E45 

%\begin{abstract}
%We introduce a notion of strong $d$-collapsibility. Using this notion, we
%simplify the proof of Matou\v{s}ek and the author~\cite{matousek-tancer08} showing that the nerve of a
%family of sets of size at most $d$ is $d$-collapsible.

%\end{abstract}


\section{Introduction}
\subparagraph*{F\'{a}ry's theorem and joint crossing numbers.} A famous theorem of F\'{a}ry~\cite{f-oslrp-48} %(originally showed by K. Wagner~\cite{w-bv-36})
states that any simple planar graph can be
embedded so that edges are represented by straight line segments. In this article we investigate analogues of this theorem in the context of graphs embedded into surfaces. We focus on the following problem:
%Given a surface
%$S$, is there a metric on $S$ such that every graph embeddable into $S$
%can be embedded so that the edges are represented by shortest paths?
Given a surface $S$, is there a metric on $S$ such that every graph embeddable
into $S$ can be embedded so that edges are represented by
shortest paths?

We call such an embedding a \textit{shortest path
embedding}, and such a metric a \emph{\uni}.\footnote{We do not require that these shortest
paths are unique but as we will see later on, in the case of our positive
results, i.e., Theorem~\ref{t:shortest_paths} and~\ref{T:concat},
the uniqueness of the shortest paths can be obtained as well.).} 


 %There is a number of possible ways to generalise this theorem in the context of graphs embedded on surfaces. Schaefer  asked whether an analogue of Fary's theorem holds true if we substitute straight line segments with geodesic segments. A question to which Y. Colin de Verdiere had given a positive answer. Schaefer also hinted to an analogue of Fary's in which shortest paths substitute straight line segments, a version of this is the main focus of this paper, specifically we focus on the following question:

% In this
%article, we investigate a generalization of F{\'a}ry's theorem to the
%setting of surface-embedded graphs.
%There are many possible ways to generalize this theorem, due to
%the numerous choices of natural
%metrics on surfaces, and the
%various possible notions of
%straight-line segments. 

%For example Y. Colin de Verdiere has shown that every graph embeddable 

%\arnaud{I don't like the flow of this sentence, maybe we could reword this as it is in the abstract}

%Generalisations of F\'{a}ry's result are numerous and touch upon
%convex geometry, graph drawing, graphics and discrete differential
%geometry.

%The Circle packing theorem of Koebe-Andreev and Thurston generalizes F\'{a}ry's theorem. It claims that every planar graph can be represented as the contact graph of a family of euclidean closed discs with disjoint interiors. Another result of relevance to us is a theorem of Tutte who generalized F\'{a}ry's theorem introducing a physical idea: realize the topological graph representing the edges by a system of springs, fix the vertices of the outer face to be the vertices of a convex polygon and let the rest of the strings find their point of equilibria. The result is an embedding with straight lines. Moreover, the motion of the vertices follows an isotopy of embeddings from the original embedding to the position of equilibrium. 




Before being enticed by this question, we were motivated to consider it by a number of problems
involving joint embeddings of curves or graphs on surfaces
arising from seemingly disparate settings. The literature on the subject goes back at least 15 years
with Negami's work related to diagonal flips in
triangulations~\cite{n-cngepc-01}. He conjectured that there exists a
universal constant $c$ such that for any pair of graphs $G_1$ and
$G_2$ embedded in a surface $S$, there exists a homeomorphism
$h:S\rightarrow S$ such that $h(G_1)$ and $G_2$ intersect transversely
at their edges and the number of edge crossings satisfies
$cr(h(G_1),G_2) \leq c |E(G_1)|\cdot |E(G_2)|$. 


Recently, on one hand,
Matou\v{s}ek, Sedgwick, Tancer, and
U. Wagner~\cite{mstw-utsnc-13,mstw-e3sd-14}, working on decidability
of embeddability of $2$-complexes into $\mathbb{R}^3$ and on the other
hand, Geelen, Huynh, and Richter~\cite{ghr-epgm-13}, in a quest for
explicit bounds for graph minors, were faced with a similar question
and provided bounds for related problems. 
Joint crossing number type problems are dually
equivalent to problems of finding a graph with a specific pattern
within an embedded graph while bounding the multiplicity of the edges
used. This is a fundamental concern of computational topology of
surfaces where one is interested in finding objects with a fixed
topology and minimal combinatorial complexity, e.g., short canonical
systems of loops~\cite{lpvv-ccpso-01}, short pants
decompositions~\cite{cl-opdsh-07} or short octagonal
decompositions~\cite{ce-tnpcs-10}; see
also~\cite{chm-dsidts-15}. 



%\begin{conjecture}[{\cite[Conjecture~1]{n-cngepc-01}}]
%There exists a universal constant $c$ such that for any pair of graphs
%$G_1$ and $G_2$ embedded on a surface $S$, there exists a
%homeomorphism $h: S \rightarrow S$ such that $h(G_1)$ and $G_2$
%intersect transversely at their edges and the number of edge crossings satisfies
%\[ cr(h(G_1),G_2) \leq c |E(G_1)| |E(G_2)|\]
%\end{conjecture}
%Towards the design of an algorithm to decides
%embeddings of a $2$-complexes into $\mathbb{R}^3$, Matou\v{s}ek, Sedgwick, Tancer and 
%Wagner~\cite{mstw-utsnc-13,mstw-e3sd-14} regarding their work on
%embeddings of $2$-complexes into $\mathbb{R}^3$, as well as in the
%work of Geelen, Richter and Young~\cite{ghr-epgm-13} towards explicit
%bounds for graph minors.

Negami provided the upper bound $cr(h(G_1),G_2) \leq c g |E(G_1)|\cdot
|E(G_2)|$, and despite subsequent
discoveries~\cite{ab-tms-01,rs-tmlrs-05}, his conjecture is still
open.  %-- we note that Archdeacon and Bonnington~\cite{ab-tms-01}
%believe the conjecture to be false.  
In a paper that refines Negami's work~\cite{rs-tmlrs-05}, Richter and
Salazar wrote \textit{``this [conjecture] seems eminently reasonable:
  why should two edges be forced to cross more than once?''}. The
connection with our work is that if two graphs are embedded
transversally by shortest path embeddings, then indeed no two edges
cross more than once, since otherwise one of them could be
shortcut. We note that prior to our work, Schaefer~\cite[paragraph on
  Geodesic crossing numbers]{s-gcnvs-13} had considered similar
questions, mainly for drawing edges of a graph by geodesics. We
provide the details below including answers to some of Schaefer's
questions. We also note that our methods easily yield a new proof of
Negami's theorem for orientable surfaces; see
Corollary~\ref{c:negami}.% Finally, we
%remark that the existence of universal shortest path metrics will
%similarly imply a conjecture of Mohar~\cite[Conjecture~3.4]{m-gcn-09}
%that states that the genus crossing number and the degenerate crossing
%number of any graph coincide.

%Another formulation of our question is via the \textit{geodesic crossing numbers} introduced by Schaefer~\cite{s-gcnvs-13}.

\arnaud{More details to be added. I'm note sure what we should say about this}

\martin{I have again reformulated what to say about Schaefer. The reference to
the conjecture of Mohar needs an update. I also added a reference to a
Corollary for Negami's conjecture.}


Beyond crossing numbers, the existence or non-existence of shortest path universal
metrics might be relevant in curvature free and extremal Riemannian geometry.

%% Yet this is only one source of motivation. From the metric geometry point of view, the definition of shortest path embedding turns each topologically embeddable graph into a metric invariant, and naturally extends ideas from systolic geometry and discrete differential geometry. These are of relevance in topics as diverse as graphics and geometric modelling, where one needs canonical and stable representations of manifolds by discrete objects, and to certain models of quantum gravity, where much progress has followed (rigorous and not rigorous) analogies between polyhedral and Riemannian metrics. 
%% \arnaud{I think that direct motivations should be placed before the ones on crossing numbers. However, this paragraph feels very pretentious to me as it claims many connections but does not mean anything because it is super vague. Which ideas from systolic geometry and discrete differential geometry are extended? Graphics and geometric modelling are not very diverse topics, at least not from the point of view of the SoCG community (it's all about meshing), and these canonical or stable representations are already referred to above in ``computational topology of surfaces''. Analogies between polyhedral and Riemannian metrics are certainly nice, but I don't see the connection with our problem.}

  
  
  %\alfredo{feel free to erase the last sentence if you find it pretentious}
  %one intuition for this
%conjecture is provided by F\'ary's Theorem in the planar case, since
%straight-line segments can cross only once. The generalization of
%F\'ary's Theorem to surfaces that we are investigating would provide a
%rigorous footing for this intuition and towards Negami's conjecture
%and its various avatars, since shortest paths on Riemannian surfaces
%cross at most once as well (note that this does not hold for
%geodesics). \note{add details?}

%\arnaud{We could add some motivations regarding graph drawing: if we could choose the metric, this could allow to draw nicely a map on a surface which is already embedded in $R^3$}

%\alfredo{ I got to claim the implication and I also decided to be ambiguous...}

%% Specifically we were motivated by the following problem: What is the
%% minimal crossing number between two graphs each of which can be
%% embedded in the surface of genus $g$? Since shortest paths cross at
%% most once (otherwise one can be shortcut by the other one), for any
%% pair of two graphs $G_1$ and $G_2$ of genus g, with $|E(G_1)|=n$ and
%% $|E(G_2)|=m$, an appropriate generalisation of F\'{a}ry's theorem
%% would imply an upper bound of $O(mn)$ crossings which has been
%% conjectured by a number of authors.

%% The question of minimizing the number of crossings between two graphs has appeared in different contexts in the literature work of Negami as a natural question in graph drawing, in the work of... in an attempt to make effective the Seymour-Robertson theory and in the work of Matou\v{s}ek et al. as a subroutine for an algorithm that checks embeddability of two dimensional simplicial complexes into $3$-dimensional manifolds and in the work of Colin de Verdière et al. in relation to discrete systolic inequalities.... Similarly we would like to know what is the minimal crossing number between two systems of curves (two multi curves).

%% We will like to know if there is an analog of F\'{a}ry's theorem for graphs embedded on closed surfaces. However, there are a number of possible generalisation of F\'{a}ry's theorem in the realm of closed surfaces.

\subparagraph*{Related work.}Various results in graph drawing~\cite{t-hgdv-13} revolve around generalizing F\'ary's theorem to find drawings of graphs with additional constraints, for instance drawing the edges with polylines with few bends. On the other hand, only few
extensions to graphs embedded in surfaces are known. Two classical
avatars of F\'ary's theorem in the plane are of relevance to our work:
Tutte's barycentric embedding theorem~\cite{t-hdg-63} and the
Koebe-Andreev-Thurston circle packing theorem (see, for example, the
book of Stephenson~\cite{s-icptda-05}). Both have been generalized to
surfaces, providing positive answers to the following questions:

%There are various ways one can try to generalize F\'ary's theorem, and in particular past work provides positive answers to the following two natural approaches:

\begin{enumerate}
\item Given a surface $S$, a metric $m$, and a graph $G$ embeddable into
  $S$, can we embed the graph $G$ so that every edge is represented by
  a geodesic with respect to $m$?
\item Given a graph $G$ embeddable into $S$, does there exist a metric
  $m$ on $S$ so that $G$ embeds into $S$ with shortest paths?
\end{enumerate}


 %We had a lower bound for this problem in our paper on systoles. Generalising to the cases with boundaries would solve the problem of Matou\v{s}ek Sedgwick Tancer Wagner.

%- Dually, it would mean that one can draw $G_1$ on $G_2$ such that every edge of $G_1$ uses at most once every edge of $G_2$. This is new in general, and reproves known results in special cases. 

The first question was considered by Schaefer in~\cite{s-gcnvs-13}, a positive answer for many metrics had been previously given by Y. Colin de
Verdi\`ere~\cite{c-crgts-91} who generalized Tutte's barycentric embedding
approach using a variational principle. The idea behind this approach is to start with a
topological embedding of the graph, replace the edges by springs, and
let the system reach an equilibrium. Y. Colin de Verdi\`ere proved that for
any metric of non-positive curvature, the edges become geodesics with
disjoint interiors when the system reaches stability; moreover, this
embedding is essentially unique within its homotopy class. However,
geodesics need not be shortest paths, and two geodesics can intersect
an arbitrarily large number of times, see Figure~\ref{F:examples}. Yet, these examples do not provide a negative
answer to the second question, or to our main question, since we could
change the embedding by a homeomorphism of the torus (thus even
preserving the combinatorial map) to obtain a shortest path embedding.

\begin{figure}
  \centering
  \def\svgwidth{.9\textwidth}
  \input{examples.pdf_tex}
%  \includegraphics[width=.9\textwidth]{examples}
  \caption{a. and b. Two geodesics crossing many times. c. A grid embedded in a torus with geodesics. d. A reembedding of this grid with shortest paths.}
  \label{F:examples}
\end{figure}

%In fact our
%results are more naturally stated in terms of maps as it will be
%explained later.

%% The answer to the second question is a resounding no in general as we
%% will soon explain. But while this answer sounds obvious \note{does
%%   it?} we do not have an obvious counter-example.


%% The third question has a trivial answer: realize the faces of the
%% graph by euclidean regular polygons, this is a Riemannian metric with
%% singularities at the vertices, and certainly the edges are shortest paths.

The second question also has a positive answer, which can be proved via a generalization of the circle packing theorem to closed surfaces~\cite{s-icptda-05}. Namely, for every triangulation $T$ of a surface, there exists a
metric of constant curvature so that $T$ can be represented as the
contact graph of a family of circles. The representation of the triangulation that places a vertex at the center of its corresponding circle is an embedding with shortest paths. Such a representation can be computed efficiently and can be used as a tool for representing graphs on surfaces~\cite{m-dghp-99}. However, the metric is determined by the triangulation, which makes this approach ill-suited for our purpose.


%Circle packings have been developed into a whole theory through analogies with Riemann surfaces.
%Remark the analogy between the circle packing theorem and the uniformization theorem of Riemannian manifolds. This theorem states that for every metric $m$  on a surface $S$, there exist a metric of constant curvature $m_c$ on $S$ and a positive function $e^h:S\to \R^+$ such that at each point $s\in S$, the Riemannian metric $m(s)$  can be expressed as the product $e^{h(s)} m_c(s)$. Metrics of constant curvature themselves are a rich topic themselves. The Gauss-Bonnet theorem implies that the sign of the curvature is determined solely by the topology of the surface. 
 %The sphere and the projective plane accept a metric of positive constant curvature which we sometimes refer as the round metric. The Torus and the Klein bottle accept metrics of $0$ constant curvature, which we sometimes refer as flat. The rest of the closed surfaces accept a metric of negative constant curvature, which we sometimes refer as hyperbolic. In the case of the sphere and projective plane there is only one such metric, but already in the case of the torus and Klein bottle we see an infinite number of non isometric metrics of constant curvature. For larger genus $g$, the different metrics of constant curvature $-1$ form a space of dimension which is covered by a convex set of $\mathbb{R}^{6g-6}$.
 %have a a number of applications, in graph drawing
% Mohar~\cite{m-ptcpa-93, m-cpmpt-97} metric geometry and discrete conformal geometry. %As we will remark later, in the process of
%circle-packing, the metric chosen depends heavily on the given
%triangulation. 


%% This theorem
%% generalizes to infinite planar graphs in the plane, and to graphs and
%% circles on the sphere, moreover, there exists a rigidity result
%% claiming uniqueness that for a triangulation the correspodning circle
%% packing representation is unique upto Möbius transformations. Using
%% these two results on the universal cover of the surface $S_g$ provides
%% a $\pi_1(S_g)$ equivariant circle packing on the hyperbolic plane,
%% euclidean plane, or sphere correspondingly. Here the circle packing is
%% determined upto a Möbius transformation and so the conjugacy class of
%% the representation of $\pi_1(S_g)$ on the group of Mobiles
%% transformations is well defined. The action is free, discrete and
%% cocompact, so quotiening by this group of isometries we obtain a
%% surface of constant curvature and the circles on the universal cover
%% are mapped to circles on this geometric structure. Notice that during
%% this process the graph $G$ "chooses" a metric $m$ (see the book of
%% Stephenson~\cite{s-icptda-05} or the papers of Mohar~\cite{m-ptcpa-93,
%%   m-cpmpt-97} on the topic).

%The question whether there is a F\'{a}ry theorem on surfaces is also asked in a
%survey by Schaefer~\cite{s-gcnvs-13} via the \textit{geodesic crossing
%numbers}. Schaefer mainly focuses of drawings with geodesics; however, he also
%asks whether there is any difference if we consider shortest paths instead of
%geodesics. The aforementioned result of Y. Colin de Verdi\`ere settles
%Schaefer's question for geodesics in large generality. For the shortest paths,
%our results below, namely Theorem~\ref{negative}, show that the drawings with shortest paths behave
%differently.

\subparagraph*{Our results.} Our objective here is a mix of these last two results. 
%: we are
%looking for a metric for which every graph admits a shortest path
%embedding. 
On the one hand, we require shortest paths and not geodesics, on the
other hand, we want a single metric for each surface and not one which
depends on the triangulation. We will also consider the relaxation of
our problem where we are allowed to use concatenations of shortest
paths: we say that a metric is a \textit{k-universal shortest path metric} if every topologically
embeddable graph can be represented by an embedding in which edges are
drawn as concatenations of $k$ shortest paths. This is akin to various
problems in graph drawing where graphs are embedded with polylines
with a bounded number of bends instead of straight
lines~\cite{ek-sepgfb-05,t-eggmnb-87}.

Our results focus on Riemannian metrics of constant curvature, and our techniques are organized by the sign of the curvature. We first observe that for the sphere and the projective plane, since there is a unique Riemannian metric of curvature $1$, the circle
packing approach applies to all graphs. Then, with the aid of \emph{irreducible triangulations}, we provide flat metrics (i.e., of zero curvature) on the torus and the Klein bottle for which every graph
admits a shortest path embedding.

%% \begin{restatable}{theorem}{tshortestpaths}\label{t:shortest_paths}
%% For each of the surfaces $S^2$, $\RP^2$, the torus $T^2$ and the Klein bottle
%% $K$, there is a metric on them with the following property. Let $G$ be a
%% triangulation of one of these surfaces. Then $G$ can be embedded in that surface so that all the edges
%% are shortest paths.
%% \end{restatable}

\begin{restatable}{theorem}{tshortestpaths}\label{t:shortest_paths}
The sphere $S^2$, the projective plane $\RP^2$, the torus $T^2$, and the Klein bottle
$K$ can be endowed with a \uni.
\end{restatable}
%\martin{I have changed all $K^2$ into $K$ for consistency. I hope that it is
%not a big harm if $K$ is the only surface missing the superscript in this case.}

This result could lead to the idea that shortest path embeddings can
be achieved for any metric, i.e., that every metric is a \uni. We prove
that this is not the case already for the unit square flat metric
on the Klein bottle (arguably the first example to consider).

\begin{restatable}{theorem}{tklein}\label{t:klein}
Let $K$ denote the Klein bottle endowed with the unit square flat
metric on the polygonal scheme $aba^{-1}b$. Then there exists a graph embeddable into $K$
which cannot be embedded into $K$ so that the edges are shortest paths.
\end{restatable}

In higher genus, the number of irreducible triangulations is too large to check all cases by hand. Hyperbolic surfaces of large genus are hard to comprehend, but the probabilistic method allows us to show that if there exists universal shortest path metrics of constant curvature $-1$ at all, their fraction tends to $0$ as the genus tends to infinity.%metrics fails even more dramatically with the following theorem.

%% \begin{restatable}{theorem}{Tnegative}\label{negative}
%% There exists a family of graphs $G_g$ embeddable on a surface of genus $g$ such that, with probability tending to $1$ as $g$
%% goes to infinity, there is no shortest path embedding of $G_g$ on a
%% random hyperbolic metric on $S_g$. Moreover, for any fixed $\varepsilon$, there is also no
%% embedding such that the edges are concatenations of
%% $O(g^{1/3-\varepsilon})$ shortest paths.
%% \end{restatable}
\begin{restatable}{theorem}{Tnegative}\label{negative}
For any $\varepsilon>0$, with probability tending to $1$ as $g$ goes to infinity, a random
hyperbolic metric is not a $O(g^{1/3-\varepsilon})$-\uni. In particular, with probability tending to $1$ as $g$ goes to infinity, a random hyperbolic metric is not a universal shortest path metric.
%% there exists a family of
%% graphs $G_g$ embeddable on a surface $S$ of genus $g$ such that, with
%% probability tending to $1$ as $g$ goes to infinity, in every embedding
%% of $G$ into $S$ endowed with a random metric there exists an edge
%% requiring at least $O(g^{1/3-\varepsilon})$ concatenations of shortest
%% paths.
%random hyperbolic metric on $S_g$. Moreover, for any fixed $\varepsilon$, there is also no
%embedding such that the edges are concatenations of
%$O(g^{1/3-\varepsilon})$ shortest paths.
\end{restatable}

Here the probability measure on the space hyperbolic surfaces is proportional to the Weil-Peterson volume, see Section~\ref{S:pants}. Our proof is an application of deep
results on this volume by Mirzakhani~\cite{m-gwpvrh-13} and Guth, Parlier, and Young~\cite{gpy-pdrs-11}.

For a given graph $G$ and a metric $m$ on $S$, Schaefer~\cite{s-gcnvs-13}
defines the \emph{geodesic crossing number} of $G$ as the minimal number of
crossings of any drawing of $G$ in $S$ in which edges are represented by
geodesics. Schaefer asks if this definition is equivalent to the analogous
definition with shortest paths instead of geodesics. Notice that the examples
in Theorems 2 and 3 have nonpositive curvature, hence, combined with the
aforementioned result of Y. Colin de Verdi\`ere imply that some graphs have geodesic crossing number zero but \emph{shortest path crossing number} nonzero, answering Schaefer's question. 

For genus $g>1$ we do not know if there exist shortest path universal
metrics. But relaxing the question to concatenations of shortest paths
and combining ideas from hyperbolic geometry and computational
topology, we provide for every orientable surface of genus $g$ an
$O(g)$-universal shortest paths metric. The proof relies on the
octagonal decompositions of \'E. Colin de Verdi\`ere and
Erickson~\cite{ce-tnpcs-10} and a variant of the aforementioned
theorem of Y. Colin de Verdi\`ere~\cite{c-crgts-91}.

%which allows to embed graphs as
%concatenations of $O(g)$ shortest paths. 
 %or when
%straight-line drawings are not possible.

\begin{restatable}{theorem}{Tconcat}\label{T:concat}
For every $g>1$, there exists an $O(g)$-universal shortest path
hyperbolic metric $m$ on the orientable surface $S$ of genus $g$.
\end{restatable}

%In this article, we choose to focus on Riemannian metrics of constant
%curvature as a paradigm of simple, or ``nice'' metric. Another case
%could be made in favor of piecewise-Euclidean metrics, which are more
%commonplace in applications and easier to compute with.  
In this article we focused on Riemannian metrics of constant
curvature, but we remark that both of our last results also hold in some setting of piecewise-Euclidean metrics as
well. For the upper bound, it suffices to replace hyperbolic hexagons
with Euclidean ones, and the rest of the proof works similarly. 
The lower bound can be derived following the heuristic strong parallels between the
Weil-Petersson volume form on moduli space and the counting measure on
the space of $N=4g$ Euclidean triangles randomly glued together. In
particular the results that we use have analogs in this latter
space: see Brooks and Makover~\cite{bm-rcrs-04} and the second half of
the article of Guth, Parlier, and Young~\cite{gpy-pdrs-11}.
%Incidentally, recall that the uniformization theorem states that for every smooth Riemannian metric $m$ on a surface of genus $g$, $S_g$, there exists a unique smooth function $f\colon S_g \to \mathbb R$ and a metric of constant curvature $m_{c}$, such that $m=e^{f}m_c$. %Our results only discuss a space of finite dimension in the infinite dimensional space of all Riemannian metrics.
%\arnaud{Still Not sure what is the point of this last incidental remark}


%\arnaud{I am not sure we should state this as this is not obvious at all: Brooks and Makover prove it with ideal triangles instead of Euclidean triangles but I believe their proof adapts. Guth Parlier and Young only allow taking paths in the 1-skeleton of the triangulation but I believe it holds as well. I will verify.}

%\arnaud{Update: in the Euclidean setting,it is enough to bound the diameter of the graph, which is easy (eg done by bollobas). For the lengths of pants decompositions, if things are short inside the triangles, one can push them on the edges with a cost at most 2 in length, so they are short in the 1-skeleton as well.}

We have stated our results for graphs in this introduction. We note
that one could consider the problem of shortest path embeddings for a
graph with a fixed embedding up to a homeomorphism of the surface
(i.e., for a combinatorial map), which is more in the spirit of
Negami's and Mohar's conjectures. Our positive results can be stated in this
stronger version; i.e., in our proofs the map is preserved. Our
negative results would be weaker if the map had to be preserved, and
in fact the proofs deal firstly with the statements for maps and then
we derive the analog for graphs with some extra work. 
%Also, one
%could also require the shortest paths in our embeddings to be unique,
%so as to mimick more accurately the planar case. 

\subparagraph*{Open questions.} The main open question is the existence of universal shortest path
metrics, or $O(1)$-universal shortest path metrics. Natural candidates
for these are given by certain celebrated extremal metrics like the ones occurring as lower bounds for Gromov's
systolic inequality \cite{bs-pmrsl-94,gro-83}.

Lists of irreducible triangulations exist for the double torus and the non-orientable surface of genus up to four~\cite{s-gits-06}. While the numbers are too big to be investigated by hand as we did for the torus and the Klein bottle, it may be possible to investigate some computerized approach to test their shortest path embeddability for some well chosen hyperbolic metric.

Our Theorem~\ref{T:concat} only deals with orientable surfaces. A similar approach might work for non-orientable surfaces as well, the key issue being to generalize the octagonal decompositions of \'E. Colin de Verdi\`ere and
Erickson~\cite{ce-tnpcs-10} to the non-orientable setting. We leave this as an open problem.


\subparagraph*{Outline.} After introducing the main definitions in Section~\ref{S:prelim}, we will prove Theorems~\ref{t:shortest_paths}, \ref{t:klein}, \ref{negative}, and~\ref{T:concat} in Sections~\ref{S:shortest-paths}, \ref{S:klein}, \ref{S:pants}, and~\ref{S:concat}, respectively.


%% But what if we don't let $G$ choose the
%% metric? This lead us to the last of the previous questions, and to the
%% first of our results. In section $2$ we show that there are graphs
%% embeddable in the Klein bottle that cannot be embedded with shortest
%% paths on the Klein bottle with the flat square metric. In section $3$
%% we take things one step further and show that for large enough $g$
%% there exist embeddings of graphs $G$ (maps) such that almost no metric
%% of constant curvature accepts a shortest path embedding of this map.

%% There is however the chance that there exists a very special metric for which all graphs accept shortest path embeddings. This is our last and fundamental question (and its variation).

%% \begin{itemize}\item Is there a metric $m$ on $S_g$ such that every graph $G$ of genus $g$ has a shortest path embedding into $(S_g,m)$?
%% \item Is there a metric $m$ on $S_g$ and a number $k(g)$ such that every graph embeds in $S_g$ with edges represented as a concatenation of $k$ shortest paths? 
%% \end{itemize}

%% Using circle packings we answer this (sixth and main) question in the positive for the sphere and the projective plane. Using minimal triangulations we answer it, again in the positive, for the torus and the Klein bottle. In general we don't conjecture a positive answer but point out that metrics that are extremal with respect to the systolic inequality are good candidates to answer this question. 
%% In section.. we provide an estimate on $k(g)=O(g)$ answering the last question in the list. The strategy is to cut the embedded graph into pieces which are topologically simple and have small combinatorial complexity. Then geometrize each of these pieces with a canonical hyperbolic metric. Finally we paste the pieces so that they yield a hyperbolic metric on $S_g$ that does not depend on the graph. 

%% Fortunately the last result has as corollaries, improvements to some of the computational and combinatorial problems that motivated this research.

%% In particular the previous result provides bounds on the lengths of canonical systems of loops~\cite{lpvv-ccpso-01}, pants decompositions~\cite{cl-opdsh-07}, octagonal decompositions~\cite{ce-tnpcs-10}. Furthermore, this is unknown for canonical systems of loops of non-orientable surfaces, a question that has attracted some attention.  (eg it's been open for a while and I know people who tried hard).

%% \alfredo{I guess I should cut and paste the main results from the sections to this introduction, this is just a first brainstorming, I still need to work more on the embedding of two graphs theme but I need to read the paper by negate and the follow up...please add change subtract, criticise}

%%  (In the following we implicitly assume that shortest paths, geodesics, volume, etcetera, are always with respect to the Riemannian metric).

%(Construct a counterexample?)

%A related question was addressed by Yves Colin de Verdière, who showed that if $m$ is a metric of non positive curvature then $G$ can be embedded in $S_g$ with edges represented by curves that are geodesics with respect to $m$. 

%In fact, what Colin de Verdière~\cite{c-crgts-91}  shows if the graph is embedded by $f$, then there exists a map $h$ which is homotopically equivalent to $f$, so that $h$ embeds the edges as geodesics. Notice however that this falls short to answer our question. Indeed geodesics need not be shortest paths. If we draw the cycle of $3$ vertices on a flat torus so that this cycle twists around 10000 times in the vertical direction as it twists once in the horizontal direction, then, any homotopy equivalent embedding will have at least one very long edge.

%In this case however, it is easy to redraw the graph, so that it is drawn with shortest paths. Alternatively we could change the metric so the edges are shortest paths. This suggests the following variation of question 1.

%2.-Given a graph $G$, does there exist a metric $m$ so that $G$ embedds in $S_g$ with shortest paths?

%The answer to this second question is trivially yes. The following variation is less trivial.

%2b.-Given a graph $G$, does there exist a metric $m$ of constant curvature so that $G$ embeds in $S_g$ with shortest paths?

%The answer is again yes, but this time we need to invoke a version of the circle packing theorem of Koebe-Andreev and Thurston  (see the book of Stephenson~\cite{s-icptda-05} or the papers of Mohar~\cite{m-ptcpa-93, m-cpmpt-97} on the topic). Recall that this theorem claims that for every graph $G$ embedded in $S_g$, there exists a metric of constant curvature $m_G$ (which is unique in the case that $G$ is a triangulation) such that $G$ is the contact graph of circles on $S_g$. It is easy to see that the geodesics between circles in contact are shortest paths. With this lesson we revisit the first question.

%1b.- Given a hyperbolic metric $m$ and a graph $G$ on $S_g$ is it possible to embed the graph with shortest paths?

%Finally we arrive at perhaps the most interesting among these questions.

%3.-Is there a (universal) metric $m$ on $S_g$ such that for every graph $G$ on $S_g$ can be embedded with shortest paths?

%In fact for the computational an combinatorial applications that we have in mind a weaker positive solution of this question is sufficient, specifically. 

%3b.-Is there a metric $m$ and a constant $c_g$ such that every graph $G$ on $S_g$ can be embedded with edges represented by concatenations of at most $c_g$ shortest paths?



%\subsection{Applications}


% Very natural question...

% Crossings of graphs: if questions 3 or 3b have positive answers, then since shortest paths cross at most once (otherwise one can be shortcut by the other one), for any pair of two graphs $G_1$ and $G_2$ of genus g, there exist embeddings of $G_1$ and $G_2$ with $O(mn)$ crossings. We had a lower bound for this problem in our paper on systoles. Generalizing to the cases with boundaries would solve the problem of Matou\v{s}ek Sedgwick Tancer Wagner.

% Dually, it would mean that one can draw $G_1$ on $G_2$ such that every edge of $G_1$ uses at most once every edge of $G_2$. This is new in general, and reproves known results in special cases. In particular the previous result provides bounds on the lengths of canonical systems of loops~\cite{lpvv-ccpso-01}, pants decompositions~\cite{cl-opdsh-07}, octagonal decompositions~\cite{ce-tnpcs-10}. Furthermore, this is unknown for canonical systems of loops of non-orientable surfaces, a question that has attracted some attention.  (eg it's been open for a while and I know people who tried hard).

%\bigskip

%\subsection{Results}

% For questions 3 and 3b, it is enough to check that it holds for minimal triangulations. Hence, the sphere and the projective plane of constant curvature are universal. For the flat square torus it is doable,. We did that in Ouessant. (what about other flat toruses?)
 %(The Klein bottle, the double torus? is there an algorithm that checks this for a given hyperbolic metric given in the form of the corresponding group of hyperbolic isometries or in techmuller coordinates?)

%- In contrast, most hyperbolic metrics are not "universal". For a fraction of hyperbolic metrics going to $1$ as $g\to \infty$ there exists a graph that does not embed with shortest paths.

%- We provide a hyperbolic metric so that every graph of genus $g$ can be embeddeed in it with $O(g)$ concatenations of shortest paths.

%- To prove this last result, we provide an algorithm to compute a pants decomposition of fixed combinatorial type of constant multiplicity (see below for exact statement). This may be interesting in its own right (eg it solves the problem of Matou\v{s}ek Sedgwick Tancer Wagner without boundaries -- this is what we discussed in Ouessant).


%\bigskip

%\subsection{Main open questions}

%- Does there exist a ``universal'' hyperbolic metric to embed every graph with shortest paths? This is not ruled out by the theorem of section 3. Good candidates: Buser-Sarnak, Hurwitz, platonic surfaces? 

%- Can one obtain the result of section 4 for any hyperbolic metric? Improve on it?

%- Improve on the $\Omega(g^{1/6})$ lower bound?

%- Compare different metrics.  We could consider a sort of dual set of questions where the graph is fixed and we ask for a metric on which the graph intersects. We could use a metric on graphs, $d_{S_g}(G,G')$ as the least number of crossings between two drawings of $G$ and $G'$ where the embeddings might not be transversal and by definition when two edges are the same then they do not cross. How does this compare with the metrics to the flip metric on triangulations, with the Teichmuller metric, with the Gromov Hausdorff, Thurston, Weil-Petersson, etc.
%\note{Your definition is super fishy, do you hae a way to make it rigorous?}


\section{Preliminaries}\label{S:prelim}

In this article we only deal with compact surfaces without
boundaries. By the classification theorem, these are characterized by
their \textit{orientability} and their \textit{genus}, generally
denoted by $g$. Orientable surfaces of genus $0$ and $1$ are
respectively the \textit{sphere} $S^2$ and the \textit{torus} $T^2$,
while non-orientable surfaces of genus $1$ and $2$ are the
\textit{projective plane} $\mathbb{R}P^2$ and the \textit{Klein
  bottle} $K$. The orientable surface of genus $g$ is denoted by $S_g$. The \textit{Euler genus} is equal to the genus for non-orientable surfaces and equals twice the genus for orientable surfaces.


By a \textit{path} on a surface $S$ we mean a continuous map $p: [0,1]
\rightarrow S$, and a \textit{closed curve} denotes a continuous map
$\gamma: S^1 \rightarrow S$. These are \textit{simple} if they are
injective.  We will be using occasionally the notions of
\textit{homotopy}, \textit{homology}, and \textit{universal cover}, we
refer to Hatcher~\cite{h-at-02} for an introduction to these
concepts.
%\martin{Changed `punctually' to `occasionally'. I think that
%  `punctually' has a different that the intended meaning. (Or I am
%  misunderstanding something.)}  \arnaud{Indeed thanks, I got confused
%  by the French word ``ponctuellement'' which means yet another thing}
All the graphs that we consider in this paper are \textbf{simple}
graphs unless specified otherwise, i.e., loops and multiple edges are
disallowed. An \textit{embedding} of a graph $G$ into a surface $S$
is, informally, a crossing-free drawing of $G$ on $S$. We refer to
Mohar and Thomassen~\cite{mt-gs-01} for a thorough reference on graphs
on surfaces, and only recall the main definitions. A graph embedding
is \textit{cellular} if its faces are homeomorphic to open
disks. Euler's formula states that $v-e+f=2-g$ for any graph with $v$
vertices, $e$ edges, and $f$ faces cellularly embedded in a surface
$S$ of Euler genus $g$. When the graph is not cellularly embedded,
this becomes an inequality: $v-e+f \geq 2-g$. A \textit{triangulation}
of a surface is a cellular graph embedding such that all the faces are adjacent to three edges. By a slight abuse of language, we will
sometimes refer to an embedding of a triangulation, by which we mean
an embedding of its underlying graph which is homeomorphic to the
given triangulation.
%\alfredo{Aren't we better of defining
%  triangulations as simplicial complexes this time?}\arnaud{Why?
%  Since we need to define graph embeddings and faces anyway, this
%  seems easier.}\alfredo{irreducible triangulations are simplicial
%  complexes, actually everything we define}\arnaud{Sure, but defining
%  simplicial complexes seems longer to me than defining embeddings
%  with triangular faces}
A \textit{pants decomposition} of a surface
$S$ is a family of disjoint curves $\Gamma$ such that cutting $S$
along all of the curves of $\Gamma$ gives a disjoint union of pairs of
pants, i.e., spheres with three boundaries. Every surface except the
sphere, the projective plane, the torus, and the Klein bottle admits a pants decomposition
with $3g-3$ closed curves and $2g-2$ pairs of pants. Note that all the pants
decompositions are not topologically the same, i.e., are not related by a
self-homeomorphism of the surface. A class of pants decompositions
equivalent under such homeomorphisms will be called the (topological)
\textit{type} of the pants decomposition. We say that an embedding
$f:G \rightarrow S$ \textit{contains a pants decomposition} if there
exists a subgraph $H \subseteq G$ such that $f:H \rightarrow S$ is a
pants decomposition of $S$.

In this article, we will also be dealing with notions coming from
Riemannian geometry, we refer
to the book of do Carmo for more background~\cite{c-rg-92}. By a
\textit{metric} we always mean a Riemannian metric, which associates
to every point of a surface the \textit{curvature} at this point. The
Gauss-Bonnet theorem ties geometry and topology; it implies that the
sign of a metric of constant curvature that a topological surface
accepts is determined solely by its Euler genus.  
%The uniformization theorem in Riemannian geometry states that for every metric $m$ on a surface $S$, there exists a metric of constant curvature $m_c$ on $S$ and a positive function $e^h:S\to \R^+$ such that at each point $s\in S$, the positive definite bilinear form $m(s)$  can be expressed as the product $e^{h(s)} m_c(s)$. Metrics of constant curvature themselves form a world of their own. The Gauss-Bonnet theorem ties geometry and topology; it implies that the sign of a metric of constant curvature that a topological surface accepts is determined solely by the Euler characteristic of the surface.   
 %By the Gauss-Bonnet theorem, a metric of
%\vojta{I know nothing about Riemannian geometry, but I have a stupid question. What is the meaning of superscript $h$ above? Was it defined somewhere earlier?}
%\arnaud{h is any function. But why is uniformization relevant anyway? Euler characteristic is undefined for now.}
%constant curvature on a surface is very restricted: 


 A Riemannian metric induces a length functional on paths and
closed curves. A path or a closed curve is a
\textit{geodesic} if the functional is locally minimal. Shortest paths between
two points are global minima of the length functional. Unlike in the plane, geodesics are not,
in general, shortest paths; in addition, neither geodesics nor shortest paths are unique in general. %On the sphere $S^2$ and the projective plane
%$\mathbb{R}P^2$, there exists a unique metric of positive curvature up
%to M\"obius transformations \note{define}. This uniqueness does not
%hold anymore for other surfaces, and this gives rise to the
%\textit{Teichm\"uller} and \textit{moduli spaces} of a surface. We
%refer to Farb and Margalit~\cite{fm-pmcg-11}, for an introduction to
%these themes, and will only introduce the notions that we will need in
%Section~\ref{S:pants}.
%A graph $G$ embedded in a surface $S$ endowed with a metric $m$ is
%said to admit a \textit{shortest paths embedding} if there exists an
%embedding of $G$ into $S$ such that all the edges are realized as
%shortest paths between their endpoints. 
If we have a shortest path embedding of a graph where every edge is drawn as
the
unique shortest path between its endpoints, we speak of \textit{shortest
paths embedding with uniqueness}.
%if, furthermore, these shortest paths are unique.

%\arnaud{Unique shortest paths embedding is ambiguous (unique might refer to the paths or the embedding). Feel free to add things that are needed in the preliminaries}
%\alfredo{what about short paths embedding and shortest path embedding when we have uniqueness? }

\section{Shortest path embeddings through minimal triangulations}\label{S:shortest-paths}


%Incidentally, notice that a triangulation $T$ is minimal (or irreducible) if it has systole 3 and every edge is on a systole.
%\martin{I guess that $S^2$ should be excluded for the claim above. In addition
%$T$ was used both for a triangulation and for the torus. I suggest to use $T^2$
%for the torus and for coherence $K^2$ for the Klein bottle.}

%\begin{theorem}
%Let $G$ be a triangulation of $S^2$, $RP$, the torus $T$, or the Klein
%Bottle $K^2$. Endow $S^2$ and $RP^2$ and $K$ with the round metric of positive constant curvature, (for $K$ this metric is singular) and $T$ with the $0$ curvature metric given by a identifying a paralelogram of angles $\frac{\pi}{3}$,$\frac{\pi}{6}$ then $G$ can be embedded so that all the edges are shortest paths.
%\end{theorem}
%\martin{Here I present a version of the theorem above corresponding to our
%current knowledge. How to denote the real projective plane. I would be slightly
%in favor of using $\RP^2$. Is it OK?}
%
%\arnaud{No strong opinion.}
%
%\alfredo{I agree, $\RP^2$}
%\martin{Uniqueness should be mentioned here (at least for the induction).}

\tshortestpaths*

%% \begin{theorem}
%% \label{t:shortest_paths}
%% For each of the surfaces $S^2$, $\RP^2$, the torus $T^2$ or the Klein bottle
%% $K^2$,
%% there is a metric on them with the following property. Let $G$ be a
%% triangulation of this surface. Then $G$ can be embedded so that all the edges
%% are shortest paths.
%% \end{theorem}
In the theorem above, for $S^2$ and $\RP^2$ we use the round metric of
positive constant curvature scaled to $1$. In the case of torus we use
the flat metric obtained by the identification of the opposite edges
of the square. In the case of the Klein bottle we can show that an
analogous result fails with the flat square metric on the polygonal
scheme $aba^{-1}b$, as we will see in Section~\ref{S:klein}. But we
can get the result for the metric obtained by the identification of
the edges of a rectangle of dimensions $1 \times b$ where $b =
\sqrt{4/3} + \varepsilon$ for some small $\varepsilon > 0$. (The edges
of length $1$ are identified coherently, whereas the edges of length
$b$ are identified in opposite directions.)

In all cases we can get shortest path embeddings with uniqueness. Actually, for
the torus and the Klein bottle, uniqueness will be a convenient assumption for
inductive proofs.

%In the case of $S^2$ and $\RP^2$ the result easily follows from already known
%results on circle packing as we describe in the following subsection. For $T^2$
%and $K^2$ we use an approach via minimal triangulations described in
%subsection~\ref{s:minimal}.


%Remark: In the cases of the Klein bottle and the Torus, the flat square metrics also work.

%\note{Unclear whether we should prove it for the systolic optimal metric of for the natural square ones.}

\subparagraph*{The sphere and the projective plane.} 

%This could also be argued via circle packings and that is the approach we follow for the sphere.
%As stated in the introduction, for the sphere and the projective plane the result follows from the circle
%packing theorem. 
%Corollary 13.6.2 of Thurston's states that for a given
%graph $G$ embedded on the sphere, there exists a circle packing $\mathcal{P}$
%whose intersection graph is isotopic to the graph $G$. 
%Notice that if we
%endow the sphere with the constant curvature metric, the boundary of a metric
%ball corresponds to a circle.  Placing the vertices of the graph at the centers
%of the circles yields a shortest path embedding. 

%\arnaud{Pushed the proof to the appendix}

The circle packing theorem states that any triangulation of the sphere
can be represented as the contact graph of circles on the
sphere~\cite[Theorem~4.3]{s-icptda-05}, endowed with the usual
metric. Since any graph can be extended into a triangulation (adding new vertices if needed), and
paths between centers of circles are shortest paths, this proves
Theorem~\ref{t:shortest_paths} for $S^2$. 

\bigskip

For the projective plane, a similar circle packing theorem follows
from the spherical case, yet since we could not find a reference in
the literature we include a proof here.

\begin{proposition}
The $1$-skeleton of every triangulation $T$ of the projective plane is the contact graph of a packing of circles on the projective plane, endowed with the spherical metric.
\end{proposition}

\begin{proof}
The main ingredient is that the circle packing theorem for the sphere
not only states that for every graph $G$ triangulating the sphere,
there exists a packing of circles $P$ such that $G$ is isomorphic to
the intersection graph of $P$, but also that $P$ is unique up to a
M\"{o}bius transformation (see Stephenson~\cite{s-icptda-05}).

The proposition can be derived from this and the following fact about
M\"{o}bius maps acting on the sphere: for every M\"{o}bius map $\phi$
such that $\phi\circ \phi=Id$ and $\phi$ is fixed-point free there
exists a M\"{o}bius map $\tau$ such that $\tau^{-1} \phi \tau$ is the
antipodal map $x \to -x$, see \cite{wil-81}.  \martin{Added that
  $\phi$ must be fixed-point free.}


Indeed, let $T$ be a simplicial complex homeomorphic to the projective
plane, i.e., $f \colon T \to \RP^2$ is a homeomorphism. Let $\pi: S^2
\to \RP^2$ be the universal covering map. Let $\hat{T}$ be the
simplicial complex homeomorphic to the sphere such that
$\hat{f}:\hat{T}\to S^2$ is a homeomorphism and $f^{-1}\circ \pi \circ
\hat{f}\colon \hat{T} \to T$ is the simplicial double cover of
$T$. %The
%important fact is that the antipodal map on the sphere pulls back to a fixed
%point free map from $a \colon \hat{T} \to \hat{T}$ such that $a \circ a=id$.
The antipodal map on $S^2$ (together with $f$ and with the fact that
$\hat{T}$ comes from $T$) induces a fixed
point free map $a \colon \hat{T} \to \hat{T}$ such that $a \circ a=id$.
There exists a packing $P$ that has the $1$-skeleton of $\hat{T}$ as its
intersection graph. The same packing has also the $1$-skeleton of $a(\hat{T})$
as its intersection graph (where the labels of the vertices are changed). 
The uniqueness of the packing
implies that there exists a M\"{o}bius transformation $\phi$ 
that preserves $P$ as an unlabelled collection circles, but switches the circle
corresponding to vertex $v$ in $T$ with the circle corresponding to $a(v)$. 
Since $a$ is fixed point free and $a \circ a=id$, the
same holds for $\phi$. Hence there exists $\tau$ such that $\tau^{-1} \phi
\tau$ is the antipodal map, and so $\tau^{-1} (P)$ is an antipodally invariant
circle packing whose intersection graph is the $1$-skeleton of $\hat{T}$.
Passing to the quotient $\pi\colon S^2 \to \RP^2$, we obtain the desired
packing on $\RP^2$.  

\end{proof}

%% ALFREDO'S VERSION
%% The circle packing theorem on the sphere states that for every graph $G$
%% embedded in the sphere, there exists a packing of circles $P$ such that $G$ is
%% isomorphic to the intersection graph of $P$. If the graph $G$ triangulates the
%% sphere, then $P$ is unique upto a M\"{o}bius transformation (see
%% Stephenson~\cite{s-icptda-05}). The existence of circle packings for any graph
%% follows from the case of triangulations. We show here that the circle packing theorem also holds
%% for the projective plane with the round metric, i.e., the $1$-skeleton of every
%% triangulation $T$ of the projective plane is the intersection graph of a
%% packing of circles on the projective plane. This theorem can be derived from
%% the circle packing on the sphere and the following fact about M\"{o}bius maps acting on the
%% sphere: for every M\"{o}bius map $\phi$ such that $\phi\circ
%% \phi=Id$ and $\phi$ is fixed-point free 
%% there exists a M\"{o}bius map $\tau$ such that $\tau^{-1} \phi \tau$
%% is the antipodal map $x \to -x$, see \cite{wil-81}.  
%% \martin{Added that $\phi$ must be fixed-point free.}
%% Now let $T$ be a
%% simplicial complex homeomorphic to the projective plane, i.e., $f \colon T \to
%% \RP^2$ is a homeomorphism. Let $\pi: S^2 \to \RP^2$ be the universal covering
%% map. Let $\hat{T}$ be the simplicial complex homeomorphic to the sphere such
%% that $\hat{f}:\hat{T}\to S^2$ is a homeomorphism and $f^{-1}\circ \pi \circ
%% \hat{f}\colon \hat{T} \to T$ is the simplicial double cover of $T$. %The
%% %important fact is that the antipodal map on the sphere pulls back to a fixed
%% %point free map from $a \colon \hat{T} \to \hat{T}$ such that $a \circ a=id$.
%% Let $\iota$ be the antipodal map on $S^2$, observe that the map  $a=\hat{f}^{-1}\circ \iota \circ \hat{f}$ is fixed
%% point free and $a \circ a=id$. There exists a packing $P$ that has the $1$-skeleton of $\hat{T}$ as its
%% intersection graph. The same packing has also the $1$-skeleton of $a(\hat{T})$
%% as its intersection graph (where the labels of the vertices are interchanged). 
%% Uniqueness of the packing implies that there exists a M\"{o}bius transformation $\phi\colon S^2 \to S^2$ 
%% that keeps $P$ invariant as an unlabelled collection circles, but intrerchanges the circle
%% corresponding to vertex $v$ in $\hat{T}$ with the circle corresponding to $a(v)$. 
%% Define a function $g$ from vertex set of $\hat{T}$ to $S^2$ by sending each vertex to the center of the circle in $P$ that represents it. Notice that $g\circ a=\phi \circ g$ on the vertices and extend $g$ to a homeomorphism of $\hat{T}$ so that this identity holds everywhere. Since $a$ is fixed point free and $a \circ a=id$, the
%% same holds for $\phi$. Hence there exists $\tau$ such that $\tau^{-1} \phi
%% \tau$ is the antipodal map, and so $\tau^{-1} (P)$ is an antipodally invariant
%% circle packing whose intersection graph is the $1$-skeleton of $\hat{T}$.
%% Passing to the quotient $\pi\colon S^2 \to \RP^2$, we obtain the desired
%% packing on $\RP^2$.  



%\arnaud{I think this proof should be pushed to the appendix. It is folklore (it is the same proof as circle packing for surfaces) and uses technical tools pretty remote from the scope of this article)}




%It is easy to check Theorem~\ref{t:shortest_paths} for the minimal
%triangulations of $S^2$ and $\RP^2$. Indeed there is a single minimal
%triangulation od $S^2$ which is obtained from embedding the complete graph
%$K_4$ into $S^2$ and this triangulation easily admits a shortest-path drawing.
%\martin{TODO: Introduce a notion of the shortest path drawing somewhere.}
%There are two minimal triangulations of $\RP^2$; see TODO.

%\begin{center}
%  \includegraphics{projective_plane}
%\end{center}

%\martin{TODO: Say a nice argument why these triangulations can be done with
%shortest paths on the round metric. For the first one, it can be perhaps said
%via projection the icosahedron to the sphere and then by taking a quotient.}

\subparagraph*{Minimal triangulations.} Let $S$ be a surface and $T$ be a triangulation of it. The triangulation $T$ is
called \emph{reducible}, if it contains an edge $e$ such that the
contraction of $e$ yields again a triangulation, which we denote by
$T/e$. We refer to $e$ as a \emph{contractible} edge (we do not mean
contractibility in a~topological sense). On the other hand, a
triangulation is \emph{minimal} (or \emph{irreducible}), if no edge
can be contracted this way. For every surface there is a finite list
of minimal triangulations. In particular, for the torus $T^2$ this
list consists of $21$ triangulations found by
Lawrencenko~\cite{l-itt-87} and for the Klein bottle $K$ there are
$29$ minimal triangulations found by Sulanke~\cite{s-nitkb-06}.

The strategy of the proof of Theorem~\ref{t:shortest_paths} for $T^2$ and $K$ is to show that it
is sufficient to check Theorem~\ref{t:shortest_paths} for minimal
triangulations with appropriate fixed metric; see Lemma~\ref{l:contraction}.
Then, since every embedded graph can be extended to a triangulation (possibly
with adding new vertices), we finish
the proof by providing the list of shortest path embeddings of the minimal
triangulations.


\begin{lemma}
\label{l:contraction}
Let $S$ be a surface equipped with a flat metric. Let $T$ be a reducible
triangulation with contractible edge $e$. Let us assume that $T/e$ admits a
shortest path embedding with uniqueness into $S$. Then $T$ admits a shortest path
embedding with uniqueness into $S$ as well.
\end{lemma}

The restriction on flat metrics in the lemma above does not seem essential, %and it can perhaps be proved for various other metrics. 
but this is all we need and this way the proof is quite simple.

\bigskip

\begin{proof}

\renewcommand*{\windowpagestuff}{\includegraphics[scale=0.8]{vertex_splitting}}
\opencutleft
\begin{cutout}{4}{0pt}{6.5cm}{8}  
Let $v$ be the vertex of $T/e$ obtained by the contraction of $e$. The idea is
to consider the shortest path drawing of $T/e$. Then we perform the appropriate 
vertex splitting of $v$ (the inverse operation to the contraction) in a close
neighborhood of $v$ so that we get a shortest path embedding of $T$. In order to see that this is indeed possible, let us consider an edge $f =
uv$ of $T/e$. Since the shortest paths are unique, a~simple compactness argument shows that there is an
$\varepsilon$-neighborhood $N_f$ of $f$ in $S$ which is isometric to an
$\varepsilon$-neighborhood of a segment of the same length in $\R^2$ and such
that for every $v'$ in the $\varepsilon$-neighborhood of $v$, the straight line
segment connecting $v$ and $v'$ inside $N_f$ is the unique shortest path between
$v$ and $v'$ in $S$.
Therefore, considering such a neighborhood for every edge, 
it is sufficient to perform the vertex splitting of $v$ in sufficiently small 
neighborhood of $v$ so that we do not introduce new intersections as on the
picture.
\end{cutout}
\end{proof}
%\begin{center}
%  \includegraphics[scale=0.8]{vertex_splitting}
%\end{center}

%\martin{In the proof above, are you happy with referring to a simple
%compactness argument? I could go into details but I hope that it is not
%necessary.}
%
%\arnaud{That's convincing enough for me, thanks!}


%Remark: in all cases one can perturb the metric quite a bit and the result is still true. This includes the particular case of the rectangular $1$ by $1$ torus. \note{Well, isn't this used in the proof with this open ball?}

%TODO: Are there easy counter-examples when the metric is the one of a very thin torus for example?


%\begin{conjecture} There exists an absolute constant $c_g$ such that if $T$ is a triangulation with controlled volume growth, i.e. $|B(x,r)|\leq C r^2$ for all $r$ and all $x$, and $m$ a metric such that $sys(T) > C sys(m)$ then it is possible to draw $T$ with shortest paths. \end{conjecture}

%\note{I vote against stating this kind of conjecture. It is not clear why this hypothesis could be the correct one -- and I have no convition that it holds.}

%\alfredo{we still have the unique or not unique shortest path pending}
%\arnaud{should be good now}


\subparagraph*{The minimal triangulations of $T^2$ and $K$.} In Figure~\ref{f:torus} we provide a list of shortest path embeddings
with uniqueness of minimal triangulations of the torus with a flat
metric obtained by identifying the opposite edges of the unit
square. They are in the same order as in the book of Mohar and
Thomassen~\cite[Figure~5.3]{mt-gs-01}. The black (thin) edges are the
edges of the triangulation whereas the green (thick) edges are the
identified boundaries of the unit square which are not parts of the edges of the
triangulations. We just skip drawings of the triangulations 7 to 17,
because they are all analogous to the triangulation 6, they only have
different patterns of diagonals. It is clear that every edge is a
geodesic.  In order to check that each of them is drawn as a shortest
path, it is sufficient to verify that each edge projects vertically
and horizontally to a segment of length less than $\frac12$.




%\martin{Pictures are not positioned well at the moment. But I think that it
%makes sense to optimize the pictures only at the very end.}
%\arnaud{sure}

\bigskip

For the Klein bottle $K$, we also provide a metric such that all the minimal
triangulations admit shortest path embeddings with uniqueness.
% such that every minimal
%triangulation of $K$ admits a shortest path embedding in this metric.
%\martin{TODO: add unique, perhaps.}
We obtain this metric as the identification of the edges of the
rectangle $R = [0,a]\times[0,b]$, where $a = 1$ and $b = \sqrt{4/3} +
\varepsilon$ for sufficiently small $\varepsilon$. The edges of length
$1$ are identified in coherent directions. The edges of length $b$ are
identified in the opposite directions. The value $b = \sqrt{4/3} +
\varepsilon$ is set up in such a way that if we consider the points $p
= (0, \frac34b) = (1,\frac b4)$ and $q = (\frac13,\frac b4)$ of $K$,
then the shortest path between $p$ and $q$ is the horizontal path of
height $\frac 14b$. However, when we shift $p$ along the boundary of
$R$ a little bit closer to the center, say by $\frac 1{1000}$, then
the shortest path becomes the diagonal edge connecting the left copy
of $p$ and $q$, see Figure~\ref{f:shortest}.



%% Minimal triangulations of the
%% Klein bottle were obtained by Lawrencenko and
%% Negami~\cite{ln-itkb-97}, and Sulanke~\cite{s-nitkb-06}, and we show
%% how to embed them with shortest paths in Figure~\ref{f:all-cases}. In some cases
%% an additional shift is necessary by a small value $\frac1{1000}$ (but
%% this value is large compared to $\varepsilon$): this is indicated by
%% arrows next to the vertices. (The pair of arrows in Kh25 indicates a
%% shift by $\frac{2}{1000}$.)
%% The triangulations split into two types---so called Kh cases and 
%% Kc cases. For the Kh cases we omit few pictures analogous to Kh14.
%% For the Kc cases, the triangulations of the Klein bottle are obtained
%% by gluing together two triangulations of the M\"obius band pictured in the
%% bottom line; Kc1, obtained from two copies of Mb1,
%% is provided as an example. 
\begin{figure}
\begin{center}
  \includegraphics{torus_shorter}
  \caption{Minimal triangulations of the torus.}
  \label{f:torus}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
  \includegraphics{kb_all_triangulations}
\caption{Minimal triangulations of the Klein bottle.}
\label{f:all-cases}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics{choiceb}
\caption{Shortest paths in the Klein bottle.}
\label{f:shortest}
\end{center}
\end{figure}

%\begin{figure}
%\begin{center}
%  \includegraphics{crosscap_triangulations}
%\caption{Minimal triangulations of the Klein bottle; Kc-cases.}
%\label{f:kc-cases}
%\end{center}
%\end{figure}



There are 29 minimal triangulations of the Klein bottle. A list of 25
of them was first found by Lawrencenko and
Negami~\cite{ln-itkb-97}. Later on, Sulanke~\cite{s-nitkb-06} found a
gap in the claimed completeness of this list and provided a complete
list containing 4 additional triangulations. These triangulations
split into two classes. The triangulations of the first class are named
Kh1--Kh25 and there are four triangulations Kc1--Kc4 in the second
class. The triangulations from the second class differ by the property
that they contain a cycle of length $3$ which splits the Klein bottle
into two M\"{o}bius bands.


We start with the examination of the triangulations in the first
class. We present shortest path embedings with uniqueness for 15 of
them; see the top three lines of Figure~\ref{f:all-cases}. We omit the
triangulations Kh15-Kh24 that are very analogous to Kh14, only the
diagonal edges form a different pattern. 
%The black (thin) edges are the edges of the triangulation
%whereas the green (thick) edges are the identified boundaries of $R$ which are
%not parts of the edges of the triangulations. (TODO: say this perhaps for torus
%and do not repeat.) 
The vertices of the triangulations are positioned in
lattice points of the lattice generated by vectors $(\frac1{12}, 0)$ and
$(0,\frac b{12})$. In some cases an additional
shift is necessary by a small value $\frac1{1000}$ (but this value is
large compared to $\varepsilon$): this is indicated by arrows next to
the vertices. (The pair of arrows in Kh25 indicates a shift by
$\frac{2}{1000}$.)
Most of the drawings are very similar to the drawings by
Negami, Lawrencenko, and Sulanke. Only for the drawings of Kh3,
Kh12, Kh13, and Kh25 we did more significant movements. It is routine (but
tedious) to check that all the edges are indeed drawn as shortest paths. For
many edges this can be checked easily. For few not so obvious cases the
general recipe is to use the universal cover approach and
Lemma~\ref{l:VoronoiCell}. %from the next section.

Now let us focus on the triangulations in the second class. All of them are
obtained by gluing two triangulations of the M\"{o}bius bands along their
boundaries. In our case, we split $K$ into two bands by a cycle depicted on the
bottom left picture of Figure~\ref{f:all-cases}. It is perhaps the most natural way
how to split the Klein bottle into two M\"{o}bius bands; a particular
advantage for us is that there is an isometric homeomorphism which maps one
band to another and which preserves the common boundary pointwise. Therefore,
it is sufficient to present the shortest paths embeddings with uniqueness into the 
bands, as on the middle three pictures. Then we get drawings of Kc1-Kc4 using this
homeomorphism. For example, Kc1 is obtained by gluing two copies of Mb1
together. The vertices on the pictures are the lattice points of the same
lattice as above with exception of two points of Mb3. The points on the
`central' cycle of Mb3 have coordinates $(\frac16, \frac b2)$, $(\frac 49,
\frac b2)$, and $(\frac 89, \frac b2)$. Note that we have redrawn the original
drawings of Lawrencenko and Negami~\cite{ln-itkb-97} quite significantly, but it is
easy to check that we get the same triangulations, because these
`halves' of triangulations of $K$ are quite small.
\vojta{Since there are triangulations Kc1-Kc4, I would expect pictures Mb1-Mb4, no only Mb1-Mb3. Am I missing something?}
\martin{I think that there are combinations 1+1, 1+2, 2+2, and 1+3, if I
remember well. I am not completely sure which ones, but surely only 4 out of the 6 possibilities
work.}
\vojta{If not all combinations lead to a valid triangulation, then I suggest to mention it somewhere.}



\section{Square flat metric on the Klein bottle}\label{S:klein}

The task of this section is to prove the following theorem.

\tklein*

We consider the minimal triangulation Kc1 (see
Figure~\ref{f:all-cases}) and we denote by $G$ the underlying graph
for this triangulation. We will prove that $G$ does not admit a
shortest path embedding into $K$ with the square metric.  First, we
observe that the triangulation Kc1 is the only embedding of $G$ into
$K$. 


\begin{proposition}
\label{p:unique_Kc1}
$G$ has a unique embedding into the Klein bottle.
 \end{proposition}

 \begin{proof}[Proof of Proposition~\ref{p:unique_Kc1}]
$G$ has $9$ vertices and their degrees
are $(8,8,8,5,5,5,5,5,5)$. Since no other irreducible triangulation of
the Klein bottle has this degree sequence, any other hypothetical
embedding of $G$ into the Klein bottle is either non-cellular or has a
reducible edge. In the first case, it means that $G$ is cellularly
embeddable into the sphere or the projective plane, which is not the
case. Indeed, it is obtained as the gluing of two copies of $K_6$
along a triangle, and therefore contains $K_5 \oplus K_5$ (two copies
of $K_5$ identified along an edge minus that edge) as a minor, which
does not embed into the projective plane~\cite[Figure~6.4]{mt-gs-01}. In
the latter case, we observe that an edge contraction cannot decrease
the degree of all three degree $8$ vertices, and thus we reach a
contradiction since a triangulation on $8$ vertices cannot have a
degree $8$ vertex.
\end{proof}

%\martin{In case of necessity, the prove above could perhaps go to the appendix
%as well.}

%\martin{Unfortunately, there is some inconsistency in the notation for the
%Klein bottle ($K$ or $K$). I will try to solve it at some point.}
%\arnaud{I fixed everything to $K^2$}
For contradiction, let us assume that $G$ admits a shortest paths embedding into
$K$. We know that Kc1 is obtained by gluing two triangulations of a M\"{o}bius
band along a cycle of length $3$ (the triangle corresponding to this cycle is
not part of the triangulation). Let $abc$ be this cycle. With a slight abuse of
notation we identify this cycle with its image in the (hypothetical) shortest
path embedding into $K$. Our strategy is to show that already $abc$ cannot be embedded into
$K$ with shortest path edges, which will give the required contradiction.
By Proposition~\ref{p:unique_Kc1}, we know that $abc$ splits $K$ to two
M\"{o}bius bands.


%We will first show that there is a minimal triangulation of the Klein
%bottle endowed with a flat-square metric which does not admit a
%shortest path embedding. Then we will prove that there is no other
%embedding of the underying graph with shortest paths.

%By Lawrencenko and Negami~\cite{ln-itkb-97} and
%Sulanke~\cite{s-nitkb-06}, there are minimal triangulations $T$ of the
%Klein bottle $K^2$ containing a cycle $abc$ which splits $K^2$ into two
%M\"{o}bius bands. This is the case for the triangulations $Kc_1,
%\ldots , Kc_4$. Our task is to show that $abc$ cannot be embedded into
%$K^2$ with shortest path edges at all. We will then argue that the graph
%underlying $Kc_1$ (see Figure~\ref{f:kc-cases}) has a unique embedding 
%on the Klein bottle, which is $Kc_1$.

Let $X = \R^2$ be the universal
cover of $K$ (with standard Euclidean metric). 
Let $\pi\colon X \to K$ be the isometric projection corresponding to the cover. 
We will represent the Klein bottle with the flat-square metric as the unit square 
$[0,1]^2$ with suitable identification of the edges ($aba^{-1}b$, as in the previous
section). We will use the convention that
$\pi((0,1)^2) = (0,1)^2$; that is, the projection is the identity on the
interior of this square. See Figure~\ref{f:uc}.


Given a point $p \in K$ we set
$X_p := \pi^{-1}(p)$. Finally, let $\V_p$ be the Voronoi diagram in $X$
corresponding to the set $X_p$.   

\begin{lemma}
\label{l:VoronoiCell}
  Let $p$ and $q$ be two points in $K$ and $\gamma$ be an arc (edge) connecting
  them, considered as a subset of $K$. Then $\gamma$ is the unique shortest path 
  between $p$ and $q$ if and only if there are $p' \in X_p$, $q' \in X_q$ such
  that $\gamma = \pi(\overline{p'q'})$ where $\overline{p'q'}$ denotes the straight edge
  connecting $p'$ and $q'$ in $X$ and $q'$ belongs to the open Voronoi cell for $p'$ in
  $\V_p$.
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{l:VoronoiCell}]
  Any path $\kappa$ with endpoints $p$ and $q$ lifts to some path $\kappa'$ with
  endpoints $p' \in X_p$ and $q' \in X_q$ ($\kappa'$, $p'$, and $q'$ are not
  determined uniquely). This lift preserves the length of the path. Vice versa, any path 
  connecting a point in $X_p$ with a point in $X_q$ projects to a path
  connecting $p$ and $q$ (not necessarily simple), again preserving the length.

  Therefore, $\gamma$ is the shortest path in $K$ connecting $p$ and $q$ if and only if it
  lifts to a straight edge realizing the distance between $X_p$ and $X_q$ in $X$. 
  Such an edge connects $p' \in X_p$ and $q' \in X_q$.
  By symmetry, we can fix $q'$ arbitrarily and we look for the closest $p'$. Then,
  a point $p'$ is the unique point of $X_p$ closest to $q'$ if and only if $q'$ 
  belongs to the open Voronoi cell for $p'$ in $\V_p$. This is what we need.
\end{proof}




%Now let us assume for contradiction that the above-mentioned cycle $abc$ can
%be embedded into $K^2$ with shortest paths. 

Now let us lift the cycle $abc$ to a path $a'b'c'a''$
in $X$; see Figure~\ref{f:uc}. 
Given a curve in $X$, we call the length of its projection to the $x$-axis, the
``horizontal length'' of the curve; similarly we speak about the horizontal distance and the
vertical distance of two points in $X$.

\begin{figure}
\begin{center}
  \includegraphics{universal_cover}
  \caption{The Klein bottle with a letter `$\Gamma$', and its universal cover
  (left). A lift of the cycle $abc$ (right).}
  \label{f:uc}
\end{center}
\end{figure}

\begin{lemma}
\label{l:a'a''}
The horizontal distance between $a'$ and $a''$ is at least $2$.
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{l:a'a''}] 
If we consider the point $a'$ fixed, then the position of $a''$ in $X_a$ determines the
homotopy class of the cycle $abc$ in $\pi_1(K)$. Therefore, it also determines
the homology classes of this cycle in $H_1(K; \Z_2)$ and in $H_1(K; \Z)$. We
note that the cycle $abc$ must be homologically trivial in $H_1(K; \Z_2)$
because it bounds a M\"{o}bius band; however, it is homologically nontrivial in
$H_1(K; \Z)$ because it bounds a M\"{o}bius band (which is non-orientable) 
on both sides. In addition the cycle $abc$ is two sided, that is, its (regular)
neighborhood is an annulus and not a M\"{o}bius band.
  
The horizontal distance between $a'$ and $a''$ must be a non-negative integer.
We will rule out the cases when this distance is $0$ or $1$. 

If this distance is $1$, then the cycle $abc$ is not two-sided (this can be
read on the lift), a contradiction.

If the horizontal distance is $0$ and the vertical distance is odd, then $abc$
is homologically nontrivial in $H_1(K; \Z_2)$. (It is
sufficient to consider the segment connecting $a'$ and $a''$ and project it to a
cycle $z$ in $K$. Then $z$ is homotopy equivalent to $abc$.) 
A contradiction.

Similarly, if the horizontal distance is $0$ and the vertical distance is even,
then $abc$ is homologically trivial in $H_1(K; \Z)$. (Again we project the
segment connecting $a'$ and $a''$.) A contradiction.
\end{proof}


%\alfredo{I think we should be more specific about this claim here, maybe:}
%\begin{lemma} Consider the Klein bottle endowed on a square of side length $1$ on the scheme $aba^{-1}b^{-1}$. 
%Any simple closed curve that separates the Klein bottle into two M\"{o}bius bands projects to the $a$-direction into a curve of length at least $2$. \end{lemma}
%\vojta{I think that the scheme above is of the torus, not the Klein bottle. There is also probably something missing after the word ``endowed''.}
%\arnaud{Projects to the $a$ direction is ambiguous}
%\martin{I would prefer the previous version. $a$-direction changed to $x$-axis}
%% \begin{proof}[Sketch of a proof.]
%% If we consider the point $a'$ fixed, then the position of $a''$ in $X_a$ determines the
%% homotopy class of the cycle $abc$ in the fundamental group $\pi_1(K)$. 
%% %Therefore, it also determines
%% %the homology classes of this cycle in $H_1(K; \Z_2)$ and in $H_1(K; \Z)$. We
%% %note that the cycle $abc$ must be homologically trivial in $H_1(K; \Z_2)$
%% %because it bounds a M\"{o}bius band; however, it is homologically nontrivial in
%% %$H_1(K; \Z)$ because it bounds a M\"{o}bius band (which is non-orientable) 
%% %on both sides. In addition the cycle $abc$ is two sided, that is, its (regular)
%% %neighborhood is an annulus and not a M\"{o}bius band.
  
%% The horizontal distance between $a'$ and $a''$ must be a non-negative integer.
%% However, by checking the homology class of $abc$ in the $\Z$ and
%% $\Z_2$-homology, it is possible to rule out the cases when this distance is $0$. By the fact that $abc$ is a double-sided cycle, it is possible to rule out
%% the distance $1$. The full proof is given in Appendix~\ref{A:a'a''}.
%
%If this distance is $1$, then the cycle $abc$ is not two-sided (this can be
%read on the lift), a contradiction.
%
%If the horizontal distance is $0$ and the vertical distance is odd, then $abc$
%is homologically nontrivial in $H_1(K; \Z_2)$. (It is
%sufficient to consider the segment connecting $a'$ and $a''$ and project it to a
%cycle $z$ in $K^2$. Then $z$ is homotopy equivalent to $abc$.) 
%A contradiction.
%
%Similarly, if the horizontal distance is $0$ and the vertical distance is even,
%then $abc$ is homologically trivial in $H_1(K; \Z)$. (Again we project the
%segment connecting $a'$ and $a''$.) A contradiction.
%\end{proof}
%\alfredo{Nice proof!}

\begin{lemma}
\label{l:5/8}
Let $\gamma$ be a unique shortest path in $K$ connecting points $p$ and $q$. Let
$\gamma'$ be a lift of $\gamma$ with endpoints $p'$ and $q'$. Then the
horizontal distance in $X$ between $p'$ and $q'$ is less than $\frac58$.
\end{lemma}


\begin{proof}
\renewcommand*{\windowpagestuff}{\includegraphics{five_eights}}
\opencutleft
  \begin{cutout}{2}{0pt}{11cm}{6}
  Let $C$ be the open Voronoi cell for $p'$ in $\V_p$. By
  Lemma~\ref{l:VoronoiCell}, $q'$ belongs to $C$. Therefore, it is sufficient
  to check that every point $c'$ of $C$ has horizontal distance less than $\frac58$
  from $p'$. Without loss of generality, we may assume that the $x$-coordinate
  of $p'$ equals $0$ since shifting $p'$ in horizontal direction only shifts
  $X_p$ and $\V_p$ ( note that this is not true for the vertical direction). 
  For contradiction, there is a $c'$ in $C$ at distance at least $\frac
  58$ and without loss of generality the $x$-coordinate of $c'$ is positive.
  Let $p''$ be the point of $X_p$ with $x$-coordinate equal $1$ which is
  vertically closest to $c'$ (pick any suitable point in case of draw); see the picture on the left. The vertical distance between $c'$ and $p''$ is
  at most $\frac12$. A simple calculation, using the Pythagoras theorem, gives
  that $p''$ is at most as far from $c'$ as $p'$. A contradiction.
\end{cutout}
\end{proof}
% Now we can finally show that the cycle $abc$ cannot be embedded to $K$ with
% shortest paths. 
 Finally, we summarize how the previous lemmas yield a contradiction.
% 
% Indeed, for a contradiction, consider a lift $a'b'c'a''$. 
 By Lemma~\ref{l:a'a''}, the horizontal distance between $a'$ and $a''$ is at
 least $2$. On the other hand, Lemma~\ref{l:5/8} gives that the horizontal 
 length of each of the edges $a'b'$, $b'c'$, and $c'a''$ is at most $\frac58$, 
 altogether at most $\frac{15}8$. This gives the required contradiction, which
 finishes the proof of Theorem~\ref{t:klein}.


% To conclude, let us show that $Kc_1$ is the only embedding of its underlying graph on the Klein bottle.



%\bibliographystyle{alpha}
%\bibliography{/home/martin/clanky/bib/grph,/home/martin/clanky/bib/topocom,/home/martin/clanky/bib/combgeo,/home/martin/clanky/bib/compl}

\section{Asymptotically almost all hyperbolic metrics are not universal}\label{S:pants}
%% In this section we focus on $2$ dimensional simplicial complexes that
%% triangulate a given surface. In graph theoretical terms, this means
%% that we are fixing the embedding of the $1$-skeleton up to
%% homeomorphism or equivalently, that we are fixing the rotation
%% system. If $T_g$ is a simplicial complex, a shortest path embedding of
%% $T_g$ with respect to a metric $m$ is a homeomorphism from $T_g$ to
%% $S_g$ such that every edge in the $1$-skeleton is mapped to a shortest
%% path with respect to $m$.

Before stating the main theorem of this section, we will give some very quick
background on the geometry of surfaces, we refer to Farb and
Margalit~\cite{fm-pmcg-11} for a proper introduction. The Teichm\"uller
space $\mathcal{T}_g$ of a surface $S$ of genus $g$ denotes the set of
hyperbolic metrics on $S$, such that two metrics are equivalent if
they are related by an isometry isotopic to the identity. In some
contexts, like ours, one might also want to identify metrics related
by an isometry (not necessarily isotopic to the identity). The
corresponding space is called the \textit{moduli space} $\mathcal{M}_g$ of the
surface, and is obtained by quotienting $\mathcal{T}_g$ by the
\textit{mapping class group} of $S$, i.e., its group of
homeomorphisms. This moduli space can be endowed with multiple
structures, here we will be interested in a particular one, called the
Weil-Petersson metric. This metric provides $\mathcal{M}_g$ with a
Riemannian structure of finite volume, and therefore by renormalizing,
we obtain a probability space, allowing to choose a random metric. We
can now state the main theorem of this section.

\Tnegative*

The proof is a consequence of two important results on random
hyperbolic metrics. The first is a small variant of a theorem of Guth,
Parlier, and Young~\cite[Theorem~1]{gpy-pdrs-11} that relies on the work of Wolpert~\cite{w-gwpcts-03}. Before stating it, we
need some definitions.

Given a hyperbolic metric $m$ on a surface
$S$, we say that $m$ has total pants length at least $\ell$ if in any
pants decomposition $\Gamma$ of $S$, the lengths of the closed curves of
$\Gamma$ sum up to at least $\ell$. We say that $m$ has total pants
length of type $\xi$ at least $\ell$ if in any pants decomposition $\Gamma$ of
$S$ of type $\xi$, the lengths of the closed curves of $\Gamma$ sum up
to at least $\ell$.



\begin{theorem}\label{T:gpy}
For any $\varepsilon >0$ and any family of types of pants decomposition $\xi_g$, a random metric on $\mathcal{M}_g$ has total pants length of fixed type $\xi_g$ at least $g^{4/3 - \varepsilon}$ with probability tending to $1$ as $g \rightarrow \infty$.
\end{theorem} 



\begin{proof}[Proof of Theorem~\ref{T:gpy}]
This bound is obtained with a similar technique as the proof of Theorem~1 of Guth, Parlier, and Young~\cite{gpy-pdrs-11}. We refer to their article for more details, and as in their proof, we will discard non super-exponential terms, e.g., $n! \approx n^n$.
For every $a,b,c \in \mathbb R^+$ there exists a unique hyperbolic metric on a pair of pants with boundary lengths $a,b$ and $c$. For a pants 
  decomposition of fixed type $\xi_g$, the Weil-Petersson volume form on moduli space is the push forward of the form
   $d\ell_1 \wedge \ldots \wedge d\ell_{3g-3} \wedge d\tau_1
  \wedge \ldots \wedge d\tau_{3g-3}$ on Teichm\"uller space which is identified with $\mathbb R^{6g-6}$ and the $\ell_i$ denote the
  lengths of the (geodesic) boundaries of the pants decomposition, while
  the $\tau_i$ quantify how much the metric \textit{twists} around
  each geodesic. Since every full twist gives a homeomorphic metric,
  %$\tau_i$ can be assumed to lie between $0$ and
 % $\ell_i$. Hence, 
 the subset of Teichm\"uller space $\{(\ell_i, \tau_i) \mid \sum_i \ell_i \leq L, 0 \leq \tau_i
  \leq \ell_i\}$ projects surjectively onto the region of moduli space corresponding to 
  surfaces with total pants length of type $\xi_g$ at most $L$. The volume of this set is bounded by
$\lesssim (\frac{L}{g})^{6g}$, which is to be compared with the total volume of moduli space $\approx g^{2g}$. For $L$ smaller than $g^{4/3-\varepsilon}$, the ratio tends to zero, which proves the theorem.  %Now, for a fixed pants type
  %$\xi_g$, we simply do not include the $g^g$ factor coming from the various types of pants decompositions. Then, the volume of moduli space one can reach is $\lesssim (\frac{L}{g})^{6g}$. 
\end{proof}










%\martin{Just a question. The theorem gives exactly
%  $g^{7/6-\varepsilon}$? (It is not $O(g^{7/6-\varepsilon})$?}
%
%\arnaud{The epsilon takes care of the constant, but there was indeed an ``at least'' missing.}


The following is an immediate corollary of this theorem.

\begin{corollary}\label{map-pants}
Let $T_g$ be a family of triangulations of $S_g$, such that every member of $T_g$ contains a pants decomposition of fixed type $\xi_g$. For any $\varepsilon >0$, with probability tending to $1$ as $g \rightarrow \infty$, a shortest embedding of $T_g$ into a random hyperbolic surface of genus $g$ has length at least $\Omega(g^{4/3-\varepsilon})$.
\end{corollary}

%\arnaud{TODO:I believe that when the combinatorial type of the pants decomposition is fixed, which is the case here, their argument be improved to $g^{4/3}$}

The next theorem was proved by Mirzakhani~\cite[Theorem~4.10]{m-gwpvrh-13}.
\begin{theorem}\label{Mirzakhani}
With probability tending to $1$, the diameter of a random hyperbolic surface of genus g is $O(\log g)$.
\end{theorem}

Theorem~\ref{negative} is proved by providing an explicit family of
graphs $G_g$ which will embed badly. It is
defined in the following way for $g \geq 2$. Let $\xi_g$ be a type of
pants decompositions for every value of $g$.
\begin{itemize}
\item We start with a pants decomposition of type $\xi_g$ of a surface $S_g$
\item We place four vertices on every boundary curve.
\item We triangulate each pair of pants with a bounded size triangulation 
  so that each cycle of length $3$ bounds a triangle in the triangulation, and any
  path connecting two boundary components of the pair of pants has length at
  least $4$ (in particular $G_g$ is a simple graph and each cycle of length $3$
  in the graph $G_g$ bounds a triangle in the triangulation).  
\end{itemize}

The following proposition controls the issues related to the flexibility of embeddings of graphs into surfaces.

\begin{proposition}\label{P:embeddings}
There is a unique embedding of $G_g$ into $S_g$, up to a homeomorphism; in
particular every embedding contains a pants decomposition of type $\xi_g$.
\end{proposition}

\begin{proof}[Proof of Proposition~\ref{P:embeddings}]
Let $v$ be the number of vertices, $e$ be the number of edges and $t$ be the
number of triangles of the triangulation in the definition of $G_g$ (triangles in the graph-theoretical sense). By Euler's formula and by the construction we get $v - e + t = \chi$ where
$\chi$ is the Euler characteristic of $S_g$. Let us consider an embedding
$\Psi$ 
of $G_g$ into $S_g$. Let $f$ be the number of
faces of this embedding and $F$ be the set of faces. Euler's formula for this
embedding gives $v - e + f \geq \chi$ (we get an inequality because some of the
faces need not be embedded cellularly). In particular, we get $f \geq t$. On the
other hand, we get $2e = 3t$ and $2e = \sum_{\sigma \in F} \deg \sigma \geq 3f$
since each edge is in exactly two faces. This gives $3t \geq 3f$. Therefore,
both of the aforementioned inequalities have to be equalities. In particular,
each $\sigma \in F$ is a triangle bounded by a cycle of length $3$ in $G_g$. 
Since the number of cycles of length $3$ in $G_g$ equals $t = f$, we deduce
that $\Psi$ coincides with the embedding from the definition of $G_g$ up to a
homeomorphism.
\end{proof}

\textbf{Remark:} We preferred to use a hands-on construction of the graphs $G_g$, but another approach could be to rely on the theory of LEW-embeddings and use one of its results on uniqueness of embeddings, see for example Mohar and Thomassen~\cite[Corollary~5.2.3]{mt-gs-01}.


%\martin{Below is the original proof/construction by Arnaud, for comparison}

%\arnaud{Thanks for the improved proof.}


%% The family of graphs $G_g$ is defined in the following way for $g \geq 2$:

%% \begin{itemize}
%% \item We start with any pants decomposition of a surface $S_g$
%% \item We place four vertices on every boundary curve.
%% \item We add a vertex in each pair of pants and triangulate it.
%% \end{itemize}

%% The following proposition controls the issues related to the flexibility of embeddings of graphs on surfaces.

%% \begin{proposition}\label{P:embeddings}
%% Any embedding of $G_g$ on $S_g$ contains a pants decomposition as a submap.
%% \end{proposition}


%% \begin{proof}
%%   By construction, $G_g$ contains $3g-3$ disjoint cycles, which we denote by $C = C_1, \ldots , C_{3g-3}$. Cutting along these, we obtain subgraphs $G_g^1, \ldots , G_g^k$ which are stars. Let $f$ be an embedding of $G_g$ on $S_g$, the cycles $C_1, \ldots , C_{3g-3}$ are mapped to disjoint simple cycles $f(C_i)$ of $S_g$. Now, either the cycles $f(C_i)$ form a pants decomposition, in which case we are done, or at least one of them is contractible, or two of them are homotopic. We reach contradictions in the two latter cases.

%%   If one is contractible, we consider the innermost contractible cycle. No subgraph $G_g^i$ can be mapped inside it by $f$ since every such graph needs to connect to at least three cycles of $C$ by construction. But if no subgraph is mapped on it, the embedding $f(G_g)$ has a face of degree $4$, which is not possible because of the Euler characteristic.

%%   If two of the cycles are homotopic, we consider a pair of those which bound a cylinder with no other $f(C_i)$ inside. Once again, no subgraph can me mapped inside it by $f$, since it would only connect to two cycles. But if no subgraph is mapped in this cylinder, this cylinder is a face of the embedding. Replacing it by two disks of degree $4$, we obtain an embedding of $G_g$ into $S_{g-1}$ with two faces of degree $4$, this is once again impossible because of the Euler characteristic.


%% \arnaud{Does this require more explanation? The point is that in case of non-cellular embeddings, the Euler equality becomes $v-e+f \geq \chi$. We have $v-e+f = \chi$ in the initial embedding, and a face of degree 4 would reduce the LHS.}
  
%% \end{proof}

%% \martin{End of the original proof/construction by Arnaud.}





With these three results at hand we are ready to provide a proof of the theorem.

\begin{proof}[Proof of Theorem~\ref{negative}]
%We need $T_g$ to be a triangulation with $O(g)$ vertices that contains a pants decomposition as a submap. There are many such examples, and we provide an elementary approach to constructing many of them. Given a number $k$  choose simplicial complexes $P_1, P_2 \ldots P_{2g-2}$ each of them triangulating a pair of pants with $O(1)$ vertices in total and $k$ vertices on each connected component of the boundary. Since we choose $k$ vertices on each boundary component we can always paste together two $P_i$ to $P_j$ through any give boundary. In fact there is a $\mathbb{Z}_k$ ambiguity of how to do so at each edge of $H$. Given any $3$-regular multigraph $H$ (possibly with loops) together with a number from $1$ to $k$ on each edge, assign one pair of pants to each of the vertices and paste them according to the combinatorics of the $3$-regular graph and the labels of the edges. Each pair of pants has a constant number of vertices, so in total each triangulation $T_g$ constructed in this way has  $O(g)$ vertices. By construction it contains a a pair of pants as a submap. 

We use the family of graphs $G_g$ previously defined. Since there are
$O(g)$ curves in a pants decomposition, it contains $O(g)$ edges, and
every embedding of $G_g$ into $S_g$ contains a pants decomposition of type $\xi_g$ by Proposition~\ref{P:embeddings}.

  
Now, by Corollary~\ref{map-pants}, for every $\varepsilon>0$, and for
$g$ large enough, the probability that the shortest possible embedding
of $G_g$ into a random metric has length at least
$O(g^{4/3-\varepsilon})$ is at least $1 - \varepsilon/2$. In
particular, since there are $O(g)$ edges in $G_g$, some edge $e_g$ in
this embedding must have length at least
$\Omega(g^{1/3-\varepsilon})$. By Theorem~\ref{Mirzakhani}, we can
choose $g$ large enough so that with probability at least
$1-\frac{\varepsilon}{2}$, the random hyperbolic metric has diameter
$O(\log g)$. Hence, by the union bound, with probability
$1-\varepsilon$ both properties hold. Therefore, for every
$\varepsilon>0$, there exists some value $g_0$ such that for any $g
\geq g_0$, in any embedding of $G_g$, there exists an edge $e_g=(x,y)$
such that $\ell_m(e_g)=\Omega(g^{1/3-\varepsilon})$, but $d_m(x,y)\leq
diam(m)\leq O(\log g)$. This implies that $e$ is not drawn by a
shortest path. Similarly, subdividing each edge $O(g^{1/3-\varepsilon})$ times will run into the same issue. This concludes the proof.\end{proof}

\section{Higher genus: positive results}\label{S:concat}

\Tconcat*

%\arnaud{I think we should ditch pants decompositions and work directly on the octagons/hexagons. Here is the new approach.}


Our approach to prove Theorem~\ref{T:concat} is to cut the surface
$S_g$ with a \textit{hexagonal decomposition} $\Delta$, so that every edge
of $G$ is cut $O(g)$ times by this decomposition $\Delta$. The construction
to do this is a slight modification of the \textit{octagonal
decompositions} provided by \'E. Colin de Verdi\`ere and Erickson~\cite[Theorem~3.1]{ce-tnpcs-10}. Each of the hexagons is then
endowed with a specific hyperbolic metric $m_H$, and pasting these
together yields the hyperbolic metric $m$ on $S_g$. The hyperbolic
metric $m_H$ is chosen so that the hexagons are \textit{convex}, i.e.,
the shortest paths between points of a hexagon stay within this
hexagon. Therefore, there only remains to embed the graph $G$ cut
along $\Delta$, separately in every hexagon with shortest paths. To do
this, we use a variant of a theorem of Y. Colin de
Verdi\`ere~\cite{c-crgts-91} which generalizes Tutte's barycentric
method to metrics of nonpositive curvature.

\subparagraph*{Hexagonal decompositions.} A \textit{hexagonal decomposition}, respectively an \textit{octagonal
  decomposition} of $S_g$ is an arrangement of closed curves on $S_g$
that is homeomorphic to the one pictured in
Figure~\ref{F:octagons}.b., respectively Figure~\ref{F:octagons}.a. In
particular, every vertex has degree four and every face has six sides,
respectively eight sides.



\begin{figure}
  \centering
  \def\svgwidth{\textwidth}
  \input{octagons.pdf_tex}
  %  \includegraphics[width=.9\textwidth]{octagons.pdf_tex}
  \caption{a. An octagonal decomposition b. A hexagonal decomposition c. How to add one closed curve to upgrade an octagonal decomposition to a hexagonal decomposition}
\label{F:octagons}
\end{figure}

%\arnaud{Pictures are ugly but will be easy to improve}
Octagonal decompositions were introduced by \'E. Colin de Verdi\`ere and Erickson~\cite{ce-tnpcs-10} where they showed how to compute one that does not cross the edges of an embedded graph too many times. We restate their theorem in our language.

\begin{theorem}[{\cite[Theorem~3.1]{ce-tnpcs-10}}]\label{T:octagons}
  Let $G$ be a graph embedded in a surface $S_g$ for $g \geq 2$. There exists an
  octagonal decomposition $\Gamma$ of $S_g$ such that each edge of
  $G$ crosses each closed curve of $\Gamma$ a constant number of times.
 \end{theorem}

We observe that this octagonal decomposition can be upgraded to a hexagonal decomposition that still does not cross $G$ too much:

\begin{corollary}\label{C:hexagons}
  Let $G$ be a graph embedded in a surface $S_g$. There exists a
  hexagonal decomposition $\Delta$ of $S_g$ such that each edge of $G$
  crosses each closed curve of $\Delta$ a constant number of times,
  except for maybe one closed curve which is allowed to cross each
  edge of $G$ at most $O(g)$ times. In particular, the number of crossing
  between every edge of $G$ and $\Delta$ is $O(g)$.
\end{corollary}

%\martin{`Curve' is a closed curve? First I thought that a curve may be just a
%segment in the decomposition. Then there would be a constant number of
%crossings for every curve, right? Maybe, it could be good to clarify this.}
%
%\arnaud{corrected}

\begin{proof}
The decomposition $\Delta$ is simply obtained by taking the decomposition $\Gamma$ and adding a single curve that follows closely a concatenation of $O(g)$ subpaths of curves of $\Gamma$, see Figure~\ref{F:octagons}c. The resulting arrangement of curves has the topology of a hexagonal decomposition, and the bounds on the number of crossings results directly from the construction.
\end{proof}

%% \arnaud{Using the arguments of their paper, we can probably get constant multiplicity for the last curve as well. I do not focus on this for now since it is unimportant}

%% \martin{Do you want to still keep this comment?}

%% We observe that the asymmetry in Corollary~\ref{C:hexagons} is only
%% apparent: instead of starting with an embedding of $G$ and finding an
%% embedding of $\Delta$ that does not cross $G$ too much, we can peruse
%% it as a proof that there is an embedding of $G$ that does not cross a
%% given hexagonal decomposition $\Delta$ too much. This is what we will
%% do: after using $\Delta$ to endow $S_g$ with a hyperbolic metric, we
%% will use Corollary~\ref{C:hexagons} to subdivide $G$ and embed it separately in each hexagon.


\subparagraph*{The hyperbolic metric.} We first endow each hexagon of the hexagonal decomposition with the
hyperbolic metric $m_H$ of an equilateral right-angled hyperbolic
hexagon. Since the hexagons have right angles and the vertices of a
hexagonal decomposition have degree $4$, this metric can be safely
pasted between hexagons to endow $S_g$ with a hyperbolic metric
$m$. The main property of this metric that we will use is the
following one:

%\arnaud{Actually I think it holds for any metric where the even edges have the same lengths. This still defines a unique metric}

\begin{proposition}\label{P:convexity}
Every hexagon $H$, viewed as a subset of $S_g$ endowed with $m$, is
convex, i.e., every path between $x,y \in H$ that is a shortest path
in $H$ is also a shortest path in $S_g$.
\end{proposition}


\begin{proof}
The proof relies on an exchange argument based on the symmetries of
the hexagonal decomposition.

The intersection graph $I$ of the hexagonal decomposition is defined by
taking one vertex for each hexagon and edges between adjacent hexagons
(we allow multiple edges). We are interested in two graph automorphisms which are also involutions. These are pictured in Figure~\ref{F:intersections}:
\begin{itemize}
\item The symmetry $\sigma_1$ about the horizontal axis, corresponding to the so-called hyperelliptic involution of the surface $S$.
\item The automorphism $\sigma_2$ swapping every hexagon with its neighbor in the octagonal decomposition.
\end{itemize}

%\martin{I had some troubles with visualization of $\sigma_2$ (checking how it
%goes). Could it help to draw the added curve in Figure~\ref{F:octagons}~b
%closer to the outer boundary of the picture. Anyway, the overall argument is
%very nice.}
%
%\arnaud{done}

\begin{figure}
  \centering
  \def\svgwidth{11cm}
  \input{Intersection.pdf_tex}
  %  \includegraphics[width=.9\textwidth]{Intersection}
  \caption{The intersection graph $I$ and the two involutions: $\sigma_1$ is the symmetry about the dashed horizontal line, and $\sigma_2$ swaps every disk and its adjacent star.}
  \label{F:intersections}
\end{figure}

Since all the hexagons are isometric, these involutions correspond naturally to isometric involutions of $S$.

Now, let $\gamma$ be a shortest path between two vertices $x$ and $y$
in a hexagon $H_1$, let us assume without loss of generality that $H_1$
is in the upper part of $I$. This path $\gamma$ naturally induces a
walk in $I$ obtained by taking each hexagon of which interior is met
by $\gamma$. This walk does not backtrack at some hexagon $H$:
otherwise one could shortcut $\gamma$ by staying on the boundary of
$H$.

From $\gamma$, one can build a path $\gamma'$ between $x$ and $y$
which stays in the upper half of the graph: for every maximal subpath
of the graph in the lower half, one applies the isometry $\sigma_1$,
effectively mirroring these paths in the upper half. Similarly, by
applying $\sigma_2$, one obtains a path $\gamma''$, which only uses
half of the hexagons. The walk in $I$ corresponding to $\gamma''$ lies
now in a path. Since it does not backtrack, it is necessarily trivial
and never leaves hexagon $H_1$. We have thus found a shortest path in
$H_1$ connecting $x$ and $y$.
\end{proof}

  
%% We use an exchange argument. Suppose that there is a path $\gamma$
%% that is a shortest path between $x,y \in H$ that does not stay in $H$,
%% and denote by $\gamma_i$ its maximal subpaths which lie in a single
%% hexagon. We claim that each $\gamma_i$ which is not in $H$ can be
%% ``exchanged'' with a curve $\hat{\gamma_i}$ which is isometric to
%% $\gamma_i$ and is embedded in $H$: since all the hexagons are
%% isometric, we can just pick iteratively one isometry that sends the
%% curve $\gamma_i$ to an isometric copy in $H$. We only need to ensure
%% that the resulting curve is connected, this is achieved by choosing an
%% isometry that matches the endpoints of $\hat{\gamma_{i}}$ with the end
%% of $\hat{\gamma_{i-1}}$ and the start of $\hat{\gamma_{i+1}}$. The
%%   resulting curve $\hat{\gamma}$ has the same length as $\gamma$ and
%%   connects $x$ and $y$. It is thus a shortest path in $S_g$.

\subparagraph*{Finishing the proof.} We prove in this paragraph how to reembed a graph embedded in a hexagon so that its edges are shortest paths. This allows us to finish the proof.


\begin{restatable}{theorem}{TYves}\label{T:Yvesvariant}
Let $G$ be a graph embedded as a triangulation in a hyperbolic hexagon
$H$ endowed with the metric $m_H$. If there are no dividing edges in
$G$, i.e., edges between two non-adjacent vertices on the boundary of
$H$, then $G$ can be embedded with geodesics, with the vertices on the
boundary of $H$ in the same positions as in the initial embedding.
\end{restatable}

%% \arnaud{this a bit of an awkward def of dividing edges}


Let us postpone the proof of this theorem for now, and show how to conclude the proof of Theorem~\ref{T:concat}. We first show how to upgrade a graph embedded in a disk to a triangulation.

\begin{lemma}\label{L:triangulate}
For any graph $G$ embedded in a disk without
dividing edges, there exists a triangulation $G'$ of the disk containing
$G$ as a subgraph and that does not contain any dividing edges.
\end{lemma}

\begin{proof}
For every face $F$ of $G$, we start by adding a vertex in $F$ and
edges connecting it to the vertices adjacent to the face. This does
not add loops or dividing edges, but may add multiple edges if one
vertex occurs multiple times on the boundary of a face. These are
taken care of by subdividing them once again and triangulating.
\end{proof}


All the pieces are now in place for the proof of Theorem~\ref{T:concat}.

\begin{proof}[Proof of Theorem~\ref{T:concat}]
By Corollary~\ref{C:hexagons}, one can embed $G$ into $S_g$ such that
every edge of $G$ is cut $O(g)$ times by the hexagonal decomposition
$\Delta$. This defines a graph $G'= \bigcup_i G'_i$ such that each of
the graphs $G'_i$ is embedded in a single hexagon and $G'$ is obtained
from $G$ by subdividing every edge $O(g)$ times. If there are dividing
edges in $G'_i$, they can be removed by subdividing the edge once. By Lemma~\ref{L:triangulate}, one can upgrade all
the $G'_i$ to triangulations. We can then apply Theorem~\ref{T:Yvesvariant}
in each of the hexagons separately, yielding embeddings with shortest
paths. Since the vertices on the boundary did not move during the
reembedding, this defines an embedding of $G$ into $S_g$. Since $H$ is
simply connected and $m_H$ is hyperbolic, there is a unique geodesic
connecting any two points, and this geodesic is a shortest path.
Therefore the edges of $G'$ are shortest paths in $H$. By
Proposition~\ref{P:convexity}, each edge of $G'$ is also a shortest
path in $S_g$. Therefore each edge of $G$ is embedded as a
concatenation of $O(g)$ shortest paths.
\end{proof}

We note that by subdividing each edge once more, the shortest paths we
obtain are unique. \bigskip 

The proof of Theorem~\ref{T:Yvesvariant} is obtained in a spirit
similar to the proof of the one of the celebrated \textit{spring
  theorem} of Tutte~\cite{t-hdg-63}. However, there are two main
differences which prevent us from directly appealing to the literature: on the
one hand the metric is not Euclidean but hyperbolic, and on the other
hand the boundary of the input polygon is not \textit{strictly
  convex}, since there may be multiple vertices of $G$ on a geodesic
boundary of $H$. The hypothesis on dividing edges is tailored to
circumvent the second issue, and in a Euclidean setting it was proved
by Floater~\cite{f-otoplm-03} that the correspond embedding theorem
holds. Regarding the first issue, Y. Colin de Verdi\`ere stated a
Tutte embedding theorem~\cite[Theorem~3]{c-crgts-91} for the
hyperbolic setting with strictly convex boundary, yet he actually did not
provide a proof for it.
%and it does not apply a priori to the non-strictly convex
%setting.
\ifappendix 
In Appendix~\ref{A:Yves}
\else
In the next paragraph
\fi
we show how to prove Theorem~\ref{T:Yvesvariant}
in the generality that we need following the ideas laid out by Y. Colin de Verdi\`ere in the rest of his article~\cite{c-crgts-91}. This concludes the proof of Theorem~\ref{T:concat}.

\bigskip
%
%Therefore, for the sake of completion we show how to prove
%Theorem~\ref{T:Yvesvariant} following the ideas laid out (in French)
%in the rest of his article~\cite{c-crgts-91}. Since there are few new
%ideas involved, this is deferred to Appendix~\ref{A:Yves}.

Finally, we remark that this proof technique provides an alternative proof of Negami's Theorem~\cite{n-cngepc-01} for orientable surfaces. If $G_1$ and $G_2$ are two graphs embedded on the orientable surface of genus $g$, a crude application of Theorem~\ref{T:concat} shows that one can reembed both graphs with a homeomorphism such that each edge is realized as a concatenation of $O(g)$ shortest paths for our hyperbolic metric. Since hyperbolic shortest paths in general position cross at most once, this gives embeddings of $G_1$ and $G_2$ such that there are $O(g^2)$ crossings between each edge of $G_1$ and each edge of $G_2$. Negami proved that $O(g)$ crossings are actually enough, and a deeper look at our construction also achieves this better bound: it is easy to see that in our reembeddings, each edge is actually cut into $O(1)$ subedges realized as shortest paths in each hexagon. Since there are $O(g)$ hexagons, there are in total $O(g)$ crossings between each edge of $G_1$ and $G_2$, which yields the following:

\begin{corollary}
\label{c:negami}  
There exists an absolute constant $c>0$ such that if $S_g$ is
an orientable surface of genus $g$, for any two embedded graphs $G_1, G_2 \to
S_g$ there exists a homeomorphism $h:S_g\rightarrow S_g$ such that
$cr(h(G_1),G_2) \leq c g  |E(G_1)|\cdot |E(G_2)|$\end{corollary}









%% The basic idea to prove this theorem is to first cut the surface along
%% a pants decomposition of a specific combinatorial type. The hyperbolic
%% metric on $S_g$ is taken to be identical on each pair of pants obtained
%% after cutting along this decomposition. This then reduces the problem
%% to the case of a single pair of pants with a fixed hyperbolic metric,
%% and we show how to embed any graph on a pair of pants as a
%% concatenation of a small number of shortest paths.



%% \paragraph*{Cutting the surface with a specific pants decomposition}
%% Given a pants decomposition, the intersection graph of the pairs of
%% pants is a $3$-regular multigraph, which characterizes the
%% homeomorphism class of the pants decomposition. We first rely on the
%% following result of Colin de Verdière and Erickson~\cite{ce-tnpcs-10}
%% which shows that we can cut $S_g$ along a pants decomposition of a
%% fixed combinatorial type, so that every curve of the pants
%% decomposition crosses every edge of $G$ a constant number of times.



%% \begin{theorem}[{\cite[Theorem~3.1]{ce-tnpcs-10}}]\label{T:pants-from-octagons}
%%   Let $G$ be embedded on a surface $S$. There exist disjoint simple
%%   closed curves $\Gamma=\{\gamma_1, \gamma_2, \ldots \gamma_{3g-3}\}$
%%   cutting $S$ into pairs of pants corresponding to the multigraph H
%%   pictured in Figure~\ref{F:pants}, such that every curve $\gamma_i$
%%   crosses every edge of $G$ a constant number of times.
%%  \end{theorem}


%%  \textbf{Remark:} The Theorem~3.1 of Colin de Verdière and Erickson provides a proof that there exists an octagonal decomposition such that every curve has small multiplicity. One can deduce Theorem~\ref{T:pants-from-octagons} from this by just observing that the pants decomposition pictured in Figure~\ref{F:pants} is included in their octagonal decomposition. Note that it is \textbf{not} the same pants decomposition as the one they compute as an intermediate step (Phase 2) of their construction.


%%  \begin{figure}
%%    \centering
%%    \def\svgwidth{10cm}
%%    \includesvg{pantstype}
%%    \caption{The multigraph describing the combinatorial type of the pants decomposition, and an example for $g=4$.}
%%    \label{F:pants}
%% \end{figure}


 
%% Our proof of Theorem~\ref{T:concat} then proceeds by cutting $S$ along
%% $\Gamma$, and embedding the portions of the graph $G$ obtained after
%% this cutting separately on every pair of pants. We show how to do this in the next paragraph.

%% %Therefore, if we can embed
%% %any graph on a pair of pants with a concatenation of a constant number
%% %of shortest paths, this will suffice to prove Theorem~\ref{T:concat}. 


%% %For the combinatorial result we work in the dual setting of cross metrics. Given a graph $G$ embedded in $S_g$, the polyhedral metric corresponding to $G$ is just the graph metric on $G$, for arguments on which there are many curves at play, it is better to use a different metric, the so called cross metric. Namely one considers the dual map of $G$, denoted by $G^*$, and for any curve in $S_g$ one defines its length by the intersection number with $G^*$. This language is particularly appropriate for pants decompositions.

%% %% \begin{proposition} Given a $3$-regular multigraph $H$ and a cross metric $(S_g, G^*)$, so that $G$ has $n$ vertices. There exists disjoint simple closed curves $\gamma_1, \gamma_2, \ldots \gamma_{3g-3}$ with $$length_{G^*}(\gamma_i)\leq O(n)$$ providing a pants decomposition of $S_g$ with intersection multigraph $H$.
%% %% \end{proposition}

%% %%  We will derive this result from a similar one that is less specific.
 
%% %%  \begin{theorem}\label{pants} For any cross metric $(S_g, G^*)$, so that $G$ has $n$ vertices. There exists disjoint simple closed curves $\{\gamma_1, \gamma_2, \ldots \gamma_{3g-3}\}=\Gamma$ so that  $\forall  e \in E(G^*)$, $\forall\gamma \in \Gamma$ the intersection number $i(e,\gamma)<C$
%% %% \end{theorem}

%% %% Together with the following result of Matou\v{s}ek et al. based on a similar result of Erten and Kobourov. We say that $G_1$ and $G_2$ can be drawn simultaneously, if the share the vertex set and each of drawn in a planar fashion.
%% %% (this needs correction):
%% %% \begin{theorem}[Matou\v{s}ek et al.] .\end{theorem}

%% %% \begin{proof} Apply theorem \ref{pants} to the  graph $G^*$. Let $H_G$ be the intersection multigraph of the corresponding pants decomposition, choose a point in each of the pair of pants and represent $H_G$ by a (piecewise linear) embedding in which each vertex is mapped to the corresponding pair of pants and each edge $e_i$ of $H_G$ intersects the corresponding closed curve $\gamma_i$ in $\Gamma$ transversally exactly once. Consider a spanning tree $t$ of $H_G$ and contract its image in $S_g$ to a point, now each edge of $H_G/t$ corresponds to a handle of $S_g$ which in turn can be identified with the curve $\gamma_i$ that the edge intersects. Cut out the corresponding of $g$ curves (dual to the edges of $H_G/t$), to obtain a surface of genus $0$ (a sphere) with $2g$ boundary components that come together with a matching.  We know that each edge of $G^*$ intersects each boundary component less than $C$ times. 
%% %% \end{proof}

%% \paragraph*{Shortest path embedding of a graph on a pair of pants}

%% In this paragraph, we show how to embed a graph on a pair of pants so that every edge is a concatenation of a constant number of shortest paths. In order to paste together the embeddings in adjacent pairs of pants, we also require from this embedding to place the vertices on the boundaries as we want.


%% \begin{proposition}\label{P:Embed}
%%   Let $G$ be a graph embedded on a pair of pants $P$, endowed with the
%%   metric $m_P$. Then there exists an embedding of
%%   $G$ in this pair of pants such that:

%%   \begin{itemize}
%%   \item The boundary vertices of $G$ are placed on $\partial P$ as in the original embedding.
%%   \item Every edge is embedded as a concatenation of a constant number of shortest paths.
%%     \end{itemize}
%% \end{proposition}




%% Our starting point is the following result of Yves Colin de Verdière~\cite{c-crgts-91}, which generalizes Tutte's theorems to a metric of negative curvature. 

%% \begin{theorem}[{\cite[Theorem~3]{c-crgts-91}}]\label{T:yves}
%%   Let $m$ be a metric of nonpositive curvature on a simply connected
%%   surface $S$. Let $G$ be a graph embedded on $S$, such that the
%%   boundary vertices of $G$ lie on a convex polygon. Three or more
%%   boundary points can be on the same boundary geodesic, but then there
%%   can be no edge between them unless they are joined by a boundary
%%   edge. Denote by $\alpha_{ij}$ the curve representing the edge
%%   $(i,j)$. For every assignment $c_{i,j} : E(G) \to R^+$ the map $G
%%   \to S$ minimizing the energy functional

%%   \[\sum_{(i,j )\in E} \int c_{ij} ||\alpha_{ij}'(t)||^2 dm\]
%%   among all maps in the homotopy class of the given embedding, is an
%%   embedding of $G$ that is isotopic to the original embedding such
%%   that the edges are represented by geodesics.
%% \end{theorem}

%% \note{This variant is actually not proved by Yves. I plan to add an appendix commenting on how to prove it -- this is polite in any case since the whole paper is in French and written in a surprising style.}


%% %A metric $m$ on a surface with boundary is said to have \emph{convex
%% %  boundary components} if the distance between two points in the same
%% %boundary component points is attained only by curves that stay on the
%% %boundary.

%% \begin{proposition}\label{P:pantsyves} Let $G$ be an embedded graph triangulating a pair of pants $P$, and denote by $\gamma_1$, $\gamma_2$ and $\gamma_3$ the three boundary cycles of $G$. If:
%% \begin{itemize}
%% \item For each boundary component, and $x,y$ vertices of $G$, if $x,y \in \gamma_i$ and $(x,y)$ is an edge of $G$, then $(x,y) \subset \gamma_i$.
%% \item There exist pairwise disjoint simple paths $\gamma_{1,2}, \gamma_{1,3}$ and $\gamma_{2,3}$ in $G$ such that $\gamma_{i,j}$ connects $\gamma_i$ and $\gamma_j$.
%% \end{itemize}
%% For the hyperbolic metric $m_P$, there exists an embedding of $G$ on $P$ such that each edge is drawn as a shortest path. 
%% \end{proposition}


%% \begin{proof}
%%   We first notice that the hypothesis on the graph imply that we can assume
%%   without loss of generality that every edge between two vertices of
%%   $\gamma_{i,j}$ is contained in $\gamma_{i,j}$. Indeed if this was
%%   not the case, we could shortcut the path without losing its
%%   defining properties.

%%   Let us denote by $\hat{\gamma_i}$ each of the boundaries of $P$. Let $\hat{\gamma_{i,j}}$ denote the shortest path with respect to $m$ between the boundary components $\hat{\gamma_i}$ and $\hat{\gamma_j}$, and denote by $\hat{v_{i,j}}$ the vertex at the intersection of $\hat{\gamma_i}$ and $\hat{\gamma_{i,j}}$. By symmetry, on a boundary $\hat{\gamma_i}$ the points $\hat{v_{i,j}}$ and $\hat{v_{i,k}}$ are antipodal.


%% Our strategy to embed $G$ will be to first embed the boundary cycles
%% $\gamma_i$ and the disjoint paths $\gamma_{i,j}$ as $\hat{\gamma_i}$
%% and $\hat{\gamma_{i,j}}$, and then to cut along them and apply
%% Theorem~\ref{T:yves} to embed the remaining graphs in the polygons we
%% obtain. An embedding of $\gamma_i$ into $\hat{\gamma_i}$ is defined by subdividing $\hat{\gamma_i}$ in the appropriate number of subpaths so as to place the vertices of $\gamma_i$, and similarly for embedding $\gamma_{i,j}$ into $\hat{\gamma_{i,j}}$. For $\gamma_i$, this subdivision is obtained by placing the vertices $\gamma_i \cap \gamma_{i,j}$ at $\hat{v_{i,j}}$, and then placing the remaining vertices at equal distances. For $\gamma_{i,j}$, it suffices to place the vertices at equal distances along $\hat{\gamma_{i,j}}$.

 
%% Now we cut $P$ along the curves $\hat{\gamma_i}$ and
%% $\hat{\gamma_{i,j}}$ to obtain two identical hyperbolic right-angled hexagons. Remember that $m_P$ is defined by the fact that these hyperbolic hexagons are equilateral. The edges
%% lying on the boundaries of the hexagons are shortest paths by
%% construction and the convexity assumption. Theorem~\ref{T:yves} allows
%% us to embed the remainder of the graph with geodesics in the two
%% hyperbolic hexagons -- we are allowed to apply it thanks to the first
%% hypothesis on $G$ and the preliminary observation. Since a hyperbolic
%% hexagon is convex, geodesics are shortest paths in this hexagon. To
%% conclude, we paste back the two hexagons to obtain a triangulated pair
%% of pants.


%% There remains to prove that shortest paths in the hexagons are also
%% shortest path in the pair of pants. This is true because the two
%% hexagons are identical: any path going through the second hexagon can
%% be mirrored and go through the first one while preserving the same
%% length and connecting the same endpoints. Therefore, shortest paths in
%% the hexagons are also shortest paths in the pair of pants. This
%% concludes the proof. \note{A:looks correct to me now}
%% \end{proof}

%% %\textbf{Remark}: Let us discuss 


%% %In the hyperbolic case, every pair of pants for which the length of the three boundary components is the same, if the boundary components are geodesics then they are convex. \note{Arnaud: that's not true: the non-trivial homotopic path with two endpoints on the boundary could shortcut it. But if the lengths of the boundaries are short enough it should be fine}


%% The positions on the vertices on the boundary obtained by the previous
%% proposition might not match the ones we are looking for. In order to
%% correct this, we ``rewire'' the edges in a $\varepsilon$-neighborhood
%% $C_{\varepsilon}$ of the boundaries. For $\varepsilon$ small enough,
%% the hyperbolic collar lemma (see for example
%% Parlier~\cite{p-pncscg-05}) shows that this neighborhood is a
%% topological cylinder, called a \textit{half-collar}, and that it is
%% isometric to $[0,\varepsilon] \times \mathbb{S}^1$ endowed with the
%% metric $ds^2=d\rho^2 + \ell^2 cosh^2 \rho dt^2$, where $\ell$ is the
%% length of the boundary.


%% \begin{lemma}\label{L:collar}
%% Let $C$ be a hyperbolic half-collar corresponding to the $\varepsilon$-neighborhood of the boundary of a pair of pants $P$, endowed with the metric $m_P$. Denote the two boundaries of $C$ by $C_1$ and $C_2$. For two sets of positions of $k$ vertices $f: V \rightarrow C_1$ and $g: V \rightarrow C_2$ with the same cyclic ordering, there exist disjoint edges connecting each vertex in $C_1$ to its counterpart in $C_2$ as a concatenation of at most $3$ shortest paths of $P$.
%% \end{lemma}

%% \begin{proof}
%%   We first pick a shortest path $\gamma$ in $C$ between a vertex in $C_1$ and its counterpart in $C_2$. Now, for every vertex $v$ in $V$, there exists a unique geodesic in $C$ connecting $f(v)$ and $g(v)$ without crossing $\gamma$. Since the shortest path $\gamma$ winds at most a half turn around the cylinder, this geodesic winds at most one and a half times around the cylinder, see Figure..., and therefore can be cut into three geodesics doing less than a half-turn on the cylinder. These are shortest paths in $C$: for an intuition, if $\varepsilon$ is small enough the half-collar is very close metrically to the cylinder. This can be checked rigorously using the explicit metric in the universal cover of the cylinder.

%% There remains to prove that these are also shortest paths in $P$. By
%% choosing $\varepsilon$ small enough, our shortest paths are
%% arbitrarily close to subpaths of the boundary cycles doing at most a
%% half-turn. Therefore it suffices to prove that these are shortest
%% paths in $P$. This results from our choice of metric $m_P$: the length
%% of the shortest path not homotopic to a boundary connecting two points
%% on the same boundary of $P$ is lower bounded by the lengths of the two
%% ortho-geodesics cutting the equilateral hyperbolic hexagons into two
%% pentagons. Applying formulas for the lengths of right-angled
%% pentagons~\cite[Formula~2.6.17]{t-tdgt-97}, we see that this lower
%% bound is bigger than the half-length of a boundary cycle.\note{to
%%   explain more, and needs a figure}
%% \end{proof}

%% \note{That is a bit hand-waving but I find it convincing enough}



%% The second lemma shows that starting with any graph embedded on a pair of pants, we can modify it so that it fulfills the hypotheses of Proposition~\ref{P:pantsyves}


%% \begin{lemma}\label{L:subdiv}
%%   Let $G$ be a graph embedded on a pair of pants $P$. Then there exists a graph $G'$ containing $G$ where every edge has been subdivided at most a constant number of times, such that $G'$ fulfills the hypotheses of Proposition~\ref{P:pantsyves}, i.e.:
%%   \begin{itemize}
%%   \item For every pair of vertices $x,y$ of $G'$ on the boundary of $P$, if $(x,y)$ is an edge of $G'$ then it is a boundary edge.
%%   \item There exist disjoint paths $\gamma_{1,2}$, $\gamma_{1,3}$ and $\gamma_{2,3}$ connecting the three boundaries of the pair of pants pairwise.
%%   \end{itemize}
%% \end{lemma}

%% \begin{proof}
%%  We start by triangulating $G$. Then, in order to fulfill the first hypothesis, it is enough to subdivide every edge that does not satisfy it, i.e., for every edge $e=(x,y)$ such that $x$ and $y$ are on a boundary $\gamma_i$ but $(x,y)$ is not in $\gamma_i$, we subdivide $e$ once and and triangulate the result.

%% In order to fulfill hypothesis $3$, we use the following subdivision scheme. \note{this will be painful and uninteresting. Should be hidden in the appendix}
  
%% \end{proof}

%% We are now ready to prove Proposition~\ref{P:embed}.

%% \begin{proof}[Proof of Proposition~\ref{P:embed}]
%%   We start with a graph $G$ embedded on a pair of pants $P$. We apply
%%   Lemma~\ref{L:subdiv} to obtain a graph $G'$ such that every edge of
%%   $G$ corresponds to a concatenation of $O(1)$ edges of
%%   $G'$. Furthermore, $G'$ verifies the hypotheses of
%%   Proposition~\ref{P:pantsyves}. After applying it, we obtain an
%%   embedding of $G'$ in $P$ such that each edge of $G'$ is a shortest
%%   path. By construction, this also gives an embedding of $G$ such that
%%   each edge is a concatenation of a constant number of shortest paths. But the vertices on the boundaries might not be equally spaced.

%%   To correct this, we denote by $P_{\varepsilon}^i$ a $\varepsilon$-neighborhood of $\gamma_i$ and we consider the restriction of the embedding $G$ to $P_{\varepsilon}= P \setminus \{ \bigcup_i P_{\varepsilon}^i \}$. If $\varepsilon$ is chosen small enough, by compacity, this is still an embedding of $G$. We can now apply Lemma~\ref{L:collar} in the hyperbolic collars $P_{\varepsilon}^i$ so that the vertices of $G$ are equally spaced on the boundaries of $P$. This concludes the proof.


%% \end{proof}


%% \paragraph*{Finishing the proof}

%% We can now conclude the proof of Theorem~\ref{T:concat}.


%% \begin{proof}[Proof of Theorem~\ref{T:concat}]
%%   We start by defining the hyperbolic metric $m$ on $S_g$ that we will
%%   use. We describe $m$ by its \textit{Fenchel-Nielsen coordinates},
%%   which parameterize a point in the Teichm\"uller space of a
%%   surface. These coordinates are defined with respect to a pants
%%   decomposition $\Gamma=\{\gamma_1, \ldots, \gamma_{3g-3}\}$ of $S_g$:
%%   we will pick the one pictured in Figure~\ref{F:pants}. Then, a unique hyperbolic metric on
%%   $S_g$ is defined by a choice of \textit{length parameters}, which
%%   record the lengths of the curve $\gamma_i$ and \textit{twist
%%     parameters}, which record how each boundary of a pair of pants is
%%   twisted when being glued to the next one. We pick all the length
%%   parameters to be equal to \note{to compute} and all the twist
%%   parameters to be zero.


%%   Given an embedding of $G$ on $S_g$, by
%%   Theorem~\ref{T:pants-from-octagons}, there exists a pants
%%   decomposition $\Gamma$ of $S_g$ with the correct combinatorial type
%%   such that every curve $\gamma_i \in \Gamma$ cuts every edge of $G$
%%   transversely and a constant number of times. Therefore, after
%%   cutting $G$ along $\Gamma$, each edge is subdivided $O(g)$ times,
%%   yielding $G'$, and $G'$ is cut into $2g-2$ subgraphs $G_i$, each of
%%   them being embedded in a pair of pants $P$. 

%%   We can now apply Proposition~\ref{P:Embed} to embed all the graphs
%%   $G_i$ separately on the pairs of pants, and such that the edges are
%%   concatenations of a constant number of shortest paths. There remains
%%   to glue these embeddings together, which can be done since in
%%   Proposition~\ref{P:Embed}, the vertices on the boundaries of the
%%   pair of pants are placed at the same positions as in $G'$: in particular they match.


%%   We claim that shortest paths in $P$ are also shortest paths
%%   in $S_g$, this is proved in Lemma~\ref{L:shortestglobal}. Since
%%   edges have been subdivided $O(g)$ times between $G$ and the $G_i$,
%%   this concludes the proof of Theorem~\ref{T:concat}.
%% \end{proof}




%% \begin{lemma}\label{L:shortestglobal}
%% We consider the surface $S_g$ endowed with the hyperbolic metric $m$,
%% and cut along $\Gamma$ into pairs of pants $P_i$. Let $x$ and $y$ be
%% two points on $P_i$ and $\alpha: [0,1] \rightarrow P_i$ an arc between
%% them. If $\alpha$ is a shortest path on $P_i$, then it is a shortest path
%% on $S_g$.
%% \end{lemma}

%% \begin{proof}
%% Let us assume by contradiction that there is another edge $\beta$
%% between $x$ and $y$ in $S_g$ that is shorter than $\alpha$. Since
%% $\alpha$ is a shortest path in $P_i$, and there are no self-loops in
%% the intersection graph of the pants decomposition\note{more details},
%% it means that $\beta$ goes through the complement $S_g \setminus P$ of
%% $P$ in $S_g$. Let us denote by $\beta_k$ the maximal subpaths of
%% $\beta$ in $S_g \setminus P$. Each $\beta_k$ connects two vertices
%% $b_{k,1}$ and $b_{k,2}$ on the boundaries of $P$, and we denote by
%% $\tilde{\beta_k}$ the shortest path in $P$ between $b_{k,1}$ and
%% $b_{k,2}$. We claim that $\tilde{\beta_k}$ is not longer than
%% $\beta_k$: this simply results from the fact that the metric picked on
%% each pair of pants is identical. By substituting
%% $\tilde{\beta_k}$ for $\beta_k$ for every $k$, we obtain an edge
%% between $x$ and $y$ that is not longer than $\beta$ but stays within
%% $P$. This is a contradiction.



%% \end{proof}






%We are ready to put together the combinatorial and Riemanian ingredients. We begin with a intersection multigraph $H$ that will be fixed together with a rotation $\theta \in [0,2\pi)$ decorating each of the edges. We choose any metric $m'$ on $S_{0,3}$ with convex boundary components all of which have the same length. The metric $m$ in the theorem is given by pasting pairs of pants isometric to $m'$ according to $H$.  

%\begin{proof}
%By proposition .. we can find a pants decomposition with intersection multigraph $H$ such that each curve $\{\gamma_1,\gamma_2\ldots \gamma_{3g-3}\}$ of the pair of pants intersects each edge of $T^*$ at most a constant $c$ times. 
%We make $c'g$ subdividisions of the primal $T$. Each subdivision consists of inserting the midpoint of each edge and connecting each midpoint to the neighboring ones. Denote the subdivision by $T'$. The number of subdivisions $c'g$ is chosen so that each the curves $\gamma_i$ can be isotoped simultaneously to run along the $1$ skeleton of $T'$ and so that the resulting curves are pairwise disjoint. By making one more subdivision we obtain a simplicial complex that satisfies the assumptions of proposition .... Applying the proposition on  each pair of pants we obtain an embedding of the subdivided triangulation on which each edge is a shortest path. The edges of the original graph can be routed through the edges of the subdivided graph. Therefore they are concatenations of at most $c'g$ shortest paths.
%\end{proof}

%There are details to take care about the subdivision. 

%Proof:

%- The metric is the one obtained with a fixed pants decomposition (no matter which one), where all the pants are endowed with exactly the same hyperbolic metric, and this metric gives the same length to the three boundaries.

%- Starting with an embedded graph, the first step is to cut it into this fixed pair of pants, such that every edge is used a constant number of times by each cycle of the pants decomposition, and therefore $O(g)$ times in total. To do that, we use Martin's idea from Ouessant: start with any pants decomposition with the correct complexity (this is done for example in a paper of Eric Colin de Verdière and Francis Lazarus), extract a subfamily of cycles such that cutting along it gives a sphere with 2g boundaries (eg contract a spanning tree in the cubic graph describing the pants decomposition), cut along this subfamily and apply the planar result of Matou\v{s}ek, Sedgwick, Tancer, Wagner.

%- Subdivide (barycentric subdivision) the graph $O(g)$ times so that every edge can now be assigned to a single curve in the pants decomposition.

%- There just remains to embed the remaining pieces separately on pairs of pants such that every edge is a shortest paths (or a %concatenation of not too many shortest paths).



%\section{Appendix: Buser-Sarnak arithmetic surfaces.}
%In this section we give an account of the Buser-Sarnak construction and akin constructions. Let $a,b \in \mathbb{Z}^+$,  let $A(\mathbb{Q},(a,b))$ be the (quaternion) algebra generated by $1,i,j,k$ with relations $i^2=a$, $j^2=b$, $ij=-ji=k$. If $a$ and $b$ are chosen so that  for every quaternion $X=x_0+ x_1i+x_2j+x_3k$ different from zero the norm  $$N(X)=N(x_0+ x_1i+x_2j+x_3k)={x_0}^2-a{x_1}^2-b{x_2}^2-ab{x_3}^2,$$
%is also different from zero, (why can $a$ and $b$ be chosen like that?) then $A(\mathbb{Q},(a,b))$ is a division algebra, (i.e., it has multiplicative inverses) ($A(\mathbb{Q},(a,b))$ is a vector space over $\mathbb{Q}$). Now let $\Gamma= \{X \in A(\mathbb{Z},(a,b)): N(X)=1\}$, notice that for elements of $\Gamma$,  $N(X_1 X_2)=N(X_1)N(X_2)=1$ and $X_1X_2$ has integer coefficients, moreover every multiplicative inverse also has integer coefficients, hence $\Gamma$ is a group. Let $\Gamma(p)=\{X \in \Gamma: X \equiv 1 \pmod p)\}$  (i.e. $x_0\equiv 1  \pmod p)$ and $x_l \equiv 0 \pmod p)$ for $l>0$. Notice that $\Gamma(p)$ is a subgroup.
%Now define a map $\phi\colon A(\mathbb{Q},(a,b)) \to SL(R,2)$,
 %\[ \phi(X)=
 %\left( \begin{array}{ccc}
%x_0+x_1\sqrt{a} & x_2+x_3 \sqrt{a}  \\
%b(x_2-x_3 \sqrt{a}) & x_0-x_1\sqrt{a} \\
%\end{array} \right)\] 
%The group $SL(2,R)$ is a subgroup of the group of Moebius transformations on the complex plane. In the upper half plane model of the hyperbolic plane, geodesics are given by vertical lines and circles that intersect perpendicularly the real line.  Since elements of $SL(2,R)$ preserve the real line they preserve the whole upper half plane $\mathbb{H}$. Since they are Moebius transformations we can conclude that they send geodesics to geodesics. Abusing notation we consider $\Gamma$ and $\Gamma(p)$ as subgroups of $SL(2,R)$, (they are called Fuchian groups). Notice that the action of $\Gamma(p)$ is free as an easy computation shows. No orbit has accumulation points so the quotient space $\mathbb{H}/\Gamma(p)$ is a compact surface. It has genus $p(p-1)(p+1)v+1$ where $v(a,b)$. (why?)
%Now to compute its systole we look in the universal cover of the surface, we want two points $\eta, \eta'$ belonging to the same orbit. Let  $\alpha=x_0+ x_1i+x_2j+x_3k\in \Gamma(p)$ so that $\alpha(\eta)=\eta'$. By assumption $p|x_l$ for $l=\{1,2,3\}$ hence $x_0^2\equiv 1 (mod p^2)$

\ifappendix
\else %content of the appendix in the main body
\subparagraph*{Tutte's embedding theorem in a hyperbolic setting.}

Here we explain the proof of the subsequent theorem, following the
arguments of Y. Colin de Verdi\`ere~\cite{c-crgts-91}.

\TYves*

As announced, the proof follows from a spring-like construction,
i.e. we think of the edges of the graph $G$ as springs with some
arbitrary stiffness, the vertices which are not on the boundary are
allowed to move and we prove that the equilibrium state for this
physical system is an embedding of the graph.

For an embedding $\varphi: G \rightarrow H$, denote by
$e_{ij}$ the map $[0,1] \rightarrow H$ representing the edge
$(i,j)$. Starting with an embedding $\varphi_0: G \to H$ and given assignments $c_{i,j} : E(G) \to \mathbb{R}^+$, we are interested in the map $\varphi: G \to
H$ minimizing the energy functional

   \[E_{\varphi}=\sum_{(i,j )\in E} \int_0^1 c_{ij} ||e_{ij}'(t)||^2 dm_H\]
with fixed vertices on the boundary of $H$. This is the equilibrium
state of the spring system with the $c_{i,j}$ coefficients specifying
the stiffness of the springs. We claim that $\varphi$ is an embedding
such that the edges are geodesics.

\textbf{Step 1: Existence.} The existence of $\varphi$ follows from
classical compactness considerations, since an Arzel\`a-Ascoli argument proves the compactness of
sets with bounded energy. Then an extremum of $E_{\varphi}$ corresponds to
a $\varphi$ where all the arcs $e_{i,j}$ are geodesics. Furthermore,
every vertex $\varphi(x)$ which is not on the boundary lies in the
strict hyperbolic convex hull of its neighbors which are not mapped to
the same point.


%\arnaud{There is also uniqueness, but I do not think we care here}
%\vojta{Does ``compacity'' above mean ``compactness''? If it does, then I would suggest to change it, I have never heard it before and neither Google translate. If it does not, just erase this comment.}
%\arnaud{Thanks, that was an ugly gallicism.}
\textbf{Step 2: Curvature considerations.} Since $\varphi_0$ provides
an embedding of $G$ into $H$, $G$ can be seen as a topological subspace
of $H$. The corresponding simplicial complex will be denoted by $X$
(it is of course homeomorphic to $H$) and its set of vertices, edges and triangles by $V$, $E$, and $T$. By extending $\varphi$ separately with
a local homeomorphism in the interior of each non-degenerate triangle,
we can extend it into a map $\Phi: X \rightarrow H$ agreeing
with $\varphi$ on $G$.

Now, the map $\Phi:X \rightarrow H$ provides values for the angles
of the non-degenerate triangles in $X$. For degenerate
triangles, values of the angles are taken arbitrarily so that they sum
to $\pi$ (therefore morally their hyperbolic area is zero). For an interior vertex
$v$, let us define the curvature $K(v)= 2 \pi - \sum_i \alpha^i_v$, where
$\alpha^i_v$ are the angles adjacent to $v$. For a vertex $v$ on the interior
of a geodesic boundary, we define it by $K(v)= \pi - \sum_i \alpha_v^i$,
and on the six vertices of $H$, we take it to be $K(v)=\pi/2 - \sum_i
\alpha_v^i$.

The area of a geodesic hyperbolic triangle is $\pi$ minus the sum of
its angles. Summing over all the triangles of $\Phi(X)$, we obtain
$|T| \pi - \sum_v \sum_i \alpha^i_v = \sum_{t \in T} Area(t)$. With
Euler's formula and double counting, this gives $\sum_{t \in
  T} Area(t)=\pi + \sum_v K(v)$. Since the boundary is fixed, $\Phi$ has degree one and is thus
surjective, therefore the sum of the areas of the triangles is at least the area of the hexagon, which is $\pi$ since it is
right-angled. Therefore $\sum_v K(v) \geq 0$.

\textbf{Step 3: Punctual degeneracies.} In this step we investigate
which subcomplexes of $X$ can be mapped to a single point. We show
that no triangle can be mapped to a single point, and that a set of
edges mapped to a single point forms a path subgraph in $G$.

Let $X_1$ be a maximal connected subcomplex of $X$ which is mapped to
a point $x$ by $\Phi$. This subcomplex has to be simply connected,
otherwise the region inside could be mapped to $x$ as well which would
reduce the value of $E_{\varphi}$. Since the boundary edges are fixed
by $\varphi$, $X_1$ does not contain any edge on the boundary or
triangle adjacent to the boundary.

For every vertex $v$ in $\Phi^{-1}(x)$, $\Phi(v)=\varphi(v)$ lies in
the strict convex hull of its neighbors which are not mapped to $x$,
as was observed in Step 1. Therefore the angles of the non-degenerate
triangles adjacent to $v$ sum up to at least $2 \pi$. Indeed the
angular opening at $\varphi(v)$ has to be at least $\pi$ by the
convexity hypothesis, but any map $\mathbb{S}^1 \rightarrow
\mathbb{S}^1$ is either surjective or at least two-to-one everywhere,
in which case this angular opening of at least $\pi$ amounts to at
least $2 \pi$ in the sum of angles around $v$. This shows that
$K(x):=\sum_{v \in \Phi^{-1}(x)} K(v)$ is nonpositive. Since the
boundary edges are fixed, we also have $K(v)\leq 0$ for the vertices
on the boundary.

Summing over all the values of $x$, we obtain that $\sum_v K(v) \leq
0$, and thus this sum is zero by the previous paragraph, and each of
the $K(x)$ is also zero.


From that we infer that $X_1$ contains no triangle: if it did, there
would be at least $3$ preimages of $x$ for which the angles of the
adjacent non-degenerate triangles would sum up to at least
$2\pi$. Summing them into $K(x)$ we would obtain a nonzero
value. Similarly, $X_1$ can only be a linear subgraph of
$G$, and every triangle adjacent to a $X_1$ not reduced to a point is degenerate.

%Furthermore, if $X_1$ is not reduced to a point, any triangle
%with at least one vertex in $X_1$ is degenerate



\textbf{Step 4: Linear degeneracies.} Now that we showed that
triangles can not be mapped to points, we show that triangles are not
mapped to lines either, or equivalently that edges are not mapped to
points.

Let $X_2$ be a maximal connected subcomplex of $X$ such that the image
of the triangles of $X_2$ by $\varphi$ are degenerate. Let us assume
that $X_2$ is non-empty. Then the image $\Phi(X_2)$ is an arc of a
geodesic of $H$: indeed if there was a broken line in $\Phi(X_2)$,
around the breaking points there would be non-degenerate triangles
adjacent to a $X_1$ not reduced to a point, which is absurd by the
previous paragraph.

%If one of the components of $X \setminus X_2$ was a topological disk not adjacent to a boundary

If this geodesic is not a boundary geodesic of $H$, two of the points
on the boundary of $X_2$ are mapped to the endpoints of the arc of
geodesic, and all the other vertices have their adjacent edges within
$X_2$ because of the convexity condition. Therefore, there must be two
arcs connecting the two boundary points, as in the top of
Figure~\ref{F:appendix}, which is impossible in the simplicial complex
$X$.

\begin{figure}
  \centering
  \def\svgwidth{11cm}
  \input{appendix.pdf_tex}
  %  \includegraphics[width=.9\textwidth]{appendix}
  \caption{Any triangulation inducing a linear degeneracy would require either multiple edges (top) or a dividing edge (bottom).}
  \label{F:appendix}
\end{figure}


If this geodesic is on the boundary of $H$, then by the same convexity
argument, two vertices of $\partial X$ must map to the endpoints of
this arc of geodesic, and the other vertices have all their edges
within $X_2$. Therefore there is a dividing edge connecting these two
vertices, as in the bottom of Figure~\ref{F:appendix}, which is a contradiction.



\textbf{Step 5: Conclusion} Since $X_2$ is empty, no triangle in the
image of $\Phi$ is degenerate. Furthermore, all the $X_1$
are reduced to a single point and thus $K(v)$ is zero for all the
vertices $v$. The only remaining possible pathology is if all the
triangles adjacent to a non-boundary vertex $v$ are mapped to a
half-plane around $\Phi(v)$. By the convexity constraint, this can
only happen if the edges adjacent to $v$ are aligned, but this would
yield degenerate triangles. Therefore $\Phi$ is a local homeomorphism of degree $1$, hence it is a global homeomorphism and $\varphi$ is an embedding.
\fi %the end of \ifappendix

\subparagraph*{Acknowledgements} We are grateful to \'Eric Colin de Verdi\`ere for his involvement in the early stages of this research. We also thank  Sergio Cabello, Francis Lazarus, Bojan Mohar, Eric Sedgwick and Uli Wagner for helpful discussions and Xavier Goaoc for organizing the workshop that led to this work.
%\alfredo{This work was . .}
%\arnaud{You don't want to put this in the footnote of the title page? }


\bibliographystyle{plain} \bibliography{biblio}

\ifappendix
\appendix




\section{Tutte's embedding theorem in a hyperbolic setting}\label{A:Yves}

%\arnaud{I write this mainly to convince myself that it is true -- but this is a logical appendix to the paper, especially since the paper of Yves is in French. On the other hand it is impossible to summarize 10 pages into 2 and have something easily readable.}

In this section, we explain the proof of the subsequent theorem, following the
arguments of Y. Colin de Verdi\`ere~\cite{c-crgts-91}.

\TYves*

As announced, the proof follows from a spring-like construction,
i.e. we think of the edges of the graph $G$ as springs with some
arbitrary stiffness, the vertices which are not on the boundary are
allowed to move and we prove that the equilibrium state for this
physical system is an embedding of the graph.

For an embedding $\varphi: G \rightarrow H$, denote by
$e_{ij}$ the map $[0,1] \rightarrow H$ representing the edge
$(i,j)$. Starting with an embedding $\varphi_0: G \to H$ and given assignments $c_{i,j} : E(G) \to \mathbb{R}^+$, we are interested in the map $\varphi: G \to
H$ minimizing the energy functional

   \[E_{\varphi}=\sum_{(i,j )\in E} \int_0^1 c_{ij} ||e_{ij}'(t)||^2 dm_H\]
with fixed vertices on the boundary of $H$. This is the equilibrium
state of the spring system with the $c_{i,j}$ coefficients specifying
the stiffness of the springs. We claim that $\varphi$ is an embedding
such that the edges are geodesics.

\textbf{Step 1: Existence.} The existence of $\varphi$ follows from
classical compactness considerations, since an Arzel\`a-Ascoli argument proves the compactness of
sets with bounded energy. Then an extremum of $E_{\varphi}$ corresponds to
a $\varphi$ where all the arcs $e_{i,j}$ are geodesics. Furthermore,
every vertex $\varphi(x)$ which is not on the boundary lies in the
strict hyperbolic convex hull of its neighbors which are not mapped to
the same point.


%\arnaud{There is also uniqueness, but I do not think we care here}
%\vojta{Does ``compacity'' above mean ``compactness''? If it does, then I would suggest to change it, I have never heard it before and neither Google translate. If it does not, just erase this comment.}
%\arnaud{Thanks, that was an ugly gallicism.}
\textbf{Step 2: Curvature considerations.} Since $\varphi_0$ provides
an embedding of $G$ into $H$, $G$ can be seen as a topological subspace
of $H$. The corresponding simplicial complex will be denoted by $X$
(it is of course homeomorphic to $H$) and its set of vertices, edges and triangles by $V$, $E$, and $T$. By extending $\varphi$ separately with
a local homeomorphism in the interior of each non-degenerate triangle,
we can extend it into a map $\Phi: X \rightarrow H$ agreeing
with $\varphi$ on $G$.

Now, the map $\Phi:X \rightarrow H$ provides values for the angles
of the non-degenerate triangles in $X$. For degenerate
triangles, values of the angles are taken arbitrarily so that they sum
to $\pi$ (therefore morally their hyperbolic area is zero). For an interior vertex
$v$, let us define the curvature $K(v)= 2 \pi - \sum_i \alpha^i_v$, where
$\alpha^i_v$ are the angles adjacent to $v$. For a vertex $v$ on the interior
of a geodesic boundary, we define it by $K(v)= \pi - \sum_i \alpha_v^i$,
and on the six vertices of $H$, we take it to be $K(v)=\pi/2 - \sum_i
\alpha_v^i$.

The area of a geodesic hyperbolic triangle is $\pi$ minus the sum of
its angles. Summing over all the triangles of $\Phi(X)$, we obtain
$|T| \pi - \sum_v \sum_i \alpha^i_v = \sum_{t \in T} Area(t)$. With
Euler's formula and double counting, this gives $\sum_{t \in
  T} Area(t)=\pi + \sum_v K(v)$. Since the boundary is fixed, $\Phi$ has degree one and is thus
surjective, therefore the sum of the areas of the triangles is at least the area of the hexagon, which is $\pi$ since it is
right-angled. Therefore $\sum_v K(v) \geq 0$.

\textbf{Step 3: Punctual degeneracies.} In this step we investigate
which subcomplexes of $X$ can be mapped to a single point. We show
that no triangle can be mapped to a single point, and that a set of
edges mapped to a single point forms a path subgraph in $G$.

Let $X_1$ be a maximal connected subcomplex of $X$ which is mapped to
a point $x$ by $\Phi$. This subcomplex has to be simply connected,
otherwise the region inside could be mapped to $x$ as well which would
reduce the value of $E_{\varphi}$. Since the boundary edges are fixed
by $\varphi$, $X_1$ does not contain any edge on the boundary or
triangle adjacent to the boundary.

For every vertex $v$ in $\Phi^{-1}(x)$, $\Phi(v)=\varphi(v)$ lies in
the strict convex hull of its neighbors which are not mapped to $x$,
as was observed in Step 1. Therefore the angles of the non-degenerate
triangles adjacent to $v$ sum up to at least $2 \pi$. Indeed the
angular opening at $\varphi(v)$ has to be at least $\pi$ by the
convexity hypothesis, but any map $\mathbb{S}^1 \rightarrow
\mathbb{S}^1$ is either surjective or at least two-to-one everywhere,
in which case this angular opening of at least $\pi$ amounts to at
least $2 \pi$ in the sum of angles around $v$. This shows that
$K(x):=\sum_{v \in \Phi^{-1}(x)} K(v)$ is nonpositive. Since the
boundary edges are fixed, we also have $K(v)\leq 0$ for the vertices
on the boundary.

Summing over all the values of $x$, we obtain that $\sum_v K(v) \leq
0$, and thus this sum is zero by the previous paragraph, and each of
the $K(x)$ is also zero.


From that we infer that $X_1$ contains no triangle: if it did, there
would be at least $3$ preimages of $x$ for which the angles of the
adjacent non-degenerate triangles would sum up to at least
$2\pi$. Summing them into $K(x)$ we would obtain a nonzero
value. Similarly, $X_1$ can only be a linear subgraph of
$G$, and every triangle adjacent to a $X_1$ not reduced to a point is degenerate.

%Furthermore, if $X_1$ is not reduced to a point, any triangle
%with at least one vertex in $X_1$ is degenerate



\textbf{Step 4: Linear degeneracies.} Now that we showed that
triangles can not be mapped to points, we show that triangles are not
mapped to lines either, or equivalently that edges are not mapped to
points.

Let $X_2$ be a maximal connected subcomplex of $X$ such that the image
of the triangles of $X_2$ by $\varphi$ are degenerate. Let us assume
that $X_2$ is non-empty. Then the image $\Phi(X_2)$ is an arc of a
geodesic of $H$: indeed if there was a broken line in $\Phi(X_2)$,
around the breaking points there would be non-degenerate triangles
adjacent to a $X_1$ not reduced to a point, which is absurd by the
previous paragraph.

%If one of the components of $X \setminus X_2$ was a topological disk not adjacent to a boundary

If this geodesic is not a boundary geodesic of $H$, two of the points
on the boundary of $X_2$ are mapped to the endpoints of the arc of
geodesic, and all the other vertices have their adjacent edges within
$X_2$ because of the convexity condition. Therefore, there must be two
arcs connecting the two boundary points, as in the top of
Figure~\ref{F:appendix}, which is impossible in the simplicial complex
$X$.

\begin{figure}
  \centering
  \def\svgwidth{11cm}
  \input{appendix.pdf_tex}
  %  \includegraphics[width=.9\textwidth]{appendix}
  \caption{Any triangulation inducing a linear degeneracy would require either multiple edges (top) or a dividing edge (bottom).}
  \label{F:appendix}
\end{figure}


If this geodesic is on the boundary of $H$, then by the same convexity
argument, two vertices of $\partial X$ must map to the endpoints of
this arc of geodesic, and the other vertices have all their edges
within $X_2$. Therefore there is a dividing edge connecting these two
vertices, as in the bottom of Figure~\ref{F:appendix}, which is a contradiction.



\textbf{Step 5: Conclusion.} Since $X_2$ is empty, no triangle in the
image of $\Phi$ is degenerate. Furthermore, all the $X_1$
are reduced to a single point and thus $K(v)$ is zero for all the
vertices $v$. The only remaining possible pathology is if all the
triangles adjacent to a non-boundary vertex $v$ are mapped to a
half-plane around $\Phi(v)$. By the convexity constraint, this can
only happen if the edges adjacent to $v$ are aligned, but this would
yield degenerate triangles. Therefore $\Phi$ is a local homeomorphism of degree $1$, hence it is a global homeomorphism and $\varphi$ is an embedding.
\fi %end of \ifappendix


\end{document}

arXiv.bbl
\begin{thebibliography}{10}

\bibitem{ab-tms-01}
Dan Archdeacon and C.~Paul Bonnington.
\newblock Two maps on one surface.
\newblock {\em Journal of Graph Theory}, 36(4):198--216, 2001.

\bibitem{bm-rcrs-04}
Robert Brooks and Eran Makover.
\newblock Random construction of {R}iemann surfaces.
\newblock {\em J. Differential Geom.}, 68(1):121--157, 2004.

\bibitem{bs-pmrsl-94}
Peter Buser and Peter Sarnak.
\newblock On the period matrix of a {R}iemann surface of large genus (with an
  appendix by {J.H.} {C}onway and {N.J.A.} {S}loane).
\newblock {\em Inventiones Mathematicae}, 117:27--56, 1994.

\bibitem{ce-tnpcs-10}
{\'E}ric Colin~de Verdi{\`e}re and Jeff Erickson.
\newblock Tightening nonsimple paths and cycles on surfaces.
\newblock {\em SIAM Journal on Computing}, 39(8):3784--3813, 2010.

\bibitem{chm-dsidts-15}
\'{E}ric Colin~de Verdi\`{e}re, Alfredo Hubard, and Arnaud de~Mesmay.
\newblock Discrete systolic inequalities and decompositions of triangulated
  surfaces.
\newblock {\em Discrete \& Computational Geometry}, 53(3):587--620, 2015.

\bibitem{cl-opdsh-07}
{\'E}ric Colin~de Verdi{\`e}re and Francis Lazarus.
\newblock Optimal pants decompositions and shortest homotopic cycles on an
  orientable surface.
\newblock {\em Journal of the ACM}, 54(4):Article~18, 2007.

\bibitem{c-crgts-91}
Yves Colin~de Verdi\`ere.
\newblock Comment rendre g{\'e}od{\'e}sique une triangulation d'une surface~?
\newblock {\em L'Enseignement Math{\'e}matique}, 37:201--212, 1991.

\bibitem{c-rg-92}
Manfredo~P. do~Carmo.
\newblock {\em Riemannian geometry}.
\newblock Birkh{\"a}user, 1992.

\bibitem{ek-sepgfb-05}
{Cesim} {Erten} and {Stephen}~G. {Kobourov}.
\newblock Simultaneous embedding of planar graphs with few bends.
\newblock {\em Journal of Graph Algorithms and Applications}, 9(3):347--364,
  2005.

\bibitem{fm-pmcg-11}
Benson Farb and Dan Margalit.
\newblock {\em A primer on mapping class groups}.
\newblock Princeton University Press, 2011.

\bibitem{f-oslrp-48}
Istv{\'a}n F{\'a}ry.
\newblock On straight line representations of planar graphs.
\newblock {\em Acta scientiarum mathematicarum (Szeged)}, 11:229--233, 1948.

\bibitem{f-otoplm-03}
Michael Floater.
\newblock One-to-one piecewise linear mappings over triangulations.
\newblock {\em Mathematics of Computation}, 72(242):685--696, 2003.

\bibitem{ghr-epgm-13}
Jim {Geelen}, Tony {Huynh}, and R.~Bruce {Richter}.
\newblock {Explicit bounds for graph minors}.
\newblock ar{X}iv:1305.1451, 2013.

\bibitem{gro-83}
Mikhael Gromov.
\newblock Filling {R}iemannian manifolds.
\newblock {\em Journal of Differential Geometry}, 1983.

\bibitem{gpy-pdrs-11}
Larry Guth, Hugo Parlier, and Robert Young.
\newblock Pants decompositions of random surfaces.
\newblock {\em Geometric and Functional Analysis}, 21:1069--1090, 2011.

\bibitem{h-at-02}
Allen Hatcher.
\newblock {\em Algebraic topology}.
\newblock Cambridge University Press, 2002.
\newblock Available at \url{http://www.math.cornell.edu/~hatcher/}.

\bibitem{l-itt-87}
Serge Lawrencenko.
\newblock The irreducible triangulations of the torus.
\newblock {\em Ukrainski\u{i} Geometricheski\u{i} Sbornik}, 30:52--62, 1987.

\bibitem{ln-itkb-97}
Serge Lawrencenko and Seiya Negami.
\newblock Irreducible triangulations of the {K}lein bottle.
\newblock {\em Journal of Combinatorial Theory, Series~B}, 70(2):265--291,
  1997.

\bibitem{lpvv-ccpso-01}
Francis Lazarus, Michel Pocchiola, Gert Vegter, and Anne Verroust.
\newblock Computing a canonical polygonal schema of an orientable triangulated
  surface.
\newblock In {\em Proceedings of the 17th Annual Symposium on Computational
  Geometry (SOCG)}, pages 80--89. ACM, 2001.

\bibitem{mstw-utsnc-13}
Ji{\v r}{\'\i} Matou{\v s}ek, Eric Sedgwick, Martin Tancer, and Uli Wagner.
\newblock Untangling two systems of noncrossing curves.
\newblock In Stephen Wismath and Alexander Wolff, editors, {\em Graph Drawing},
  volume 8242 of {\em Lecture Notes in Computer Science}, pages 472--483.
  Springer International Publishing, 2013.

\bibitem{mstw-e3sd-14}
Ji\v{r}\'{\i} Matou\v{s}ek, Eric Sedgwick, Martin Tancer, and Uli Wagner.
\newblock Embeddability in the 3-sphere is decidable.
\newblock In {\em Proceedings of the Thirtieth Annual Symposium on
  Computational Geometry}, SOCG'14, pages 78--84. ACM, 2014.

\bibitem{m-gwpvrh-13}
Maryam Mirzakhani.
\newblock Growth of {W}eil-{P}etersson volumes and random hyperbolic surface of
  large genus.
\newblock {\em J. Differential Geom.}, 94(2):267--300, 06 2013.

\bibitem{m-dghp-99}
Bojan Mohar.
\newblock Drawing graphs in the hyperbolic plane.
\newblock In {\em Graph Drawing}, pages 127--136. Springer, 1999.

\bibitem{mt-gs-01}
Bojan Mohar and Carsten Thomassen.
\newblock {\em Graphs on surfaces}.
\newblock Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins
  University Press, 2001.

\bibitem{n-cngepc-01}
Seiya Negami.
\newblock Crossing numbers of graph embedding pairs on closed surfaces.
\newblock {\em Journal of Graph Theory}, 36(1):8--23, 2001.

\bibitem{rs-tmlrs-05}
R.~Bruce Richter and Gelasio Salazar.
\newblock Two maps with large representativity on one surface.
\newblock {\em Journal of Graph Theory}, 50(3):234--245, 2005.

\bibitem{s-gcnvs-13}
Marcus Schaefer.
\newblock The graph crossing number and its variants: a survey.
\newblock {\em The electronic journal of combinatorics}, 1000:DS21--May, 2013.

\bibitem{s-icptda-05}
Kenneth Stephenson.
\newblock {\em Introduction to circle packing: The theory of discrete analytic
  functions}.
\newblock Cambridge University Press, 2005.

\bibitem{s-gits-06}
Thom Sulanke.
\newblock Generating irreducible triangulations of surfaces.
\newblock arXiv preprint math/0606687, 2006.

\bibitem{s-nitkb-06}
Thom Sulanke.
\newblock Note on the irreducible triangulations of the {K}lein bottle.
\newblock {\em Journal of Combinatorial Theory, Series~B}, 96:964--972, 2006.

\bibitem{t-eggmnb-87}
Roberto Tamassia.
\newblock On embedding a graph in the grid with the minimum number of bends.
\newblock {\em SIAM Journal on Computing}, 16(3):421--444, 1987.

\bibitem{t-hgdv-13}
Roberto Tamassia.
\newblock {\em Handbook of graph drawing and visualization}.
\newblock CRC press, 2013.

\bibitem{t-hdg-63}
William~T. Tutte.
\newblock How to draw a graph.
\newblock {\em Proceedings of the London Mathematical Society}, 13:743--768,
  1963.

\bibitem{wil-81}
John~B. Wilker.
\newblock Inversive geometry.
\newblock In Chandler Davis, Branko Gr{\"u}nbaum, and F.A. Sherk, editors, {\em
  The Geometric Vein}. Springer New York, 1981.

\bibitem{w-gwpcts-03}
Scott~A. Wolpert.
\newblock Geometry of the {W}eil-{P}etersson completion of {T}eichm\"{u}ller
  space.
\newblock In {\em Surveys in differential Geometry, VIII}. Int. Press, 2003.

\end{thebibliography}
