% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \usepackage[utf8x]{inputenx} \usepackage{soul} \usepackage{verbatim} \usepackage{amsthm,amsmath,amssymb} %\usepackage{amscd} \usepackage{amsfonts} \usepackage{mathrsfs} \usepackage{graphics,graphicx} \usepackage{subfigure} \usepackage{psfrag} \usepackage{epic,eepic} \usepackage{color} \usepackage{latexsym} \usepackage{fullpage} \usepackage{psfrag, mathrsfs} \usepackage{euscript} %\usepackage{stmaryrd} %\usepackage{pstricks, pstricks-add, pst-math,pst-node} %\usepackage{pst-xkey} \usepackage{cite} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage{hypcap} \usepackage{enumerate} %\usepackage[left]{showlabels} \usepackage{lineno} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} % some additional math fonts \DeclareSymbolFont{slantedbx}{OT1}{cmr}{bx}{sl} \DeclareSymbolFontAlphabet\mathslbx{slantedbx} \DeclareSymbolFont{AMSa}{U}{msa}{m}{n} \DeclareMathSymbol{\upharpoonright} {\mathrel}{AMSa}{"16} \let\restriction\upharpoonright \def\parc#1{\restriction\!{#1}} % Commenter l'une de ces deux lignes %\RequirePackage[applemac]{inputenc} %\RequirePackage[latin1]{inputenc} \def\omu{{\overline{\mu}}} \def\oG{{\overline{G}}} \def\plane#1#2{{\Delta_{#1,#2}}} \def\half#1#2{{H_{#1,#2}}} \def\We{{\widetilde{e}}} \def\Wf{{\widetilde{f}}} \def\ol#1{{\overline{#1}}} \def\gmuv{{G-\{u,v\}}} \def\gd{{G^*_{u,v}}} \def\gde{{G_{u,v}}} \def\ff{{\cal F}} \def\gg{{\cal G}} \def\pp{{\cal P}} \def\ii{{\cal I}} \def\dd{{\cal D}} \def\w{{\ol{\lambda}}} \def\wuvd{{\lambda^*}} \def\wuv{{\lambda}} \def\wwuv{{\widetilde{\lambda}}} \def\dfufv{{L}} \def\muuvd{{\mu^*}} \def\muuv{{\mu}} \def\crn#1#2#3{{\text{\sc cr}(#1,(#2,#3))}} \def\ignore#1{{\vglue 0.05 cm}} \def\wa{{\omega}} \def\tmag#1{{\textcolor{magenta}{#1}}} \def\comm#1{{\marginpar{\tiny \tmag{#1}}}} \def\real{{\mathbb{R}}} \DeclareMathOperator{\cro}{\rm cr} \DeclareMathOperator{\mcro}{\bf cr*} \newcommand{\C}{\mathbb{C}} %\pagestyle{plain} %\sloppy %\setlength{\marginparwidth}{1.2in} %\setlength{\marginparsep}{0.35in} %\textwidth=17cm %\oddsidemargin=0in %\evensidemargin=0in %----------- A C O M P L E T E R P A R L E S A U T E U R S ------------ % Titre de l'article original (franc,ais ou anglais) \title{\bf Making a graph crossing-critical \\ by multiplying its edges} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Laurent~Beaudou\\ %\thanks{Supported by .}\\ \small LIMOS\\[-0.8ex] \small Universit\'e Blaise Pascal\\[-0.8ex] \small Clermont-Ferrand, France\\ \small\tt laurent.beaudou@univ-bpclermont.fr\\ \and C\'esar~Hern\'andez-V\'elez \qquad Gelasio~Salazar\thanks{Partially supported by CONACyT Grant 106432.}\\ \small Instituto de F\'{\i}sica\\[-0.8ex] \small Universidad Aut\'onoma de San Luis Potos\'{\i}\\[-0.8ex] \small San Luis Potos\'{\i}, M\'exico\\ \small\tt \{cesar,gsalazar\}@ifisica.uaslp.mx } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Dec 16, 2012}{Feb 18, 2013}\\ \small Mathematics Subject Classifications: 05C22, 05C62, 05C75} %%% 05C10 (1973-now) Planar graphs; geometric and topological aspects of graph theory %%% 05C22 (2000-now) Signed and weighted graphs %%% 05C62 (2000-now) Graph representations (geometric and intersection representations, etc.) For graph drawing %%% 05C75 (1980-now) Structural characterization of families of graphs \begin{document} %\linenumbers \maketitle % Re'sume' en anglais avec mots-cle's \begin{abstract} A graph is {\em crossing-critical} if the removal of any of its edges decreases its crossing number. This work is motivated by the following question: to what extent is crossing-criticality a property that is inherent to the structure of a graph, and to what extent can it be induced on a noncritical graph by multiplying (all or some of) its edges? It is shown that if a nonplanar graph $G$ is obtained by adding an edge to a cubic polyhedral graph, and $G$ is sufficiently connected, then $G$ can be made crossing-critical by a suitable multiplication of its edges. % keywords are optional % \bigskip\noindent \textbf{Keywords:} crossing number; connectivity; planarity \end{abstract} %%% I guess: explain what polyhedral means! (planar 3-connected, %%% that's it; we're following Riskin) \section{Introduction} \label{sec:intro} This work is motivated by the recent breakthrough constructions by DeVos, Mohar and \v{S}\'amal~\cite{devosetal} and Dvo\v{r}\'ak and Mohar~\cite{dvorakmohar}, which settled %in the affirmative two important %open crossing numbers questions. The graphs constructed in~\cite{devosetal} and~\cite{dvorakmohar} use weighted (or ``thick'') edges. A graph with weighted edges can be naturally transformed into an ordinary graph by substituting weighted edges by multiedges (recall that a {\em multiedge} is a set of edges with the same pair of endvertices). If one wishes to avoid multigraphs, one can always substitute a weight $t$ edge by a $K_{2,t}$, but still the resulting graph is homeomorphic to a multigraph. Sometimes (as in~\cite{devosetal}) one can afford to substitute each weighted edge by a slightly richer structure (such as a graph obtained from $K_{2,t}$ by joining the degree $2$ vertices with a path), but sometimes (as in~\cite{dvorakmohar}) one is concerned with criticality properties, and so no such superfluous edges may be added. In any case, the use of weighted edges is crucial. % An essential feature of these constructions is % the clever, careful use of weight assignments % to edges. Each edge $e$ is assigned a {\em weight} $w(e)$, %(equivalently, allowing parallel edges in the graphs upon %consideration). After trying unsuccessfully to come up with graphs with similar crossing number properties as those presented in~\cite{devosetal} and~\cite{dvorakmohar}, while avoiding the use of weighted edges, we were left with a wide open question: in the realm of crossing numbers, more specifically on crossing-criticality issues, to what extent does it make a difference to allow (equivalently, to forbid) weighted edges (or, for that matter, multiedges)? % SIMPLE GRAPHS everywhere??? %weighted edges (equivalently, to %allow for parallel edges)? %Our own investigation follows a related theme: the %addition of parallel edges to a graph in order to make it more %interesting from the viewpoint of crossing numbers. %turn large, interesting classes of graphs into crossing-critical. %We set out to explore further directions in which the %adecquate, careful addition of parallel edges (i.e., the {\em % multiplication} of edges) can yield interesting %results in the field of crossing numbers. %This work is motivated by the following question: how important and/or %useful is it to allow parallel edges when working with crossing %numbers? %which crossing %number results remain true if we disallow weighted graphs? Or, %equivalently for crossing number purposes: which results remain true %if we restrict ourselves to simple graphs with minimum degree at least %$3$? %\subsection{Making a graph crossing-critical by multiplying its edges}\label{sub:making} %\comm{Alternativo} \subsection{Crossing-critical graphs and multiedges} \label{subsec:crit} Recall that the {\em crossing number} $\cro(G)$ of a graph $G$ is the minimum number of pairwise intersections of edges in a drawing of $G$ in the plane. %%%(analogous definitions apply to other host surfaces). An edge $e$ of $G$ is {\em crossing-critical} if $\cro(G-e) < \cro(G)$. If all edges of $G$ are crossing-critical, then $G$ itself is {\em crossing-critical}. A crossing-critical graph seems naturally more interesting %(from the crossing numbers point of view) than a graph with some not crossing-critical edges, since a graph of the latter kind contains a proper subgraph that has all the relevant information from the crossing numbers point of view. %Now suppose that a (say, simple) graph $G$ is not %crossing-critical. We ask to Earlier constructions of infinite families of crossing-critical graphs made essential use of multiedges~\cite{siran0}. On the other hand, constructions such the ones given by Kochol~\cite{kochol}, Hlin\v{e}n\'y~\cite{hli1}, and Bokal~\cite{bokal} deal exclusively with simple graphs. We ask to what extent crossing-criticality is an inherent structural property of a graph, and to what extent crossing-criticality can be induced by multiplying the edges of a (noncritical) graph. Let $G, H$ be graphs. We say that $G$ {\em is obtained by multiplying edges of $H$} if $H$ is a subgraph of $G$ and, for every edge of $G$, there is an edge of $H$ with the same endvertices. \begin{question}\label{question1} When can a graph be made crossing-critical by multiplying edges? That is, given a (noncritical) graph $H$, when does there exist a crossing-critical graph $G$ that is obtained by multiplying edges of $H$? \end{question} %More formally, let us say that graph $\overline{G}$ is a {\em multiplication} of %graph $G$ if $G$ is a subgraph of $\overline{G}$, and for every edge $e$ %of $\overline{G}$ there is an edge of $G$ with the same endpoints as %$e$. With this terminology, Question~\ref{question1} becomes: Our universe of interest is, of course, the set of nonplanar graphs, since a planar graph obviously remains planar after multiplying any or all of its edges. \subsection{Main result}\label{sub:main} We show that a large, interesting family of nonplanar graphs satisfy the property in Question~\ref{question1}. A nonplanar graph $G$ is {\em near-planar} if it has an edge $e$ such that $G-e$ is planar. Near-planar graphs constitute a natural family of nonplanar graphs. Any thought to the effect that crossing number problems might become easy when restricted to near-planar graphs is put definitely to rest by the recent proof by Cabello and Mohar that {\sc CrossingNumber} is NP-Hard for near-planar graphs~\cite{cabellomohar1}. A graph $G$ is \emph{internally $3$-connected} if $G$ is simple and $2$-connected, and for every separation $(G_1, G_2)$ of $G$ of order two, either $|E(G_1)| \leq 2$ or $|E(G_2)| \leq 2$. Hence, internally $3$-connected graphs are those that can be obtained from a $3$-connected graph by subdividing its edges, with the condition that no edge can be subdivided more than once. We recall that a graph is {\em polyhedral} if it is planar and $3$-connected~\cite{riskin}. Our main result is that any adequately connected, near-planar graph $G$ obtained by adding an edge to a cubic polyhedral graph, belongs to the class alluded to in Question~\ref{question1}. Throughout this paper, if $G$ is a graph with vertices $u,v$ such that the edge $uv$ is in $G$, then $G-uv$ is the graph that results by removing the edge $uv$ from $G$, and $G-\{u,v\}$ is the graph that results by removing both $u$ and $v$ (as well as their incident edges) from $G$. \begin{theorem}\label{thm:maintheorem} Let $G$ be a near-planar simple graph, with an edge $uv$ such that $G-uv$ is a cubic polyhedral graph. Suppose that $G -\{u,v\}$ is internally $3$-connected. Then there exists a crossing-critical graph that is obtained by multiplying edges of $G$. \end{theorem} %%% REMOVE reference to ``e'' (edge) wherever possible. So I can use %%% the dummy ``e'' in proofs. %%% Really NEED simple?? We note that some connectivity assumption is needed in order to guarantee that a nonplanar graph can be made crossing-critical by multiplying edges. To see this, consider a graph $G$ which is the union of two subgraphs $G_1, G_2$, where $G_1$ is nonplanar and $G_2$ is planar with at least one edge, and $G_1$ and $G_2$ have exactly one vertex in common. Since crossing number is additive on the blocks of a graph, it is easy to see that $G$ (more specifically, the edges of $G_2$) cannot be made crossing-critical by multiplying edges. \subsection{Reformulating Theorem~\ref{thm:maintheorem} in terms of weighted graphs}\label{sub:ref} We recall that a {\em weighted graph} is a pair $(G,\wa)$, where $G$ is a graph and $\wa$ (the {\em weight assignment}) is a map that assigns to each edge $e$ of $G$ a number $\wa(e)$, the {\em weight} of $e$. The {\em length} of a path in a weighted graph is the sum of the weights of the edges in the path. If $u,v$ are vertices of $G$, then the {\em distance} $d_{\wa}(u,v)$ {\em from $u$ to $v$} ({\em under $\wa$}) is the length of a minimum length (also called a {\em shortest}) {$uv$-path}. The weight assignment $\wa$ is {\em positive} if $\wa(e) >0$ for every edge $e$ of $G$, and it is {\em integer} if each $\wa(e)$ is an integer. In the context of Theorem~\ref{thm:maintheorem}, let $G$ be a simple graph which we seek to make crossing-critical by multiplying (some or all of) its edges. With this in mind, let $\overline{G}$ be a multigraph (that is, a graph with multiedges allowed) whose underlying simple graph is $G$. Now consider the (positive integer) weight assignment $\wa$ on $E(G)$ defined as follows: for each edge $uv$ of $G$, let $\wa(uv)$ be the number of edges in $\overline{G}$ whose endpoints are $u$ and $v$ (i.e., the {\em multiplicity} of $uv$). If we extend the definition of crossing number to weighted graphs, with the condition that a crossing between two edges contributes to the total crossing number by the product of their weights, then, from the crossing number point of view, clearly $(G,\wa)$ captures all the relevant information from $\overline{G}$. In particular, $\cro(\overline{G})= \cro(G,\wa)$. Moreover, by extending the definition of crossing-criticality to weighted graphs in the obvious way (which we now proceed to do), it will follow that $\overline{G}$ is crossing-critical if and only if $(G,\wa)$ is crossing-critical. To this end, let $G$ be a graph and $\wa$ a positive integral weight assignment on $G$. An edge $e$ of $(G,\wa)$ is {\em crossing-critical} if $\cro(G,\wa_e) < \cro(G,\wa)$, where $\wa_e$ is the weight assignment defined by $\wa_e(f) = \wa(f)$ for $f\neq e$ and $\wa_e(e) = \wa(e)-1$. As with ordinary graphs, $(G,\wa)$ is {\em crossing-critical} if all its edges are crossing-critical. Under this definition of crossing-criticality for weighted graphs, it is now obvious that if we start with a multigraph $\overline{G}$ and derive its associated weighted graph $(G,\wa)$ as above, then $\overline{G}$ is crossing-critical if and only if $(G,\wa)$ is crossing-critical. In view of this equivalence (for crossing number purposes) between multigraphs and weighted graphs, it follows that Theorem~\ref{thm:maintheorem} is equivalent to the following: \begin{theorem}[{\bf Equivalent to Theorem~\ref{thm:maintheorem}}]\label{thm:maintheorem2} Let $G$ be a near-planar simple graph, with an edge $uv$ such that $G-uv$ is a cubic polyhedral graph. Suppose that $G -\{u,v\}$ is internally $3$-connected. Then there exists a positive integer weight assignment $\wa$ such that $(G,\wa)$ is crossing-critical. \end{theorem} %\subsection{Structure of the rest of this paper}\label{sub:rest} The next section is devoted to the proof of Theorem~\ref{thm:maintheorem2}, and Section~\ref{sec:concludingremarks} contains some concluding remarks and open questions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of Theorem~\ref{thm:maintheorem2}}\label{sec:proofmain2} Throughout this proof, $G$ is a graph that satisfies the hypotheses of Theorem~\ref{thm:maintheorem2}. That is, $G$ is near-planar and simple, and has an edge $uv$ such that $G-uv$ is a cubic polyhedral graph and $\gde:=\gmuv$ is internally $3$-connected. We let $u_1, u_2,$ and $u_3$ be the vertices of $G$ (other than $v$) adjacent to $u$. Analogously, we let $v_1, v_2,$ and $v_3$ be the vertices of $G$ (other than $u$) adjacent to $v$. To help comprehension, we break the proof into several subsections. \subsection{Basic observations and facts about \texorpdfstring{$G$}{G}, \texorpdfstring{$\gde$}{Gu,v}, and \texorpdfstring{$G-uv$}{G-uv}}\label{sub:lay} We start with an observation that follows from the connectivity properties of $G-uv$ and $\gde$. \begin{remark}\label{rem:uni} Both $G-uv$ and $\gde$ admit unique (up to homeomorphism) embeddings in the plane. This allows us, for the rest of the proof, to regard these as graphs embedded in the plane. Moreover, since $\gde$ is a subgraph of $G-uv$, it follows that we may assume that the restriction of the embedding of $G-uv$ to $\gde$ is precisely the embedding of $\gde$. \end{remark} \begin{proposition}\label{pro:dist} $u_1, u_2, u_3, v_1, v_2, v_3$ are all distinct. \end{proposition} \begin{proof} Since $G$ is simple, it follows that $u_1,u_2$, and $u_3$ are all distinct. Similarly, $v_1, v_2$, and $v_3$ are all distinct. Now suppose that $u_i=v_j$ for some $i,j\in\{1,2,3\}$, and consider an embedding of $G-uv$ in the plane. It is easy to see that since $u_i=v_j$, and $G-uv$ is cubic, it follows that $uv$ can be added to the embedding of $G-uv$ without introducing any crossings, resulting in an embedding of $G$. This contradicts the nonplanarity of $G$. Thus $u_i\neq v_j$ for all $i,j\in \{1,2,3\}$. \end{proof} \begin{proposition}\label{pro:apro} In $\gde$ there is a unique face $F_u$ (respectively, $F_v$) incident with $u_1,u_2,$ and $u_3$ (respectively, $v_1, v_2$, and $v_3$). Moreover, $F_u\neq F_v$. \end{proposition} \begin{proof} The existence of a face $F_u$ in $\gde$ incident with $u_1,u_2$, and $u_3$ follows since $G-uv$ is planar. Since $u_1, u_2$, and $u_3$ are all distinct, and $G-uv$ is cubic, it follows that $u_1,u_2,$ and $u_3$ all have degree $2$ in $\gde$. The internal $3$-connectivity of $\gde$ implies that no two $u_i$s can be adjacent to each other. This implies that there cannot be two distinct faces of $\gde$ incident with more than one $u_i$, and, in particular, that $F_u$ is unique. An identical argument shows that $F_v$ exists and is unique. To see that $F_u\neq F_v$, it suffices to note that if $F_u=F_v$ then the edge $uv$ could be added to the embedding of $G-uv$ without introducing any crossings, resulting in an embedding of $G$, contradicting its nonplanarity. \end{proof} The previous three statements immediately imply the following. \begin{observation} To obtain the embedding of $G-uv$, we start with the embedding of $\gde$, and then draw $u u_1, u u_2$, and $u u_3$ (and, of course, $u$) inside $F_u$, and $v v_1, v v_2$, and $v v_3$ (and, of course, $v$) inside $F_v$. \end{observation} \subsection{Weight assignments on the dual \texorpdfstring{$\gd$}{G*uv} of \texorpdfstring{$\gde$}{Guv}}\label{sub:wei} We shall make extensive use of weight assignments on the dual (embedded graph) $\gd$ of $\gde$. We start by noting that $\gd$ is well-defined (and admits a unique plane embedding) since $\gde$ admits a unique plane embedding. As with $G-uv$ and $\gde$, this allows us to unambiguously regard $\gd$ as an embedded graph. We shall let $\ff$ denote the set of all faces in $\gde$ (equivalently, the set of all vertices of $\gd$). A weight assignment $\wuv$ on $\gde$ naturally induces a weight assignment $\wuvd$ on $\gd$, and vice versa: if $e$ is an edge of $\gde$ and $e^*$ is its dual edge in $\gd$, then we simply let $\wuvd(e^*)= \wuv(e)$. Trivially, a weight assignment $\w$ on the whole graph $G$ also naturally induces a weight assignment $\wuvd$ on $\gd$: it suffices to consider the restriction $\wuv$ of $\w$ to $\gde$, and from this we obtain $\wuvd$ as we just described. %If $\wuvd$ is a weight assignment on $\gd$, then for $F,F'\in\ff$ we let $d_{\wuvd}(F,F')$ denote the length of a shortest $FF'$-path in $\gd$ under $\wuvd$. We call $d_{\wuvd}(F,F')$ the {\em distance} between $F$ and $F'$ under $\wuvd$. \begin{definition} A weight assignment $\wuvd$ on $\gd$ is {\em balanced} if each edge $e^*$ of $\gd$ belongs to a shortest $F_uF_v$-path in $(\gd,\wuvd)$. \end{definition} %\marginpar{\tiny I prefer $F^u$ instead of $F_u$, etc.} Now since for $i=1,2,3$ the vertex $u_i$ has degree $2$ in $\gde$, it follows that $u_i$ is incident with exactly two faces in $\gde$, one of which is $F_u$; let $F_{u_i}$ denote the other face. Thus it makes sense to define the {\em distance} $d_{\wuvd}(u_i,F)$ between $u_i$ and any face $F\in\ff$ as $\min\{d_\wuvd(F_u,F),d_\wuvd(F_{u_i},F)\}$. We define $F_{v_i}$ and $d_{\wuvd}(v_i,F)$ analogously, for $i=1,2,3$. We note that possibly $F_{u_i} = F_v$ for some $i\in\{1,2, 3\}$, or $F_{v_j} = F_u$ for some $j\in\{1, 2, 3\}$. On the other hand, we have the following. \begin{proposition}\label{pro:someobs} $F_{u_1}, F_{u_2}$ and $F_{u_3}$ are all distinct. Similarly, $F_{v_1}, F_{v_2}$ and $F_{v_3}$ are all distinct. \end{proposition} \begin{proof} As observed in the proof of Proposition~\ref{pro:apro}, the internal $3$-connectivity of $\gde$ implies that no two $u_i$s can be adjacent to each other, and so there cannot be two distinct faces of $\gde$ incident with more than one $u_i$. Since $F_u$ is incident with $u_1,u_2$, and $u_3$, it follows that $F_{u_1}, F_{u_2}$, and $F_{u_3}$ are all distinct. An identical argument shows that $F_{v_1}, F_{v_2}$ and $F_{v_3}$ are all distinct. \end{proof} %If $\wuvd$ is balanced, we also say that its induced weight %assignment $\wuv$ on $\gde$ is {\em balanced}. Moreover, if $\wuv$ is %balanced, and $\w$ is an extension of $\wuv$, we also say that $\w$ %is {\em balanced}. % ************************************************************* %Consider $G-\{u,v\}$ embedded in the plane. An $F_uF_v$-{\em arc} is %an open arc (that is, a homeomorphic image of $[0,1]$ in the plane) %with an endpoint in $F_u$ and the other endpoint in $F_v$. \subsection{Strategy of the rest of the proof} Although the core of the proof of Theorem~\ref{thm:maintheorem2} is somewhat technical, the main ideas behind it are not difficult to explain. Our aim in this subsection is to give an informal account of the strategy behind the proof. This will also give us the opportunity to motivate the introduction of five properties (namely (P1)--(P5) below) that a weight assignment $\omega$ would need to satisfy (in our strategy) for $(G,\omega)$ to be crossing-critical. We will finish this subsection by formally stating (i) that if $\omega$ satisfies (P1)--(P5), then $(G,\omega)$ is indeed crossing-critical (Lemma~\ref{lem:ifthere}); and (ii) the existence of an $\omega$ that satisfies (P1)--(P5) (Lemma~\ref{lem:thereis}). Theorem~\ref{thm:maintheorem2} will obviously follow from these lemmas, which will be proved in Subsections~\ref{sub:ifthere} and~\ref{sub:thereis}, respectively. %\marginpar{$w$ or $\omega$} We seek a weight assignment $\omega$ such that in every optimal drawing of $(G,\omega)$, the induced drawing of $\gde$ is its unique (see Remark~\ref{rem:uni}) embedding. Moreover, we wish to adjust the weights of the edges so that if we start with $\gde$ and then draw $u$ inside $F_u$ and $v$ inside $F_v$, and finally add $uv$ following a shortest $F_uF_v$-path in $(\gde^*,\omega^*)$, the resulting drawing is optimal. Since such a drawing will have $\omega(uv)\cdot d_{\omega^*}(F_u,F_v)$ crossings, the aim is to have cr$(G,\omega)=\omega(uv)\cdot d_{\omega^*}(F_u,F_v)$. To ensure that in every optimal drawing of $(G,\omega)$ the induced drawing of $\gde$ is an embedding, we need to discourage crossings among edges in $\gde$ in every optimal drawing of $(G,\omega)$. This is achieved by assigning large weights to the edges of $\gde$, as captured by the following property: \begin{description} \item{(P1)} For every pair of edges $e,e'$ of $\gde$, $\omega(e) \omega(e') > \omega(uv)\cdot d_{\omega^*}(F_u,F_v) $. \end{description} Now in order to guarantee that the described way of drawing $G$ (adding $uv$ as explained) will be best possible, we need to make sure that if we place $u$ (respectively, $v$) in a face other than $F_u$ (respectively, $F_v$), and then add $uv$ in the most economical way, then the resulting drawing will not have fewer than $\omega(uv)\cdot d_{\omega^*}(F_u,F_v)$ crossings. In order to achieve this, we need to make the weights of the edges $uu_1, uu_2, uu_3, vv_1, vv_2, vv_3$ large enough, so that if we place $u$ (respectively, $v$) in a face other than $F_u$ (respectively, $F_v$), we introduce a large enough number of crossings with the edges incident with $u$. This is captured by the next property: \begin{description} \item{(P2)} For each $x\in\{u,v\}$ and each $F\in\ff$, \begin{center} $\omega(xx_1)\cdot d_{\omega^*}(x_1,F) + \omega(xx_2) \cdot d_{\omega^*}(x_2,F) + \omega(xx_3) \cdot d_{\omega^*}(x_3,F) \ge \omega(uv) \cdot d_{\omega^*}(F_x,F)$ \end{center} \end{description} The conditions explained so far are quite easy to accomplish: it suffices to make the weights of all the edges other than $uv$ very large compared to $\omega(uv)$. The difficulty lies on the fine-tuning of these weights in order to guarantee the criticality of every edge. The criticality of the edges of $\gmuv$ is forced by asking $\omega^*$ to be balanced: \begin{description} \item{(P3)} The dual weight assignment $\omega^*$ on $\gd$ induced by $\omega$ is balanced. \end{description} Indeed, this balancedness guarantees that if we choose any edge $e\in \gde$, then we can draw $u$ on $F_u$ and $v$ on $F_v$, and then add $uv$ in a most economical way so that $uv$ crosses $e$; since $e$ gets crossed in an optimal drawing of $G$, then $e$ is obviously critical. The criticality of the edges $uu_1,uu_2,uu_3,vv_1,vv_2,vv_3$ is a little bit harder to achieve. Consider an edge $uu_i$ (the situation is identical for an edge $vv_j$). Our strategy to ensure the criticality of $uu_i$ is to ask that there exist a face $U_i\in\ff$ not incident with $u_i$, such that we can place $u$ in $U_i$ and join it to $u_1,u_2$ and $u_3$ with a cost (in crossings) equal to the cost of reaching $U_i$ from $F_u$ (with a weight $w(uv)$). The upshot is that, since $u_i$ is not incident with $U_i$, we find an alternative way to join $u$ and $v$ by placing $u$ in the face $U_i$, and in this alternative way $uu_i$ gets crossed, thus guaranteeing its criticality. This gets captured by the following property: \begin{description} \item{(P4)} For each $(x,X)\in \{(u,U),(v,V)\}$ and each $i=1, 2, 3$, there is a face $X_i\in\ff$ such that $d_{\omega^*}(x_i,X_i)>0$ and \begin{center} $ \omega(xx_1) \cdot d_{\omega^*}(x_1,X_i) + \omega(xx_2)\cdot d_{\omega^*}(x_2,X_i) + \omega(xx_3) \cdot d_{\omega^*}(x_3, X_i) = \omega(uv)\cdot d_{\omega^*}(F_x,X_i) $. \end{center} \end{description} Now the caveat in this attempt to make $uu_i$ critical is that since $u$ gets drawn outside $F_u$, we may introduce crossings involving one edge in $\{uu_1,uu_2,uu_3\}$ and one edge in $\{vv_1,vv_2,vv_3\}$; if such crossings get introduced, then the resulting drawing is not optimal. With the aim of fixing this, we identify a property to ensure that any such crossings, if introduced, are negligible compared to the weight of any edge in $\gde$: \begin{description} \item{(P5)} For all $i,j\in\{1,2,3\}$, $ \omega(uu_i) \cdot \omega(vv_j) < (1/9) \min\{\ \omega(e) \ | \ e \in E(\gde)\}. $ \end{description} Throughout this informal discussion, we have identified the properties that we want to be satisfied by $\omega$. Getting back to the formal setting, our task is then to establish the following two statements: \begin{lemma}\label{lem:ifthere} Suppose that $\omega$ is a positive integer weight assignment on $G$ satisfying (P1)--(P5). Then $(G,\omega)$ is crossing-critical. \end{lemma} \begin{lemma}\label{lem:thereis} There exists a positive integer weight assignment $\omega$ on $G$ that satisfies (P1)--(P5). \end{lemma} The proofs of these statements, whose combination obviously finishes the proof of Theorem~\ref{thm:maintheorem2}, are given in Subsections~\ref{sub:ifthere} and~\ref{sub:thereis}, respectively. \subsection{Proof of Lemma~\ref{lem:ifthere}}\label{sub:ifthere} % ************************************************************* % ************************************************************* Throughout the proof, for brevity we let $t:=\omega(uv)$. To help comprehension, we break the proof into several steps. \bigskip \noindent{(A) } {\em $\cro(G,\omega) \le t\cdot d_{\omega^*}(F_u,F_v)$. } \bigskip Start with the (unique) embedding of $G-uv$, and draw $uv$ following a shortest $F_uF_v$-path in $(\gd,\omega^*)$. Then the sum of the weights of the edges crossed by $uv$ equals the total weight of the shortest $F_uF_v$-path, that is, $d_{\omega^*}(F_u,F_v)$ (here we use the elementary, easy to check fact that crossings between adjacent edges can always be avoided; in this case, we may draw $uv$ so that it crosses no edge adjacent to $u$ or $v$). Since $\omega(uv)=t$, it follows that such a drawing of $(G,\omega)$ has exactly $t\cdot d_{\omega^*}(F_u,F_v)$ crossings. \bigskip \noindent{(B) } {\em $\cro(G,\omega) = t\cdot d_{\omega^*}(F_u,F_v)$. } \bigskip Consider a crossing-minimal drawing $\dd$ of $(G,\omega)$. An immediate consequence of (P1) and (A) is that the drawing of $\gde$ induced by $\dd$ is an embedding (that is, no two edges of $\gde$ cross each other in $\dd$). Now let $F'$ (respectively, $F''$) denote the face of $\gde$ in which $u$ (respectively, $v$) is drawn in $\dd$. Clearly, for $i=1,2,3$ the edge $uu_i$ contributes at least $\omega(uu_i)\cdot d_{\omega^*}(u_i,F')$ crossings. Analogously, for $i=1,2,3$ the edge $vv_i$ contributes at least $\omega(vv_i)\cdot d_{\omega^*}(v_i,F'')$ crossings. Thus it follows from (P2) that the edges in $\{uu_1, uu_2, uu_3, vv_1, vv_2, vv_3\}$ contribute at least $t\cdot d_{\omega^*}(F_u,F') + t\cdot d_{\omega^*}(F_v,F'') = t\cdot (d_{\omega^*}(F_u,F') + d_{\omega^*}(F_v,F''))$ crossings. On the other hand, since the ends $u,v$ of $uv$ are in faces $F'$ and $F''$, it follows that edge $uv$ contributes at least $t\cdot d_{\omega^*}(F',F'')$ crossings. We conclude that $\dd$ has at least $t\cdot \bigl( d_{\omega^*}(F_u,F') + d_{\omega^*}(F_v,F'') + d_{\omega^*}(F',F'')\bigr)$ crossings. Elementary triangle inequality arguments show that $d_{\omega^*}(F_u,F') + d_{\omega^*}(F_v,F'') + d_{\omega^*}(F',F'') \ge d_{\omega^*}(F_u,F_v)$, and so $\dd$ has at least $t\cdot d_{\omega^*}(F_u,F_v)$ crossings. Thus $\cro(G,\omega) \ge t\cdot d_{\omega^*}(F_u,F_v)$. The reverse inequality is given in (A), and so (B) follows. \bigskip \noindent{(C) } {\em Crossing-criticality of the edges in $\gde$ and of the edge $uv$.} \bigskip Let $e$ be any edge in $\gde$. We proceed similarly as in (A). Start with the (unique) embedding of $G-uv$, and draw $uv$ following a shortest $F_uF_v$-path in $(\gd,\omega^*)$ that includes $e^*$ (the existence of such a path is guaranteed by the balancedness of $\omega^*$). This yields a drawing of $(G,\omega)$ with exactly $t\cdot d_{\omega^*}(F_u,F_v)$ crossings, in which $e$ and $uv$ cross each other. Since $\cro(G,\omega) = t\cdot d_{\omega^*}(F_u,F_v)$, it follows that $e$ and $uv$ are both crossed in a crossing-minimal drawing of $(G,\omega)$. Therefore both $e$ and $uv$ are crossing-critical in $(G,\omega)$. \bigskip \noindent{(D) } {\em Crossing-criticality of the edges $uu_1, uu_2, uu_3, vv_1, vv_2$, and $vv_3$.} \bigskip We prove the criticality of $uu_1$; the proof of the criticality of the other edges is totally analogous. Consider the (unique) embedding of $\gde$. Put $u$ in face $U_1$ (see property (P4)) and $v$ in face $F_v$. Then draw $uu_j$, for $j=1,2,3$, adding $\omega(uu_j)\cdot d_{\omega^*} (u_j,U_1)$ crossings with the edges in $\gde$. Since crossings between adjacent edges can always be avoided, it follows that $uu_1, uu_2, uu_3$ get drawn by adding $ \omega(uu_1)\cdot d_{\omega^*} (u_1,U_1) + \omega(uu_2)\cdot d_{\omega^*} (u_2,U_1) + \omega(uu_3)\cdot d_{\omega^*} (u_3,U_1) = t\cdot d_{\omega^*}(F_u,U_1) $ crossings (using (P4)). Finally we draw $vv_1, vv_2, vv_3$ in face $F_v$. Now this last step may add crossings, but only of the edges $vv_1, vv_2, vv_3$ with the edges $uu_1, uu_2, uu_3$. In view of (P5), the last step added fewer than $9\cdot(1/9) \min\{\ \omega(e) \ | \ e \in E(\gde)\} = \min\{\ \omega(e) \ | \ e \in E(\gde)\}$ crossings. We finally draw $uv$; since $u$ is in face $U_1$ and $v$ is in face $F_v$, it follows that $uv$ can be drawn by adding $t \cdot d_{\omega^*}(U_1,F_v)$ crossings. The described drawing $\dd$ of $G$ has then fewer than $t\cdot d_{\omega^*}(F_u,U_1) + t \cdot d_{\omega^*}(U_1,F_v) + \min\{\ \omega(e) \ | \ e \in E(\gde)\} = t\cdot d_{\omega^*}(F_u,F_v) + \min\{\ \omega(e) \ | \ e \in E(\gde)\} = \cro(G,\omega) + \min\{\ \omega(e) \ | \ e \in E(\gde)\}$ crossings, where for the first equality we used the balancedness of $\omega^*$, and for the second equality we used (B). Thus $\cro(\dd) < \cro(G,\omega) + \min\{\ \omega(e) \ | \ e \in E(\gde)\}$. In $\dd$, one weight unit of $uu_1$ contributes $d_{\omega^*} (u_1,U_1)$ crossings, and so $uu_1$ contributes $\omega(uu_1)\cdot d_{\omega^*} (u_1,U_1)$ crossings; note that (P4) implies that $\omega(uu_1)\cdot d_{\omega^*} (u_1,U_1)>0$. Since obviously $d_{\omega^*} (u_1,U_1)\ge \min\{\omega(e) \ | \ e \in E(\gde)\}$, it follows that one weight unit of $uu_1$ contributes at least $\min\{\omega(e) \ | \ e \in E(\gde)\}$ crossings. Thus, if we decrease the weight of $uu_1$ by $1$, then we obtain a drawing of $G-uu_1$ with fewer than $\cro(G,\omega)$ crossings. Therefore $uu_1$ is critical in $(G,\omega)$, as claimed. \hfill{$\qed$} % ************************************************************* % ************************************************************* \subsection{Proof of Lemma~\ref{lem:thereis}}\label{sub:thereis} %, and {\em rational} is each $w(e)$ is a rational number. %, and it is {\em integer} if $w(e)$ is always an integer. An important ingredient in the proof of Lemma~\ref{lem:thereis} is the following, somewhat curious statement for which we could not find any reference in the literature. \begin{proposition}\label{pro:aux} Let $G$ be a $2$-connected loopless graph, and let $u,v$ be distinct vertices of % ``DISTINCT'' is new. OK to assume it? Loops, what bothers me. $G$. Then there is a positive integer %%% CHECK THE PROOF IS ALSO RATIONAL %integer weight assignment $\mu$ %on the edges of $G$ such that every edge of $(G,\mu)$ belongs to a shortest $uv$-path. \end{proposition} \begin{proof} We make use of $st$-numberings~\cite{lempel}. We recall that if $H$ is a graph with vertex set $V$ and $st$ is an edge of $H$, then an $st$-{\em numbering} of $H$ is a bijection $g:V\to\{1,2,\ldots,|V|\}$ such that $g(s)=1, g(t)=|V|$, and for every $v\in V\setminus\{s,t\}$ there are edges $xv$ and $vy$ such that $g(x) < g(v) < g(y)$. It is known that if $s,t$ is any pair of adjacent vertices in a $2$-connected graph, then there is an $st$-numbering of $H$. Now let $G,u,v$ be as in the statement of the proposition, and let $n:=|V(G)|$. It is easy to see that if $u$ and $v$ are not adjacent and the proposition holds for $G+uv$, then it also holds for $G$. Thus we may assume that $u$ and $v$ are adjacent. Let $g$ be a $uv$-numbering on $G$, and let $\mu$ be the weight assignment defined as follows: for each edge $xy$ of $G$, let $\mu(xy)=|g(x)-g(y)|$. It is straightforward to check that a $\mu$-shortest $uv$-path in $(G,\mu)$ has length $n-1$, and that every edge in $G$ belongs to a $\mu$-shortest $uv$-path. \end{proof} \bigskip \begin{proof}[Proof of Lemma~\ref{lem:thereis}] We start with a balanced positive integer weight assignment $\mu^*$ on $\gd$. The existence of such a $\mu^*$ is guaranteed by Proposition~\ref{pro:aux}, which applies since the connectivity assumption on $\gde$ implies that $\gd$ is also $3$-connected. Let $\mu$ denote the (also positive integer) weight assignment naturally induced on $\gde$. % ***************************************************************** % ***************************************************************** % ***************************************************************** For each face $F\in\ff\setminus\{F_u\}$, we let $\half{F}{u}$ denote the halfspace defined by $d_{\mu^*}(u_1,F)x_1 + d_{\mu^*}(u_2,F)x_2 + d_{\mu^*}(u_3,F)x_3 \ge d_{\mu^*}(F_u,F)$, and let $\plane{F}{u}$ denote its supporting plane. Let $\pp_u$ denote the polyhedron defined by the (intersection of the) set of halfspaces $\{\half{F}{u} \,|\, F\in\ff\setminus\{F_u\}\}$ and the nonnegative octant $\{(x_1,x_2,x_3) \ | \ x_1\ge 0, x_2\ge 0, x_3\ge 0\}$. It is clear that if $x_1, x_2$, and $x_3$ are all large enough then $(x_1, x_2, x_3)$ is in $\pp_u$, and so $\pp_u$ is not empty. \vglue 0.5 cm \noindent{\bf Claim I. } {\em There is a strictly positive rational point $(x_1,x_2,x_3)$ in $\pp_u$ that belongs to (not nec\-es\-sarily distinct) supporting planes $\plane{U_1}{u}$, $\plane{U_2}{u}$, $\plane{U_3}{u}$, such that for $i=1,2,3$ we have $d_{\mu^*}(u_i,U_i)>0$. } \vglue 0.5 cm %%% (and therefore is in the boundary of $\pp_u$), \begin{proof} Suppose first that there is an $F\in\ff\setminus\{F_u,F_{u_1},F_{u_2},F_{u_3}\}$ such that a facet of $\pp_u$ is in $\plane{F}{u}$. Since $F\in\ff\setminus\{F_u,F_{u_1},F_{u_2},F_{u_3}\}$, then $d_{\mu^*}(u_i,F) > 0$ for $i=1,2,3$. Thus the plane $\plane{F}{u}$ intersects each of the coordinate axes in a positive coordinate, and so it follows that $\plane{F}{u}$ (more specifically, the facet of $\pp_u$ contained in $\plane{F}{u}$) has a positive rational point $(x_1,x_2,x_3)$ that satisfies the claim, with $U_1=U_2=U_3=F$. Suppose finally that there is no such $F\in\ff\setminus\{F_u,F_{u_1},F_{u_2},F_{u_3}\}$. Since for $i,j\in\{1,2,3\}$ we have $d_{\mu^*} (u_i,F_{u_j})\ge 0$, where equality holds if and only if $i=j$, it follows that for each $i\in\{1,2,3\}$ the plane $\plane{F_{u_i}}{u}$ is parallel to the $i$-th coordinate axis, and intersects each of the other two axes in strictly positive points. It then follows from elementary convex geometry arguments that there exists a strictly positive rational point $(x_1,x_2,x_3)$ contained in $\plane{F_{u_1}}{u}\cap \plane{F_{u_2}}{u}\cap \plane{F_{u_3}}{u}$. Since no facet of $\pp_u$ is in $\plane{F}{u}$ for any $F\in\ff\setminus\{F_u,F_{u_1},F_{u_2},F_{u_3}\}$, it follows that $(x_1,x_2,x_3)$ is in $\pp_u$. \end{proof} Analogously, for each face $F\in\ff\setminus\{F_v\}$, we let $\half{F}{v}$ denote the halfspace defined by $d_{\mu^*}(v_1,F)y_1 + d_{\mu^*}(v_2,F)y_2 + d_{\mu^*}(v_3,F)y_3 \ge d_{\mu^*}(F_v,F)$, and let $\plane{F}{v}$ denote its supporting plane. Similarly, let $\pp_v$ denote the polyhedron defined by the (intersection of the) set of halfspaces $\{\half{F}{v} \,|\, F\in\ff\setminus\{F_v\}\}$ and the nonnegative octant $\{(y_1,y_2,y_3) \ | \ y_1\ge 0, y_2\ge 0, y_3\ge 0\}$. The proof of the following statement is totally analogous to the proof of Claim I: \vglue 0.5 cm \noindent{\bf Claim II. } {\em There is a strictly positive rational point $(y_1,y_2,y_3)$ in $\pp_v$ that belongs to (not nec\-es\-sarily distinct) supporting planes $\plane{V_1}{v}$, $\plane{V_2}{v}$, $\plane{V_3}{v}$, such that for $i=1,2,3$ we have $d_{\mu^*}(v_i,V_i)>0$. } \hfill \qed \vglue 0.5 cm Let $(p_1/q_1, p_2/q_2, p_3/q_3)$ be a point as in Claim I, and let $(a_1/b_1, a_2/b_2, a_3/b_3)$ be a point as in Claim II, where all $p_i$s, $q_i$s, $a_i$s, and $b_i$s are integers. Let $M:=q_1q_2q_3b_1b_2b_3$, and let $r_1:=p_1q_2q_3b_1b_2b_3, r_2:=p_2q_1q_3b_1b_2b_3$, $r_3:=p_3 q_1 q_2b_1b_2b_3$, $s_1:=a_1b_2b_3q_1q_2q_3, s_2:=a_2b_1b_3q_1q_2q_3$, and $s_3:=a_3 b_1 b_2q_1q_2q_3$. Then $(r_1, r_2, r_3)$ is a positive integer solution to the set of inequalities $\{d_{\mu^*}(u_1,F)r_1 + d_{\mu^*}(u_2,F)r_2 + d_{\mu^*}(u_3,F)r_3 \ge M\cdot d_{\mu^*}(F_u,F) : F\in\ff\setminus\{F_u\}\}$, and for each $i=1,2,3$, we have $d_{\mu^*}(u_1,U_i)r_1 + d_{\mu^*}(u_2,U_i)r_2 + d_{\mu^*}(u_3,U_i)r_3 = M\cdot d_{\mu^*}(F_u,U_i)$. Similarly, $(s_1, s_2, s_3)$ is a positive integer solution to the set of inequalities $\{d_{\mu^*}(v_1,F)s_1 + d_{\mu^*}(v_2,F)s_2 + d_{\mu^*}(v_3,F)s_3 \ge M\cdot d_{\mu^*}(F_v,F) : F\in\ff\setminus\{F_v\}\}$, and for each $i=1,2,3$, we have $d_{\mu^*}(v_1,V_i)s_1 + d_{\mu^*}(v_2,V_i)s_2 + d_{\mu^*}(v_3,V_i)s_3 = M\cdot d_{\mu^*}(F_v,V_i)$. Finally, let $c$ be any integer greater than $ M\cdot d_{\mu^*}(F_u,F_v)/(\min\{\mu(e)\ | \ e\in E(\gde)\})^2 $ and also greater than $ 9r_i s_j/\min\{\mu(e)\ | \ e\in E(\gde)\} %\min\{\mu^*(e^*)\ | \ e^*\in \gd \} $, for all $i,j \in\{1,2,3\}$. %\marginpar{\tiny CAREFUL: use $e^*$ for edges in $\gd$ and $e$ for % edges in $\gde$ --- be consistent.} %\marginpar{\tiny ALSO: use ``edge in $E(G)$'' OR ``edge in $G$'', but % not both --- be consistent.} Define the weight assignment $\omega$ on $G$ as follows: \begin{itemize} \item $\omega(uv) = M$; \item $\omega(uu_i)=r_i$ and $\omega(vv_i)=s_i$ for $i=1,2,3$; \item $\omega(e) = c\cdot \mu(e)$, for all edges $e$ in $\gde$. \end{itemize} We finish the proof by showing that $\omega$ (and its induced weight assignment $\omega^*$ on $\gd$) satisfies (P1)--(P5). To see that $\omega^*$ satisfies (P3), it suffices to note that $\omega^*$ inherits the balancedness (when restricted to $\gd$) from $\mu^*$. Now let $e,e'$ be edges of $\gde$. Then $ \omega(e) \omega(e') = c^2\cdot \mu(e)\mu(e') \ge c^2\cdot (\min\{ \mu(f)\ | \ f\in E(\gde)\ \})^2 > c\cdot M \cdot d_{\mu^*}(F_u,F_v) = \omega(uv)(c\cdot d_{\mu^*}(F_u,F_v)) = \omega(uv)\cdot d_{\omega^*} (F_u,F_v)$. This proves (P1). % * %Now Recall that $(r_1, r_2, r_3)$ is a positive integer solution to the set of inequalities $\{d_{\mu^*}(u_1,F)r_1$ $+ d_{\mu^*}(u_2,F)r_2 + d_{\mu^*}(u_3,F)r_3 \ge M\cdot d_{\mu^*}(F_u,F) : F\in\ff\setminus\{F_u\}\}$, and for each $i=1,2,3$, we have $d_{\mu^*}(u_1,U_i)r_1 + d_{\mu^*}(u_2,U_i)r_2 + d_{\mu^*}(u_3,U_i)r_3 = M\cdot d_{\mu^*}(F_u,U_i)$. Noting that for any faces $F,F'\in\ff\setminus\{F_u\}$, $d_{\omega^*}(F,F') = c\cdot d_{\mu^*}(F,F')$, and using the definition of $\omega$ (and its induced $\omega^*$), we immediately obtain (P2) (when $x=u$) and (P4) (when $(x,X)=(u,U)$). The proof of (P2) for the case $x=v$ and the proof of (P4) for the case $(x,X)=(v,V)$ are totally analogous. Finally, we recall that we defined $c$ so that $ c > 9r_i s_j/\min\{\mu(e)\ | \ e\in E(\gde) \} $ for all $i,j \in\{1,2,3\}$. By the definition of $\omega$, this is equivalent to $ c\cdot \min\{\mu(e) \ | \ e\in E(\gde) \} > 9\omega(uu_i)\omega(vv_j) $, that is, $ \min\{\omega(e) \ | \ e\in E(\gde) \} > 9\omega(uu_i)\omega(vv_j) $, which is in turn obviously equivalent to (P5).\hfill $\qed$ \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Concluding remarks and open questions}\label{sec:concludingremarks} Let $\gg$ be the class of graphs that can be made crossing-critical by a suitable multiplication of edges. In this work we have proved that a large family of graphs is contained in $\gg$ (note that the cubic condition is only used around vertices $u,v,u_1,u_2, u_3, v_1,v_2$ and $v_3$; other vertices can have arbitrary degrees). Which other graphs belong to $\gg$? Is there any hope of fully characterizing $\gg$? It is not difficult to prove that we can restrict our attention to simple graphs: if $\overline{G}$ is a graph with multiedges and $G$ is a maximal simple graph contained in $\overline{G}$, then $\oG$ is in $\gg$ if and only if $G$ is in $\gg$. One reason (but not necessarily the only one) for a graph $G$ not to belong to $\gg$, is the existence of an edge $e$ of $G$ with the following property: if $\dd$ is a drawing of $G$ in which $e$ is crossed, then there is a drawing $\dd'$ in which $e$ is not crossed, and such that every two edges that cross each other in $\dd'$ also cross each other in $\dd$. It is immediately seen that such a graph is not in $\gg$. As Jes\'us Lea\~nos has pointed out, the easiest such instance is the graph $K_{3,3}^+$ obtained by adding to $K_{3,3}$ an edge (between vertices in the same chromatic class). Following \v{S}ir\'a\v{n}~\cite{siran1,siran2}, an edge $e$ in a graph $G$ is a {\em Kuratowski edge} if there is a subgraph $H$ of $G$ that contains $e$ and is homeomorphic to a Kuratowski graph (that is, $K_{3,3}$ or $K_5$). It is trivial to see that the added edge in Lea\~nos's example is not a Kuratowski edge of $K_{3,3}^+$. This observation naturally gives rise to the following. \begin{conjecture}\label{con:thecon} If $G$ is a graph all whose edges are Kuratowski edges, then $G$ can be made crossing-critical by a suitable multiplication of its edges. \end{conjecture} We remark that the converse of this statement is not true: \v{S}ir\'a\v{n}~\cite{siran1} gave examples of graphs that contain crossing-critical edges that are not Kuratowski edges. The only positive result we have in this direction is that Kuratowski edges can be made individually crossing-critical: \begin{proposition}\label{pro:kur1} If $e$ is a Kuratowski edge of a graph $G$, then $e$ can be made crossing-critical by a suitable multiplication of the edges of $G$. \end{proposition} \begin{proof} Let $H$ be a subgraph of $G$, homeomorphic to a Kuratowski graph, such that $e$ is in $H$. Let $f$ be another edge of $H$ such that there is a drawing $\dd_H$ of $H$ with exactly one crossing, which involves $e$ and $f$. Extend $\dd_H$ to a drawing $\dd$ of $G$. Let $p$ be the number of crossings in $\dd$. If $p=1$ then $e$ is already critical in $G$, so there is nothing to prove. Thus we may assume that $p \ge 2$. %$p$ be the maximum number of %edges crossed by an edge in $G$, and let $k$ be the maximum number %of crossings among any two edges of $G$ in $\dd$. Add $p^2-1$ parallel edges to each of $e$ and $f$, add $p^4-1$ parallel edges to all edges in $H\setminus \{e,f\}$, and do not add any parallel edge to the other edges of $G$. Let $G'$ denote the resulting graph. We claim that $\cro(G')\le p^5$. To see this, consider the drawing $\dd'$ of $G'$ naturally induced by $\dd$. It is easy to check that each crossing from $\dd$ yields at most $p^4$ crossings in $\dd'$ (here we use that $e$ and $f$ are the only edges in $H$ that cross each other in $\dd$). Thus $\dd'$ has at most $p\cdot p^4=p^5$ crossings, and so $\cro(G') \le p^5$, as claimed. On the other hand, it is clear that a drawing of $G'$ in which $e$ and $f$ do not cross each other has at least $p^6$ crossings. Since $p^6 > p^5 \ge \cro(G')$, it follows that no such drawing can be optimal. Therefore $e$ and $f$ cross each other in every optimal drawing of $G'$. This immediately implies that $e$ is critical in $G'$. \end{proof} The immediate next step towards Conjecture~\ref{con:thecon} seems already difficult enough so as to prompt us to state it: \begin{conjecture} Suppose that $e,f$ are Kuratowski edges of a graph $G$. Then there exists a graph $H$, obtained by multiplying edges of $G$, such that both $e$ and $f$ are crossing-critical in $H$. \end{conjecture} The proof technique of Proposition~\ref{pro:kur1} cannot be applied to settle this conjecture. Indeed, if we were to apply the same ideas, in order to make $e$ critical we would assign a weight to the other edges of $G$, and to make $f$ critical we would also assign a weight to the other edges of $G$; the problem is that these edge assignments could (in principle) be irreconcilably different. Finally, let us remark that the proof technique of Theorem~\ref{thm:maintheorem} can be applied to other similar families of near-planar graphs. For instance, the vertices sufficiently far from $u$ and $v$ need not have degree $3$. Moreover, neither $u$ nor $v$ needs to have degree $3$; this requirement may be substituted by asking that there exist $3$ vertices adjacent to $u$ that are incident with faces distinct from each other and distinct from $F_u$ (respectively, $F_v$). Actually, this last property is essential in our proof, and is the reason to require internal $3$-connectivity instead of the weaker condition that $G-\{u,v\}$ is the subdivision of a $3$-connected graph and $G-uv$ is subcubic. \vglue 0.8 cm \noindent{\bf\Large Acknowledgements} \vglue 0.8 cm We thank Jes\'us Lea\~nos for helpful discussions. We also thank two anonymous referees for their constructive suggestions, which helped us to substantially improve this paper. %%%%%%%% The second and third authors were supported by CONACYT Grant 106432. %Let cr(G) denote the crossing number of the graph G (on the plane or, equivalently, on the sphere). An edge e of G is said to be crossing-critical if cr(G−e)