# An Approximate Generalization of the Okamura-Seymour Theorem

Nikhil Kumar
Hasso Plattner Institute
University of Potsdam, Germany

###### Abstract

We consider the problem of multicommodity flows in planar graphs. Okamura and
Seymour [11] showed that if all the demands are incident on one face, then the
cut-condition is sufficient for routing demands. We consider the following
generalization of this setting and prove an approximate max flow-min cut
theorem: for every demand edge, there exists a face containing both its end
points. We show that the cut-condition is sufficient for routing
$\Omega(1)$-fraction of all the demands. To prove this, we give a
$L_{1}$-embedding of the planar metric which approximately preserves distance
between all pair of points on the same face.

##  1 Introduction

Given a graph $G$ with edge capacities and multiple source-sink pairs, each
with an associated demand, the multicommodity flow problem is to route all
demands simultaneously without violating edge capacities. The problem was
first formulated in the context of VLSI routing in the 70’s and since then it
has seen a long and impressive line of work.

The demand graph, $H$ is the graph obtained by including an edge
$(s_{i},t_{i})$ for a demand with source-sink $s_{i},t_{i}$. A necessary
condition for the flow to be routed is that the capacity of every cut exceeds
the demand across the cut. This condition is known as the cut-condition and is
known to be sufficient when $G$ is planar and all the source-sink pairs are on
one face [11] or when $G+H$ is planar [14]. However, one can construct small
instances where the cut-condition is not sufficient for routing flow. When $G$
is series-parallel, if every cut has capacity at least twice the demand across
it, then flow is routable [6, 3]. The flow-cut gap of a certain graph class is
the smallest $\alpha$ such that flow is routable when capacity of every cut is
at least $\alpha$ times the demand across it. Thus, for series-parallel
graphs, the flow-cut gap is 2. For general graphs, the flow-cut gap is
$\Theta(\log k)$ [10], where $k$ is the number of demand pairs.

The flow-cut gap for planar graphs ($G$ planar, $H$ arbitrary) is
$\mathcal{O}(\sqrt{\log n})$ [12] and is conjectured to be $\mathcal{O}(1)$
[6]. Chekuri et al. [4] showed a flow-cut gap of $2^{\mathcal{O}(k)}$ for
$k$-outerplanar graphs. Lee et al. [8] made progress towards this conjecture
by showing an $\mathcal{O}(\log h)$ bound on the flow-cut gap, where $h$ is
the number of faces on which source-sink vertices are incident. Filtser [5]
further improved his bound by showing a flow-cut gap of
$\mathcal{O}(\sqrt{\log h})$, when all the source-sink vertices are incident
on $h$ faces. In this paper, we consider instances where the source and sink
of every demand lie on the same face, but all source-sink pairs don’t
necessarily lie on a single face, and show that the flow-cut gap of such
instances is $\mathcal{O}(1)$. It is well known that the cut-condition is not
sufficient for such instances (see Figure 1).

Figure 1: This example first appeared in the work of Okamura and Seymour [11].
All supply (blue) and demand (red) edges have value 1. $S$ (green) is a cut.
The total capacity of supply edges across $S$ is three while $S$ separates
three units of demand; hence $S$ satisfies the cut-condition. One can check
that no cut violates the cut-condition. Since the source-sink of every demand
is distance two apart, a total capacity of $4\cdot 2=8$ is required for a
feasible routing, but only six are available. Hence, no feasible routing is
possible. This also implies that no more than 3/4 of every demand can be
routed simultaneously. Figure on the right shows a feasible routing of 3/4 of
every demand, which implies a flow-cut gap of 4/3.

A common approach to establish bounds on the flow-cut gap is to bound the
$L_{1}$ distortion incurred in embedding an arbitrary metric on the graph $G$
into a normed space. This, for instance, has been the method used to establish
flow-cut gaps for general graphs [10], series-parallel graphs [6, 3] and
planar graphs [12]. We too build on this technique to prove our results (see
Theorem 5 and 6).

##  2 Definitions and Preliminaries

Let $G=(V,E)$ be a simple graph with edge capacities $c:E\rightarrow R_{\geq
0}$. We call this the supply graph. Let $H=(V,D)$ be a simple graph with
demands on edges $d:D\rightarrow R_{\geq 0}$. We call this the demand graph.
The objective of the $\bf{multicommodity}$ $\bf{flow}$ problem is to find
paths between the end points of demand edges in the supply graph such that the
following hold: for every demand edge $e\in D$, $d(e)$ paths are picked in the
supply graph and every supply edge $e\in E$ is present in at most $c(e)$
paths.

We say that an instance is feasible if paths satisfying the above two
conditions can be found. We also call such an instance integrally feasible. If
there exists an assignment of positive real numbers to paths such that total
flow for every demand edge $e\in F$ is $d_{e}$ and total value of paths using
a supply edge $e\in E$ is at most $c_{e}$, then we say that the instance is
(fractionally) feasible. A cut $S\subseteq V$ is a partition of the vertex set
$(S,V\setminus S)$. The number of edges of $G$ going across the cut is denoted
by $\delta_{G}(S)$. Similarly, $\delta_{H}(S)$ denotes the number of demand
edges going from $S$ to $V\setminus S$. One necessary condition for routing
the flow (fractionally or integrally) is as follows: for every $S\subseteq
V,\delta_{G}(S)\geq\delta_{H}(S)$. In other words, across every cut, total
supply should be at least the total demand. This condition is also known as
the cut-condition. In general, the cut-condition is not sufficient for a
feasible routing. We can ask for the following relaxation: given an instance
for which the cut-condition is satisfied, what is the maximum value of $f$,
such that $f$ fraction of every demand can be routed? The number $f^{-1}$ is
known as the flow-cut gap of the instance. There is an equivalent definition
of the flow-cut gap: given an instance $(G,H)$ satisfying the cut condition,
the smallest number $k$, such that $(kG,H)$ is feasible, where $kG$ denotes
the graph with every edge capacity multiplied by $k$ (see Figure 1 for an
illustration). The following two classic results identify settings where the
cut-condition is also sufficient for routing demands in planar graphs. We will
be invoking these to prove our results.

######  Theorem 1 (Okamura-Seymour [11])

If $G$ is a planar graph, all the edges of $H$ are restricted to a face and
$G+H$ is eulerian, then the cut-condition is necessary and sufficient for
integral routing of all the demands.

######  Theorem 2 (Seymour [14])

If $G+H$ is planar and eulerian, then the cut-condition is necessary and
sufficient for integral routing of all the demands.

Note that if eulerian condition is not satisfied, we get a half integral flow.
Both the results can be converted into algorithms which run in polynomial
time. In this paper, we will not be concerned with (half) integral flows and
focus on proving flow-cut gap for instances that generalize the setting of the
above stated results (see Theorem 5).

From now on, we assume a fixed planar embedding of $G$. Without loss of
generality, one can assume that $G$ is 2-vertex connected. If there is a cut
vertex $v$ and $ab$ is a demand separated by removal of $v$, then replacing
$ab$ by $av,vb$ maintains the cut-condition. By doing this for every cut
vertex and demand separated by them, we get separate smaller instances for
each 2-vertex connected component. Hence, every vertex is a part of cycle
corresponding to some face. By our assumption, for every demand edge there
exists a face such that both its end points lie on that face. Hence, we can
associate every demand with a face. We abuse notation and use $f$ to also
denote the edges and vertices associated with the cycle of face $f$. Given a
set $S$, we denote the subgraph induced by vertices in $S$ as $G[S]$. We call
a subset $A\subseteq V$ central if both $G[A]$ and $G[V-A]$ are connected. The
following is well-known.

######  Lemma 1 ([13])

$(G,H)$ satisfies the cut-condition if and only if all the central sets
satisfy the cut-condition.

The set of all faces of $G$ will be denoted by $F$. The $\bf{dual}$ of a
planar graph $G^{D}=(V^{D},E^{D})$ is defined as follows: $V^{D}=F$ and if
$f_{i},f_{j}\in F$ share an edge in $G$, then $(f_{i},f_{j})\in E^{D}$. It is
a well known fact that edges of a central cut in $G$ correspond to a simple
circuit in $G^{D}$ and vice versa. Given a graph $G=(V,E)$ with edge length
$l:E\rightarrow\mathbb{R}_{\geq 0}$, we use $d_{G}(u,v)$ to denote the
shortest path distance between $u$ and $v$ in $G$ w.r.t $l$. We now describe
the connection between flow-cut gap and embedding vertices into normed space.

###  2.1 Embedding Metrics into $L_{1}$

Given an edge weighted graph $G=(V,E)$ with edge length
$l:E\rightarrow\mathbb{R}_{\geq 0}$, associated shortest path metric $d_{G}$,
a graph $H=(V,F)$ and an embedding $f$ of vertices $V$ into $L_{1}$, the
contraction and expansion of $f$ are the smallest $\alpha$, $\beta$
respectively, such that $||f(u)-f(v)||_{1}\geq d_{G}(u,v)/\alpha$ for all
$(u,v)\in F$ and $||f(u)-f(v)||_{1}\leq\beta\cdot d_{G}(u,v)$ for all
$(u,v)\in E$. The distortion of the embedding, $\texttt{dist}(G,H,f)$, is
$\alpha\cdot\beta$. Given $G,H$, we are generally interested in finding an
embedding with low distortion. If $H$ is a clique, we refer to
$\texttt{dist}(G,H,f)$ simply as $\texttt{dist}(G,f)$ and call it the
distortion of $G$ with respect to $f$. Linial et al. [10] built on the result
of Bourgain [1], and gave a polynomial time algorithm that embeds any graph on
$n$ vertices into $L_{1}$ with distortion $\mathcal{O}(\log n)$. Furthermore,
this result is asymptotically the best possible, as there exist instances for
which any embedding into $L_{1}$ has distortion $\Omega(\log n)$. There is a
rich literature on finding low distortion embeddings for special graph
classes. It is well known that a tree can be embedded into $L_{1}$ with
distortion 1, outerplanar graphs with distortion 1 [11], $k$-outerplanar
graphs with distortion $2^{\mathcal{O}(k)}$ [4], series-parallel graphs with
distortion 2 [3]. Rao [12] showed that any planar metric can be embedded into
$L_{1}$ with distortion $\mathcal{O}(\sqrt{\log n})$ and there has essentially
been no improvement upon this in the last two decades. It is conjectured that
any planar graph can be embedded into $L_{1}$ with distortion $\mathcal{O}(1)$
[6] (also known as the GNRS-Conjecture). In this paper, we make progress
towards this conjecture. Given a drawing of a planar graph in the plane, let
$H$ be the set of all pairs of vertices $(u,v)$ such that $u$ and $v$ lie on
the same face. We show the existence of a polynomial time computable
$f:V\rightarrow L_{1}$ such that $\texttt{dist}(G,H,f)=\mathcal{O}(1)$. In
this paper, we will work exclusively with the 1-norm, so we drop the subscript
and denote $||f(u)-f(v)||_{1}$ simply as $||f(u)-f(v)||$. Also, if $\beta=1$,
we say that the embedding is non-expansive. By scaling, we may convert any
$L_{1}$ embedding into a non-expansive one.

###  2.2 Flow-Cut Gap and Embedding into $L_{1}$

Flow-cut gaps and embedding graphs into $L_{1}$ are intimately related. This
connection was first observed by Linial et al. [10], who used it to prove
flow-cut gap results for arbitrary graphs. We describe this connection
formally now. Let $G=(V,E),H=(V,F)$ be fixed graphs and
$c:E\rightarrow\mathbf{R_{\geq 0}}$, $d:F\rightarrow\mathbf{R_{\geq 0}}$ and
$l:E\rightarrow\mathbf{R_{\geq 0}}$ be the capacity, demand and length
functions on respective edge sets. Let $\mathcal{I}$ be the set of all
multicommodity flow instances $G=(V,E,c),H=(V,F,d)$ for which the cut-
condition is satisfied. Let $\texttt{cong}(G,H)$ denote the maximum congestion
required for routing in any multicommodity flow instance in $\mathcal{I}$. Let
$\texttt{dist}(G,H)$ be the minimum number such that for any length function
$l$, there exists a $f$ such that
$\texttt{dist}(G,H,f)\leq\texttt{dist}(G,H)$, where $G=(V,E)$ with edge-length
$l$. The congestion-distortion theorem states that
$\texttt{cong}(G,H)=\texttt{dist}(G,H)$. See Section 3 of [2] for a simple
proof of this fact using LP duality. This connection has been exploited
extensively to prove flow-cut gap results for general graphs [10], series-
parallel graphs [3, 6] and planar graphs [12]. All these results proceed by
showing the existence of a low distortion embedding of the corresponding
metric into $L_{1}$. Using the congestion-distortion theorem, we now restate
the theorem of Okamura and Seymour [11] and Seymour [14] in terms of metric
embedding.

######  Theorem 3 (Okamura-Seymour[11])

Let $G=(V,E)$ be a planar graph with edge length
$l:E\rightarrow\mathbb{R}_{\geq 0}$ and $t\in F$ be one of its faces. Then
there exists an embedding of $V$ into $L_{1}$ such that for all $u,v\in
t,||f(u)-f(v)||=d_{G}(u,v)$ and for all $(u,v)\in E,||f(u)-f(v)||\leq
d_{G}(u,v)=l(u,v)$.

######  Theorem 4 (Seymour[14])

Let $G=(V,E)$ be a planar graph with edge length
$l:E\rightarrow\mathbb{R}_{\geq 0}$ and $H=(V,T)$ be a demand graph such that
$G+H$ is planar. Then there exists an embedding of $V$ into $L_{1}$ such that
for all $(u,v)\in T,||f(u)-f(v)||=d_{G}(u,v)$ and for all $(u,v)\in
E,||f(u)-f(v)||\leq d_{G}(u,v)=l(u,v)$.

###  2.3 Cut Metrics and $L_{1}$ Embedding

Suppose we have a set of cuts with non-negative weights
$\mathcal{C}=\\{(C_{1},w_{1}),\ldots,(C_{k},w_{k})\\}$. Define
$\delta_{C_{i}}(u,v)$ to be $w_{i}$ if exactly one of $u,v$ is contained in
$C_{i}$ and 0 otherwise. Let
$\delta_{\mathcal{C}}(u,v)=\sum_{i=1}^{k}\delta_{C_{i}}(u,v)$. It is easy to
verify that $\delta_{C}$ induces a metric on $V$. We refer to $\delta_{C}$ as
the distance induced by the cuts in $\mathcal{C}$ or a cut-metric
$\mathcal{C}$. One can construct $f:V\rightarrow\mathbb{R}^{k}$ such that
$\forall u,v$ we have $||f(u)-f(v)||_{1}=\delta_{\mathcal{C}}(u,v)$ as
follows: for any vertex $u$, define $f(u)=(u_{1},u_{2},\ldots,u_{k})$ where
$u_{i}=w_{i}$ if $u\in C_{i}$, 0 otherwise. In fact, the converse of above is
also true: given any embedding of vertices into $L_{1}$, there exists a set of
weighted cuts $\mathcal{C}$ such that the distance metric induced by
$\mathcal{C}$ is equal to the distance metric induced by the $L_{1}$ embedding
(see Lemma 15.2 of [15] for a proof). Hence, to show a low distortion $L_{1}$
embedding of a metric, it is equivalent to show a collection of cuts which
preserve distances with low distortion. Using the aforementioned equivalence
of the cut-metric and $L_{1}$ embedding, we us them interchangeably from now
on. Given a scalar $\alpha$ and a collection of weighted cuts $\mathcal{C}$,
$\alpha\cdot\mathcal{C}$ denotes the the same collection of cuts with the
weight of all cuts scaled by a (multiplicative) factor of $\alpha$.

##  3 Our Contribution

We generalize the result of Okamura and Seymour [11] and prove the following
approximate max flow-min cut theorem:

###### Theorem 5

Let $G$ be an edge-capacitated planar graph and $H$ be a set of demand edges
such that for each $(u,v)\in H$, there exists a face $f$ containing both $u$
and $v$. If the cut-condition is satisfied, then there exists a feasible
routing of $\Omega(1)$-fraction of all the demands.

Using the congestion-distortion theorem, Theorem 5 can be stated in terms of
metric embedding as follows:

###### Theorem 6

Let $G=(V,E)$ be a planar graph with edge length $l\rightarrow\mathbb{R}_{\geq
0}$ and $T$ be pairs of vertices $(u,v)$ such that both $u$ and $v$ lie on the
same face. Then there exists a constant $c>1$ and an embedding $g:V\rightarrow
L_{1}$ such that $||g(u)-g(v)||\geq d_{G}(u,v)/c$ for $(u,v)\in T$ and
$||g(u)-g(v)||\leq l(u,v)$ for $(u,v)\in E$.

We now give a brief overview of our approach. As mentioned before, we work
with a fixed embedding of the given planar graph in the plane. We call a face
$f\in F$ geodesic if for all $u,v\in f$, $d_{G}(u,v)$ is equal to the shortest
path distance between $u,v$ using only the edges of the cycle corresponding to
$f$. A face which is not geodesic is called non-geodesic. Let $F_{G}$ and
$F_{N}$ denote the set of all the geodesic and non-geodesic faces. Given a
face $f$, let $G_{f}$ be the subgraph enclosing minimal area in the plane that
supports the metric on the vertices of face $f$. Let $S_{f}$ be the minimal
area cycle bounding $G_{f}$ in the plane. Given a cycle $S$, let
$R(S)\subseteq\mathbb{R}^{2}$ be the open region contained inside $S$.

If $f$ is a geodesic face, then $G_{f}$ is exactly the cycle bounding the
face, i.e. $G_{f}=S_{f}$. In Section 4, we first show that the set
$\\{R(S_{f})|f\in F\\}$ forms a laminar or non-crossing set system. This
implies that there is a face $f$ with minimal $R(S_{f})$, i.e. for any
$f^{\prime}\neq f$ either $R(S_{f})\subseteq R(S_{f^{\prime}})$ or
$R(S_{f})\cap R(S_{f^{\prime}})=\emptyset$. We then go on to show that
removing the edges of $(G_{f}\setminus S_{f})$ doesn’t modify the metric on
any of the non-geodesic faces other than $f$. We then go on to find a suitable
embedding of the graph $(G\setminus G_{f})\cup S_{f}$ inductively and show how
to extend the embedding to include all the faces contained in $R(S_{f})$. This
extension argument turns out to be non-trivial and forms the core of our
proof. To do this extension, we need to develop several new tools. In Section
4, we give an algorithm to modify the original length function so as to allow
a nice inductive decomposition. We call such length functions $\alpha$-good
and believe that this could be a useful tool in proving flow-cut gaps for
other planar instances as well. In Section 5, we come up with an embedding for
all geodesic pairs of vertices,i.e. pairs of vertices for which there exists a
shortest path using only the edges on the corresponding face. In Section 6, we
develop a low distortion embedding for all pairs of vertices whose shortest
path uses a fixed vertex of the graph. We believe that this problem is
interesting in its own right and could prove to be useful in other settings.
In Sections 7 and 8, we combine the tools developed in previous sections to
complete the inductive step.

##  4 Laminar Structure of Face Supports

We partition the set of faces of a planar graph $G$ into two sets:
$\bf{geodesic}$ and non-geodesic. A face $f$ is called geodesic if for all
$u,v\in f$, there exists a shortest path between $u$ and $v$ using only the
vertices of the cycle associated with $f$. A face which is not geodesic is
called a non-geodesic face. Let $F_{G},F_{N}$ denote the set of geodesic and
non-geodesic faces. Observe that $F=F_{G}\cup F_{N}$.

Let $f$ be a face of $G$. A set of edges $E^{\prime}\subseteq E$ is called a
support of $f$ if for all $u,v\in f$, $d_{G^{\prime}}(u,v)=d_{G}(u,v)$, where
$G^{\prime}=(V,E^{\prime})$. In other words, restricting to $E^{\prime}$
doesn’t change the shortest path metric on $f$. A support of $f$ is called
minimal if deleting any edge from it changes the shortest path metric on
vertices of $f$. Given a cycle $C$, let $R(C)$ (resp. $\overline{R(C)}$)
denote the open (resp. closed) region contained inside the cycle $C$ in the
planar embedding of $G$. We choose $R(C)$ and $\overline{R(C)}$ such that it
does not contain the infinite face. Let $S_{f}$ be a cycle such that
$\overline{R(S_{f})}$ is the inclusion wise minimal region containing a
support of $f$ (i.e. there exists a support $E_{f}$ of $f$ such that
$u,v\in\overline{R(S_{f})}$ for all $(u,v)\in E_{f}$). Note that if $f\in
F_{G}$, then $S_{f}=f$. Also, for any $f\in F$,
$\overline{R(f)}\subseteq\overline{R(S_{f})}$. We stress that the $S_{f}$ is a
function of the edge-lengths.

###### Lemma 2

Let $f_{1},f_{2}\in F_{N}$. Then one of the following must hold:
$R(S_{f_{1}})\cap R(S_{f_{2}})=\emptyset$ or $R(S_{f_{1}})\subseteq
R(S_{f_{2}})$ or $R(S_{f_{2}})\subseteq R(S_{f_{1}})$.

Proof. For the sake of contradiction, assume that there exist $f_{1},f_{2}\in
F_{N}$ such that $R(S_{f_{1}})\setminus R(S_{f_{2}})\neq\emptyset$ and
$R(S_{f_{2}})\setminus R(S_{f_{1}})\neq\emptyset$. Then either $R(f_{1})\in
R(S_{f_{2}})$ or $R(f_{1})\cap R(S_{f_{2}})=\emptyset$. We present the
argument for the case when $R(f_{1})\in R(S_{f_{2}})$, an analogous argument
works for the second case as well. Suppose $R(f_{1})\in R(S_{f_{2}})$. Then
there must exist $u_{1},v_{1}\in f_{1}$ such that any shortest path from
$u_{1}$ to $v_{1}$ exits and enters the region $R(S_{f_{2}})$ at least once.
Let $P(u_{1},v_{1})$ be one such shortest path and $x_{1},y_{1}$ be the first
point of entry/last point of exit of $P(u_{1},v_{1})$ from/into $R(S_{f_{2}})$
respectively. Let $P(x_{1},y_{1})$ be the portion of the path between $x_{1}$
and $y_{1}$ on the cycle $S_{f_{2}}$. Note that $P(x_{1},y_{1})$ is a path on
the boundary of $\overline{R(S_{f_{2}})}$. Since $\overline{R(S_{f_{2}})}$
defines the minimal region containing the support of the metric on $f_{2}$,
there must exist $u_{2},v_{2}\in f_{2}$ such that some shortest path between
$u_{2}$ and $v_{2}$ uses an edge on the path $P(x_{1},y_{1})$. Let
$P(u_{2},v_{2})$ be such a shortest path and let $x_{2},y_{2}$ be the first
and the last point of intersection of $P(u_{2},v_{2})$ with $P(u_{1},v_{1})$.
Then replacing the portion of the path $P(u_{1},v_{1})$ between $x_{2}$ and
$y_{2}$ by portion of the path $P(u_{2},v_{2})$ between $x_{2}$ and $y_{2}$,
we obtain a shortest $u_{1},v_{1}$ path contained completely inside
$S_{f_{2}}$. This contradicts our assumption on the minimality of
$\overline{R(S_{f_{1}})}$. We can use an analogous argument to arrive at a
contradiction in case $R(f_{1})\cap R(S_{f_{2}})=\emptyset$. Hence such
$f_{1},f_{2}$ can’t exist and it must be true that $R(S_{f_{1}})\cap
R(S_{f_{2}})=\emptyset$ or $R(S_{f_{1}})\subseteq R(S_{f_{2}})$ or
$R(S_{f_{2}})\subseteq R(S_{f_{1}})$ for any $f_{1},f_{2}\in F_{N}$.

Given a cycle $C$, let $I(C)$ be the set of vertices contained in $R(C)$. Note
that $I(C)$ doesn’t contain vertices of $C$. Let $\alpha>1$ be a given
constant. Given a face $f\in F_{N}$ and its support cycle $S_{f}$, we say that
$S_{f}$ is $\alpha$-loose if the following holds: for any $u,v\in f$, the
length of any path between $u$ and $v$ using only the vertices in
$I(S_{f})\cup\\{u,v\\}$ is at least $\alpha\cdot d_{G}(u,v)$.

To make the induction argument work, only the laminar property of face
supports is not sufficient and we need a stronger structure. We now describe
this property in more detail now. By Lemma 2, the set of regions
$\\{R(S_{f})|f\in F_{N}\\}$ forms a laminar structure. This implies that there
exists a face $f\in F_{N}$ such that for any $f^{\prime}\in F_{N}$, either
$R(S_{f})\subseteq R(S_{f^{\prime}})$ or $R(f)\cap
R(S_{f^{\prime}})=\emptyset$. We call such faces innermost. Note that there
could be multiple innermost faces. An $\alpha$-good length function
$l:E\rightarrow\mathbb{R}^{+}$ is defined inductively as follows: if $f\in
F_{N}$ is an innermost face, then the graph obtained by removing all the edges
contained completely inside $R(S_{f})$ is $\alpha$-good and $S_{f}$ is
$\alpha$-loose. We now show than any length function can be converted into a
$\alpha$-good one by modifying the edge lengths by a factor of at most
$\alpha$.

###### Theorem 7

Let $G=(V,E)$ be a planar graph with $f_{I}$ as the infinite face, edge length
$l:E\rightarrow\mathbb{R}_{\geq 0}$ and $\alpha>1$ be a constant. Then there
exists a new edge length $l^{\prime}:E\rightarrow\mathbb{R}^{+}$ such that $G$
is $\alpha$-good with respect to $l^{\prime}$, $l^{\prime}(e)=l(e)$ for $e\in
E\cap f_{I}$ and $l(e)/\alpha\leq l^{\prime}(e)\leq l(e)$ for $e\in E$.

Proof. We prove the theorem by induction on the number of faces in the graph.
In case $|F|=1$ or there are no non-geodesic faces, the statement of the
theorem follows trivially by setting $l^{\prime}=l$. Suppose that $G$ has at
least one non-geodesic face w.r.t the length function $l$. By Lemma 2, regions
in the set $\\{R(S_{f})|f\in F_{N}\\}$ form a laminar structure. A face $f\in
F_{N}$ is called maximal if for any other face $f^{\prime}$, either
$R(S_{f^{\prime}})\subseteq R(S_{f})$ or $R(S_{f^{\prime}})\cap
R(S_{f})=\emptyset$. Let $f_{1},f_{2},\ldots,f_{k}$ be the maximal faces of
$G$ w.r.t length function $l$. Let $G_{i}$ be the graph consisting of vertices
and edges contained completely inside $\overline{R(S_{f_{i}})}$. If $k=1$ and
$R(f_{I})\subset R(S_{f_{1}})$ or $k\geq 2$, then each $G_{i}$ has strictly
less number of faces than $G$. By induction, for each $G_{i}$ we have length
functions $l_{i}$ satisfying the conditions of the theorem. We construct the
new length function $l^{\prime}$ as follows: for an edge $(u,v)$ not contained
in any of the $G_{i}$, we set $l^{\prime}(u,v)=l(u,v)$. If an edge $(u,v)$ is
contained in $G_{i}$, we set $l^{\prime}(u,v)=l_{i}(u,v)$. Note that if an
edge $(u,v)$ is contained in $G_{i}$ and $G_{j}$, then it must be present on
the infinite face of $G_{i},G_{j}$ and $l_{i}(u,v)=l_{j}(u,v)=l(u,v)$ (by
induction). Hence $l^{\prime}$ is a valid length function and by construction
$G$ is $\alpha$-good with w.r.t $l^{\prime}$. Suppose that $k=1$ and
$R(S_{f_{1}})=R(f_{I})$. We consider two cases depending on whether face
$f_{I}$ is $\alpha$-loose or not.

Suppose the face $f_{I}$ is not $\alpha$-loose. By the definition of a
$\alpha$-loose face, there must exist $u,v\in f_{I}$ such that the shortest
$u,v$ path using no edges on $f_{I}$ has length $\beta\cdot d_{G}(u,v)$, for
some $\beta\leq\alpha$. Let $P=\\{u,u_{1},\ldots,u_{l},v\\}$ be such a path.
For every edge $e\in P$, we set $l^{\prime}(e)=l(e)/\beta$. Since $P$ contains
no edge of the infinite face $f_{I}$, the length of edges on $f_{I}$ remain
unchanged due to this operation. The path $P$ divides $\overline{R(f_{I})}$
into two closed regions, say $R_{1}$ and $R_{2}$. Let $G_{1}\subset G$ and
$G_{2}\subset G$ be the graphs contained inside $R_{1}$ and $R_{2}$
respectively. Since $P$ is a shortest $u,v$ path w.r.t $l^{\prime}$, it
follows that for any $f\in G_{i}$, $R(S_{f})\subseteq R_{i}$ for $i=1,2$.
Hence, if $u,v\in G_{i}$, then $d_{G_{i}}(u,v)=d_{G}(u,v)$ for $i=1,2$.
Therefore we can compute length functions for $G_{1},G_{2}$ separately by
using induction and combine them as before. Using induction, we find length
functions $l_{1},l_{2}$ satisfying the conditions of the theorem and set
$l^{\prime}(e)=l_{i}(e)$ depending on whether $e\in G_{1}$ or $e\in G_{2}$. If
$e$ belongs to both to $G_{1}$ and $G_{2}$, then $e$ is on the infinite face
of $G_{1}$ and $G_{2}$ and by the statement of the theorem,
$l_{1}(e)=l_{2}(e)$. Hence $l^{\prime}$ is a valid length function satisfying
the conditions of the theorem.

Suppose that face the $f_{I}$ is $\alpha$-loose. Then the statement of the
theorem holds for non-geodesic face $f_{1}$. Let $g_{1},g_{2},\ldots,g_{k}$ be
the maximal non-geodesic faces contained strictly inside $R(f_{I})$. By the
laminar structure of regions in $\\{R(S_{f})|f\in F_{N}\\}$, we have
$R(S_{g_{i}})\cap R(S_{g_{j}})=\emptyset$ for $i\neq j$. Let $G_{i}$ be the
graph consisting of vertices and edges contained completely inside
$\overline{R(S_{g_{i}})}$. By induction hypothesis, we have length functions
$l_{1},\ldots,l_{k}$ such that each one of them satisfies the statement of the
theorem. We set $l^{\prime}(e)=l(e)$ for any edge not contained inside any of
the $G_{i}^{\prime}s$ and set $l^{\prime}(e)=l_{i}(e)$ if $e\in G_{i}$. Since
for any edge $e\in S_{g_{i}}$, $l^{\prime}(e)=l(e)$, we do not create any new
non-geodesic face in $R(f_{I})\setminus\cup_{i=1}^{k}R(S_{g_{i}})$. We
complete the proof of the theorem by showing that
$\overline{R(S_{f_{1}})}=\overline{R(f_{I})}$ and $f_{I}$ is $\alpha$-loose
w.r.t $l^{\prime}$. To show this, we prove that the metric on $f_{1}$ w.r.t to
$l$ and $l^{\prime}$ are the same.

###### Lemma 3

Let $u,v\in f\in F_{N}$ and $P=\\{u,u_{1},u_{2},\ldots,u_{l},v\\}$ be a
shortest $u,v$ path, then $P\cap I(S_{f})=\\{u,v\\}$.

Proof. Suppose there exists $u,v$ and a shortest path
$P=\\{u,u_{1},u_{2},\ldots,u_{l},v\\}$ between them such that
$\\{u_{1},u_{2},\ldots,u_{l}\\}\cap I(S_{f})\neq\emptyset$. Let
$S^{\prime}_{f}$ be the cycle created by replacing the $u,v$ path on the cycle
$S_{f}$ by $P$ such that
$\overline{R(f)}\subseteq\overline{R(S^{\prime}_{f})}$. Since
$\\{u_{1},u_{2},\ldots,u_{l}\\}\cap
I(S_{f})\neq\emptyset,\overline{R(S^{\prime}_{f})}\subset\overline{R(S_{f})}$
and for any $u_{1},v_{1}\in f$, there exists a $u_{1},v_{1}$ shortest path
contained completely inside $\overline{R(S^{\prime}_{f})}$. Hence,
$\overline{R(S^{\prime}_{f})}$ contains a support of face $f$ and this
contradicts the minimality of $S_{f}$. Hence, $P\cap I(S_{f})=\\{u,v\\}$ and
this completes proof of the lemma.

By Lemma 3, deleting the edges contained completely inside a
$\overline{R(S_{g_{i}})}$ doesn’t affect the metric on $f_{1}$. Doing this for
each $i=1,2,\ldots,k$ in a sequential order and noting that for any
$e\in\displaystyle\cup_{i=1}^{l}S_{g_{i}}$, $l^{\prime}(e)=l(e)$, we conclude
that the metric on $f_{1}$ remains unchanged under $l^{\prime}$, and this
completes the proof of the theorem.

##  5 Embedding For The Geodesic Pairs

Let $G=(V,E)$ be a planar graph and $F$ be the set of its faces and $u,v\in V$
be a pair of vertices on the same face (i.e. there exists a face $f\in F$ such
that $u,v\in f$). Furthermore, suppose that there exists a shortest path
between $u$ and $v$ using only the edges of $f$. We call $(u,v)$ a geodesic
pair. Let $T$ be the set of all the geodesic pairs in $G$. In Theorem 9, we
show that there exists an embedding of $V$ into $L_{1}$ which preserves the
distances between all the geodesic pairs within a constant factor. Using the
congestion-distortion theorem, the following result follows directly from
Theorem 12 of Kumar [9].

###### Theorem 8

Let $G=(V,E)$ be a planar graph with edge length
$l:E\rightarrow\mathbb{R}_{\geq 0}$ and $T$ be pairs of vertices $(u,v)$ such
that both $u$ and $v$ lie on the same face. Let $T_{f}\subseteq T$ denote the
set of pairs of vertices incident on face $f$. Suppose for each $f\in F$,
there exists disjoint set of vertices
$X_{1},Y_{1},X_{2},Y_{2},\ldots,X_{k},Y_{k}\subseteq f$ such that
$X_{i},Y_{i}$ appear contiguously on $f$ in clockwise order and for each
$(u,v)\in T_{f},u\in X_{j},v\in Y_{j}$ for some $j\in\\{1,2,\dots,k\\}$. Then
there exists an embedding $h:V\rightarrow L_{1}$ such that $||h(u)-h(v)||\leq
d_{G}(u,v)$ for all $(u,v)\in E$ and $||h(u)-h(v)||\geq d_{G}(u,v)/3$ for all
$(u,v)\in T$.

###### Theorem 9

Let $G$ be a planar graph with edge length $l:E\rightarrow\mathbb{R}^{+}$.
Then there exists an embedding $g:V\rightarrow L_{1}$ such that
$||g(u)-g(v)||\leq d_{G}(u,v)$ for all $(u,v)\in E$ and $||g(u)-g(v)||\geq
d_{G}(u,v)/21$ for all $(u,v)\in T$.

Proof. We first construct a set of geodesic pairs $T_{p}\subseteq T$ as
follows. Initially $T_{p}=\emptyset$. Let $f\in F$ and
$V(f)=\\{v_{1},v_{2},\ldots,v_{n},v_{n+1}=v_{1}\\}$ be the vertices of $f$ in
clockwise order. We partition $V(f)$ into contiguous sets of vertices as
follows: let $v_{k}$ be the largest $k$ such that $(v_{1},v_{k})$ is a
geodesic pair. We set $T_{p}=T_{p}\cup(v_{1},v_{k})$ and
$S_{f}^{1}=\\{v_{1},v_{2},\ldots,v_{k}\\}$. We then start from $v_{k+1}$ and
find the largest index $l$ such that $(v_{k+1},v_{l})$ is a geodesic pair, set
$T_{p}=T_{p}\cup(v_{k+1},v_{l})$ and
$S_{f}^{2}=\\{v_{k+1},v_{k+2},\ldots,v_{l}\\}$, and we continue with this
process until all the vertices in $C(f)$ have been exhausted, i.e.
$C(f)=\cup_{i\geq 0}S_{f}^{i}$. We do the above for all the faces of $G$. By
construction, the graph $G\cup T_{p}$ is planar. Therefore by Theorem 4, we
have an embedding, say $h:V\rightarrow L_{1}$, that preserves the distance
between the end points of vertices in $T_{p}$ exactly. In other words,
$||h(u)-h(v)||=d_{G}(u,v)$ for all $(u,v)\in T_{p}$ and $||h(u)-h(v)||\leq
d_{G}(u,v)$ for all $(u,v)\in E$. Let $T^{\prime}=\\{(u,v)|u,v\in
S_{f}^{i},f\in F,i\geq 0\\}$. By construction, the first and the last vertex
(w.r.t the numbering above) of each of the set $S_{f}^{i}$ form a geodesic
pair, hence for all $u,v\in T^{\prime}$, we have that
$\||h(u)-h(v)||=d_{G}(u,v)$.

In Claim 1, we show that the geodesic pairs in $T\setminus T^{\prime}$ can be
partitioned into $T_{0},T_{1},T_{2},T_{3},T_{4},T_{5}$ such that each one of
them satisfies the condition of Theorem 8. Then by Theorem 8, there exists
$h_{i}:V\rightarrow L_{1}$ such that $||h_{i}(u)-h_{i}(v)||\leq d_{G}(u,v)$
for $(u,v)\in E$ and $||h_{i}(u)-h_{i}(v)||\geq d_{G}(u,v)/3$ for $(u,v)\in
T_{i}$ for $i=0,1,2,3,4,5$. By setting
$g=\dfrac{1}{7}(h+h_{0}+h_{1}+h_{2}+h_{3}+h_{4}+h_{5})$, we obtain
$||g(u)-g(v)||\leq d_{G}(u,v)$ for $(u,v)\in E$ and $||g(u)-g(v)||\geq
d_{G}(u,v)/21$ for $(u,v)\in T$.

###### Claim 1

$T\setminus T^{\prime}$ can be partitioned into
$T_{0},T_{1},T_{2},T_{3},T_{4},T_{5}$ such that each of the $T_{i}$’s
satisfies the condition of Theorem 8.

Proof. It is sufficient to show that the geodesic pairs incident on each face
can be partitioned into $T^{f}_{i}$ for $i=0,1,2,3,4,5$ such that each
$T^{f}_{i}$ satisfies the condition of Theorem 8. Let $f\in F$ and
$S_{f}^{1},S_{f}^{2},\ldots.S_{f}^{k}$ be the partition of $C(f)$ created in
the first step. Suppose there exists $(u,v)\in T\setminus T^{\prime}$ such
that $u\in S_{f}^{[l]},v\in S_{f}^{[l+t]}$ for some $t\geq 3$, where $[p]=p$
if $p\leq k$ and $p-k$ otherwise. Then our procedure in the first step would
not have created separate partitions for $S_{f}^{[l+1]}$ and $S_{f}^{[l+2]}$
and hence such a geodesic pair $(u,v)$ can’t exist. Therefore for all $u,v\in
C(f)$ and $(u,v)\in T\setminus T^{\prime}$, one of the following must hold:
$u\in S_{f}^{[l]},v\in S_{f}^{[l+1]}$ (called _type 1_) or $u\in
S_{f}^{[l]},v\in S_{f}^{[l+2]}$ (called _type 2_) for some $l$.

Let $(u,v)$ be a geodesic pair $(u,v)$ such that $u\in S_{f}^{i}$ and $v\in
S_{f}^{j}$. We say that $(u,v)$ belongs to class $i$ if $\min(i,j)\mod 3=i$.
Let $T^{f}_{0},T^{f}_{1},T^{f}_{2}$ be the geodesic pairs of class 0,1,2 of
_type 1_ incident on the face $f$ and $T^{f}_{3},T^{f}_{4},T^{f}_{5}$ be the
geodesic pairs of class 0,1,2 of _type 2_ incident on the face $f$. We set
$T_{i}=\bigcup_{f\in F}T^{f}_{i}$ for $i=0,1,2,3,4,5$. The geodesic pairs in
each of the $T_{i}$’s satisfy the condition of Theorem 8 and this completes
the proof of the claim.

##  6 Single Source Shortest Path Embeddings

We next show how to find an embedding such that the distance between all pairs
of vertices whose shortest path uses a fixed vertex $v$ is approximately
preserved. To prove this result, we make use of a well known result of Klein,
Plotkin and Rao [7] on small diameter decomposition. Let $(X,D)$ be a finite
metric space. A distribution $\mu$ over (vertex) partitions of $X$ is called
$(\beta,\Delta)$-lipschitz if every partition $P$ in the support of $\mu$
satisfies $S\in P\implies diam_{X}(S)\leq\Delta$ and moreover for all $x,y\in
X$, $\underset{P\sim\mu}{\mathcal{P}}[P(x)\neq
P(y)]\leq\beta\cdot\dfrac{d(x,y)}{\Delta}$. Klein, Plotkin and Rao [7] showed
that there exists a $(c,\Delta)$-lipschitz partition of a planar metric where
$\Delta>0$ is arbitrary and $c$ is an absolute constant. 111In fact Klein,
Plotkin and Rao [7] showed that such a partition exists for any minor-closed
family of graphs.

######  Theorem 10 (Klein, Plotkin and Rao [7])

Let $(X,D)$ be a finite planar metric and let $\Delta\in\mathbb{R}_{\geq 0}$
be a given number. Then there exists a polynomial-time computable
$(c,\Delta)$-lipschitz partition of $(X,D)$, where $c$ is some absolute
constant.

###### Theorem 11

Let $G=(V,E)$ be a planar graph with edge-length
$l:E\rightarrow\mathbf{R}_{\geq 0}$ and $v\in V$. Let
$T=\\{(s_{i},t_{i})\\}_{i=1}^{k}$ be the set of pair of vertices such that
$d(s_{i},t_{i})=d(v,s_{i})+d(v,t_{i})$ for $i=1,2,\ldots,k$. Then there exists
an embedding $g:V\rightarrow L_{1}$ and a constant $\beta>1$ such that
$d(s_{i},t_{i})/\beta\leq||g(s_{i})-g(t_{i})||\leq d(s_{i},t_{i})$ for all
$i$. Furthermore such an embedding can be computed in polynomial time.

Proof. We first prove the theorem for the special case when
$d(v,s_{i})=d(v,t_{i})$ for all $(s_{i},t_{i})\in T$. Let
$B_{i}=\\{x|d(v,x)\leq 2^{i+1}\\}$ for $i\geq 0$. Since
$d(v,s_{j})=d(v,t_{j})$ for each $(s_{j},t_{j})\in T$, there exists an $i$
such that $(s_{j},t_{j})\in B_{i+1}\setminus B_{i}$. Let
$T_{i}=\\{(s_{j},t_{j})|2^{i}\leq d(v,s_{j})=d(v,t_{j})\leq 2^{i+1}\\}$ and
$G_{i}$ be the graph obtained by setting the edge length of all the edges
contained inside $P_{i}=B_{i-2}$ and $Q_{i}=V\setminus B_{i+2}$ to 0. More
formally, for all $(u,w)\in E$ such that $u,w\in P_{i}$ or $u,w\in Q_{i}$, we
set $l_{(u,w)}=0$ to obtain $G_{i}$ from $G$. Claim 2 shows that distance
between the $(s_{i},t_{i})$ pairs in $G_{i}$ are within a constant factor of
the distance in $G$.

###### Claim 2

$d_{G}(s_{j},t_{j})/4\leq d_{G_{i}}(s_{j},t_{j})\leq d_{G}(s_{j},t_{j})$ for
all $(s_{j},t_{j})\in T_{i}$.

Proof. $d_{G_{i}}(s_{j},t_{j})\leq d_{G}(s_{j},t_{j})$ follows directly from
construction since each $G_{i}$ is formed by setting the length of some edges
of $G$ to 0. Since $(s_{j},t_{j})\in T_{i}$, we have
$d(s_{j},t_{j})=d(s_{j},v)+d(t_{j},v)\geq 2^{i+1}$ and
$d(s_{j},t_{j})=d(s_{j},v)+d(t_{j},v)\leq 2^{i+2}$. If the shortest path
between $(s_{j},t_{j})$ in $G_{i}$ doesn’t use any vertex in $P_{i}$ or
$Q_{i}$, then $d(s_{j},t_{j})$ remains unchanged and the statement of claim
follows trivially. Suppose the $(s_{j},t_{j})$ shortest path in uses a vertex
in $P_{i}$ or $Q_{i}$. Then we have:

$\displaystyle d(P_{i},s_{j})=d(B_{i-2},s_{j})\geq d(B_{i-2},V\setminus
B_{i-1})\geq 2^{i-1}$ $\displaystyle d(Q_{i},s_{j})=d(V\setminus
B_{i+2},s_{j})\geq d(V\setminus B_{i+2},B_{i+1})\geq 2^{i+1}$ $\displaystyle
d(P_{i},t_{j})=d(B_{i-2},t_{j})\geq d(B_{i-2},V\setminus B_{i-1})\geq 2^{i-1}$
$\displaystyle d(Q_{i},t_{j})=d(V\setminus B_{i+2},t_{j})\geq d(V\setminus
B_{i+2},B_{i+1})\geq 2^{i+1}$

We have
$d_{G_{i}}(s_{j},t_{j})\geq\min\\{d(P_{i},s_{j})+d(P_{i},t_{j}),d(Q_{i},s_{j})+d(Q_{i},t_{j})\\}\geq
2^{i}\geq d_{G}(s_{j},t_{j})/4$ and the claim follows.

We now use Theorem 10 to construct a distribution over (vertex) partitions
$\mathcal{P}$ of $G_{i}$ by setting $\Delta=2^{i-1}$. Suppose the partition is
$(c,\Delta)$-lipschitz for some constant $c>0$. We construct a cut metric
$\mathcal{C}_{i}$ using $\mathcal{P}$ as follows: for each partition
$P=\\{P_{1},P_{2},\ldots,P_{k}\\}\in\mathcal{P}$ with weight $\mu(P)$, we
include $P_{1},P_{2},\ldots,P_{k}$ in $\mathcal{C}_{i}$, each with weight
$\dfrac{\mu(P)\cdot\Delta}{c}$. Claim 3 shows that $\mathcal{C}_{i}$ preserves
distances between the pair of vertices in $T_{i}$.

###### Claim 3

For any $(u,w)\in G_{i}$, we have $\delta_{\mathcal{C}_{i}}(u,w)\leq
d_{G_{i}}(u,w)$. Furthermore, for any $(s_{j},t_{j})\in T_{i}$, we have
$\delta_{\mathcal{C}_{i}}(s_{j},t_{j})\geq\dfrac{d_{G_{i}}(s_{j},t_{j})}{4c}$.

Proof. By the definition of $(c,\Delta)$-lipschitz partition, we have that for
any $u,w\in G_{i}$, probability that $u$ and $w$ are in separate partitions is
at most $\dfrac{c\cdot d_{G_{i}}(u,w)}{\Delta}$. Hence, for any $u,w\in
G_{i}$, we have:

$\delta_{\mathcal{C}_{i}}(u,w)=\displaystyle\sum_{C\in\mathcal{C}_{i}:|C\cap\\{u,w\\}|=1}w(C)=\underset{P\sim\mu}{\mathcal{P}}[P(u)\neq
P(w)]\cdot\dfrac{\Delta}{c}\leq\dfrac{c\cdot
d_{G_{i}}(u,w)}{\Delta}\cdot\dfrac{\Delta}{c}\leq d_{G_{i}}(u,w).$

We now show the other part. Since $d_{G_{i}}(s_{j},t_{j})\geq 2^{i}>\Delta$,
we have that in every partition $P\in\mathcal{P}$, $(s_{j},t_{j})$ are in
different subsets of $P$. This implies that the total weight of cuts in
$\mathcal{C}_{i}$ separating $(s_{j},t_{j})$ is at least $\dfrac{\Delta}{c}$.
Hence,
$\delta_{\mathcal{C}_{i}}(s_{j},t_{j})\geq\dfrac{2^{i-1}}{c}\geq\dfrac{d_{G_{i}}(s_{j},t_{j})}{4c}$
and the claim follows.

###### Claim 4

Let $\mathcal{C}=\displaystyle\bigcup_{i\geq 2}\mathcal{C}_{i}$. For any
$(u,w)\in G$, we have $\delta_{\mathcal{C}}(u,w)\leq 3\cdot d_{G}(u,w)$.
Furthermore, for any $(s_{j},t_{j})\in T$, we have
$\delta_{\mathcal{C}}(s_{j},t_{j})\geq\dfrac{d_{G}(s_{j},t_{j})}{16\cdot c}$.

Proof. By Theorem 10, if an edge has length $0$ in $G_{i}$, then it is not
separated by any cut in $\mathcal{C}_{i}$. Furthermore, any edge $(u,w)\in E$
can be a part of at most three $G_{i}$’s. Hence, using Claim 3, we obtain
$\delta_{\mathcal{C}}(u,w)\leq 3\cdot d_{G}(u,w)$. By Claim 3, for any
$(s_{j},t_{j})\in T_{i}$, $\delta_{\mathcal{C}_{i}}(s_{j},t_{j})\geq
d_{G_{i}}(s_{j},t_{j})/4c$. Using Claim 2, we have $d_{G_{i}}(s_{j},t_{j})\geq
d_{G}(s_{j},t_{j})/4$. Hence,
$\delta_{\mathcal{C}}(s_{j},t_{j})\geq\delta_{\mathcal{C}_{i}}(s_{j},t_{j})\geq
d_{G}(s_{j},t_{j})/16c$.

We have shown that the theorem holds when $d_{G}(v,s_{j})=d_{G}(v,t_{j})$ for
all $(s_{j},t_{j})\in T$. We now prove a more general version of Claim 4 when
$d_{G}(v,s_{j})\neq d_{G}(v,t_{j})$.

###### Claim 5

For any $(s_{j},t_{j})\in T$,
$\delta_{\mathcal{C}}(s_{j},t_{j})\geq\dfrac{d_{G}(s_{j},t_{j})}{16\cdot
c}-3|d_{G}(v,s_{j})-d_{G}(v,t_{j})|$.

Proof. Without loss of generality, we may assume that $d_{G}(v,s_{j})\geq
d_{G}(v,t_{j})$. Let $s^{\prime}_{j}$ be the vertex on a shortest path from
$v$ to $s_{j}$ such that $d_{G}(v,s^{\prime}_{j})=d_{G}(v,t_{j})$. By Claim 4,
we have $\delta_{\mathcal{C}}(s^{\prime}_{j},t_{j})\geq
d_{G}(s^{\prime}_{j},t_{j})/16c$. All the cuts in $\mathcal{C}$ which contain
exactly one of $s^{\prime}_{j}$ and $t_{j}$ contribute to
$\delta_{\mathcal{C}}(s^{\prime}_{j},t_{j})$ and they can be partitioned into
two groups: one in which $s^{\prime}_{j}$ and $s_{j}$ are in the same
partition and the other in which $s_{j}$ and $t_{j}$ are in the same
partition. Let’s call them $\delta_{\mathcal{C}}(s^{\prime}_{j}s_{j},t_{j})$
and $\delta_{\mathcal{C}}(s^{\prime}_{j},s_{j}t_{j})$ respectively. Observe
that,

$\delta_{\mathcal{C}}(s^{\prime}_{j},t_{j})=\delta_{\mathcal{C}}(s^{\prime}_{j}s_{j},t_{j})+\delta_{\mathcal{C}}(s^{\prime}_{j},s_{j}t_{j})\hskip
5.69054pt\text{and}\hskip
5.69054pt\delta_{\mathcal{C}}(s^{\prime}_{j}s_{j},t_{j})\leq\delta_{\mathcal{C}}(s_{j},t_{j}).$

Hence
$\delta_{\mathcal{C}}(s_{j},t_{j})\geq\delta_{\mathcal{C}}(s^{\prime}_{j},t_{j})-\delta_{\mathcal{C}}(s^{\prime}_{j},s_{j}t_{j})$.
By Claim 4, we have,

$\delta_{\mathcal{C}}(s^{\prime}_{j},s_{j}t_{j})\leq\delta_{\mathcal{C}}(s^{\prime}_{j},s_{j})\leq
3d_{G}(s^{\prime}_{j},s_{j})=3|d_{G}(v,s_{j})-d_{G}(v,t_{j})|$

Using $\delta_{\mathcal{C}}(s^{\prime}_{j},t_{j})\geq
d_{G}(s^{\prime}_{j},t_{j})/16c$, we obtain:

$\delta_{\mathcal{C}}(s_{j},t_{j})\geq\delta_{\mathcal{C}}(s^{\prime}_{j},t_{j})-3|d_{G}(v,s_{j})-d_{G}(v,t_{j})|\geq
d_{G}(s_{j},t_{j})/16c-3|d_{G}(v,s_{j})-d_{G}(v,t_{j})|.$

We augment $\mathcal{C}$ by the following single source cuts: let
$V=\\{v_{1},v_{2},\ldots,v_{n}\\}$ such that $d_{G}(v,v_{1})\leq
d_{G}(v,v_{2})\leq\ldots\leq d_{G}(v,v_{n})$. Let
$R_{i}=\\{v_{1},v_{2},\ldots,v_{i}\\}$ and
$w(R_{i})=3\cdot(d_{G}(v_{i+1})-d_{G}(v_{i}))$ for $i=1,2,3,\ldots,n$. Let
$\mathcal{R}=\\{(R_{1},w(R_{1})),\ldots,(R_{n},w(R_{n}))\\}$ and
$\mathcal{C}^{\prime}=\mathcal{C}\cup\mathcal{R}$.

###### Claim 6

For any $(u,w)\in G$, we have $\delta_{\mathcal{C}^{\prime}}(u,w)\leq 6\cdot
d_{G}(u,w)$. Furthermore, for any $(s_{j},t_{j})\in T$, we have
$\delta_{\mathcal{C}^{\prime}}(s_{j},t_{j})\geq d_{G}(s_{j},t_{j})/16c$.

Proof. Observe that $\delta_{R}(u,w)=3\cdot(d_{G}(v,u)-d_{G}(v,w))\leq 3\cdot
d_{G}(u,w)$. Using Claim 5, for any $(u,w)\in E$ we have,
$\delta_{\mathcal{C}^{\prime}}(u,w)=\delta_{\mathcal{C}}(u,w)+\delta_{\mathcal{R}}(u,w)\leq
3\cdot d_{G}(u,w)+3\cdot d_{G}(u,w)=6\cdot d_{G}(u,w)$. Using Claim 5, for any
$(s_{j},t_{j})\in T$ we have
$\delta_{\mathcal{C}^{\prime}}(s_{j},t_{j})=\delta_{\mathcal{C}}(s_{j},t_{j})+\delta_{\mathcal{R}}(s_{j},t_{j})\geq
d_{G}(s_{j},t_{j})/16c-3|d_{G}(v,s_{j})-d_{G}(v,t_{j})|+3|d_{G}(v,s_{j})-d_{G}(v,t_{j})|=d_{G}(s_{j},t_{j})/16c$.

Let $\mathcal{C^{\prime\prime}}=\mathcal{C^{\prime}}/6$. Then for any
$(u,w)\in G$, we have $\delta_{\mathcal{C}^{\prime}}(u,w)\leq d_{G}(u,w)$ and
for any $(s_{j},t_{j})\in T$, we have
$\delta_{\mathcal{C}^{\prime}}(s_{j},t_{j})\geq d_{G}(s_{j},t_{j})/96c$. By
using the equivalence between the cut-metric and $L_{1}$-embedding, we have
the desired $g:V\rightarrow L_{1}$ with $\beta=96c$.

##  7 Constrained Embedding

Let $G=(V,E)$ be a planar graph and $f$ be its infinite face. Let
$V(f)=\\{v_{1},v_{2},\ldots,v_{l}=v_{1}\\}$ be the vertices on the cycle of
$f$ in clockwise ordering. Suppose that we are given a cut-metric
$\mathcal{C}=\\{(C_{1},w_{1}),(C_{2},w_{2}),\ldots,(C_{m},w_{m})\\}$ w.r.t
$V(f)$ such that each cut $C_{i}\subseteq V(f)$ corresponds to a contiguous
subset of vertices on cycle of $f$. We say that $\mathcal{C}$ is a cut-metric
w.r.t $f$. Suppose we wish to extend $\mathcal{C}$ to $V$, i.e. we wish to
find a cut-metric $\mathcal{D}$ w.r.t $V$ 222i.e. each cut in $\mathcal{D}$
corresponds to a partition of $V$ such that
$\mathcal{D}=\cup_{i=1}^{m}\mathcal{D}_{i}$,
$\mathcal{D}_{i}=\\{(D^{1}_{i},w^{1}_{i}),(D^{2}_{i},w^{2}_{i}),\ldots,(D^{k}_{i},w^{k_{i}}_{i})\\}$,
$\sum_{j=1}^{k_{i}}w^{j}_{i}=w_{i}$, $C_{i}\subseteq D^{j}_{i}$,
$(V(f)\setminus C_{i})\cap D^{j}_{i}=\emptyset$ for $i=1,2,\ldots,m$, and
$\delta_{\mathcal{D}}(u,v)\leq d_{G}(u,v)$ for $(u,v)\in E$. We call
$\mathcal{D}$ an extension of $\mathcal{C}$ to $G$ w.r.t face $f$. Lemma 4
shows that this is always possible if $\delta_{\mathcal{C}}(u,v)\leq
d_{G}(u,v)$ for $u,v\in V(f)$. Note that by definition of $\mathcal{D}$, it
follows that $\delta_{\mathcal{D}}(u,v)=\delta_{\mathcal{C}}(u,v)$ for all
$u,v\in V(f)$.

###### Lemma 4

Let $G=(V,E)$ be a planar graph and $f$ be its infinite face. Let
$\mathcal{C}$ be a cut-metric w.r.t face $f$ such that
$\delta_{\mathcal{C}}(u,v)\leq d_{G}(u,v)$ for all $u,v\in f$ and $C_{i}$
corresponds to a contiguous set of vertices on $f$. Then there exists an
extension $\mathcal{D}$ of $\mathcal{C}$ to $G$ w.r.t $f$.

Proof. We set up a multicommodity flow instance in the planar dual of $G$ such
that all the sink-source pairs are on the infinite face and the cut-condition
is satisfied. We use Theorem 1 to find a feasible flow and the fact that
circuits in a planar graph correspond to (central) cuts in the (planar) dual
to finish the proof. Let
$\mathcal{C}=\\{(C_{1},w_{1}),(C_{2},w_{2}),\ldots,(C_{m},w_{m})\\}$,
$V(f)=\\{v_{1},v_{2},\ldots,v_{l}=v_{1}\\}$ be the vertices on cycle of $f$
and $e_{i}=(v_{i},v_{i+1}),1\leq i\leq l-1$ be the edges. Let
$G^{D}=(V^{D},E^{D})$ be the planar dual of $G$ and $f^{D}$ be the dual vertex
corresponding to the infinite face $f$. For each edge $e^{D}\in E^{D}$, we set
the capacity of edge $e^{D}$ as $c(e^{D}):=l(e)$. Let
$e^{D}_{1},\ldots,e^{D}_{l-1}$ be the edges incident on $f^{D}$ in $G^{D}$. We
split the vertex $f^{D}$ into $l-1$ vertices $f^{D}_{1},\ldots,f^{D}_{l-1}$
such that $e^{D}_{i}$ is the only edge incident on vertex $f^{D}_{i}$. Note
that each of the vertices $f^{D}_{i}$ lie on a single face of $G^{D}$.

Each $C_{i}\in\mathcal{C}$ separates exactly two of the edges on $f$, say
$e_{j},e_{k}$ (since each $C_{i}$ is a contiguous subset of vertices on $f$).
We set up a multicommodity flow instance in $G^{D}$ as follows: for each
$C_{i}\in\mathcal{C}$, we introduce a demand edge $(f^{D}_{j},f^{D}_{k})$ with
demand value $w_{i}$. By Lemma 1, to check that the cut-condition is satisfied
for the instance, we only need to verify it for central cuts. In this case,
each central cut corresponds to a $(v_{i},v_{j})$ path in $G$ for some $1\leq
i<j\leq l-1$. The total capacity of the supply edges across such a cut is the
length of shortest path between $(v_{i},v_{j})$ in $G$ and total demand across
such a cut is equal to $\delta_{\mathcal{C}}(v_{i},v_{j})$. Since for each
$v_{i},v_{j}\in V(f)$, $\delta_{\mathcal{C}}(u,v)\leq d_{G}(u,v)$, the cut-
condition is satisfied and we have a feasible flow satisfying all the demands.
Each flow path in $G^{D}$ corresponds to a set of edges in $G$, which in turn
correspond to a cut in $G$ (recall that a circuit in a planar graph
corresponds to a cut in its (planar) dual). Let $\mathcal{D}$ be such a set of
cuts. Since the total flow through any edge in $G^{D}$ is at most
$c(e^{D})=l(e)$, the total weight of cuts in $G$ separating $e$ is at most
$l(e)$. Since each $D\in\mathcal{D}$ corresponds to a path in
$G^{D},D\cap(V(f)\setminus C_{i})=\emptyset$. Hence $\mathcal{D}$ is a valid
extension of $\mathcal{C}$ and this completes the proof of the lemma.

###### Theorem 12

Let $G=(V,E)$ be a planar graph with edge-length
$l:E\rightarrow\mathbf{R}_{\geq 0}$ and $F$ be its set of faces. Furthermore,
let $S$ be a $\alpha$-loose cycle and $f_{2}\in F$ be the unique non-geodesic
face contained inside $\overline{R(S)}$. Let $G_{1}=(V_{1},E_{1})\subseteq G$
be the graph induced by the vertices and edges in $\overline{R(S)}$ and
$F_{1}$ be the set of faces of $G_{1}$333note that $S,f_{2}\in F_{1}$ and
$\overline{R(S)}$ is the closed region bounded by cycle $S$. Let $\mathcal{C}$
be a cut-metric w.r.t $S$ and $\alpha\geq 12\beta$ be a constant such that
$d_{G}(u,v)/\alpha\leq\delta_{\mathcal{C}}(u,v)\leq d_{G}(u,v)$ for $u,v\in
S$444$\beta$ is the constant from Theorem 11. Then there exists an extension
of $\mathcal{C}$ to $G_{1}$, say $\mathcal{Z}$, such that for all $u,v\in f\in
F_{1}$, we have $d_{G}(u,v)/\alpha\leq\delta_{\mathcal{Z}}(u,v)\leq
d_{G}(u,v)$.

Proof. As mentioned before, we abuse notation and let $S$ also denote the set
of vertices and edges incident on the cycle $S$. Consider two copies of
$G_{1}$, say $H_{1}=(V_{1},E_{1})$ and $H_{2}=(V_{1},E_{1})$ with length
functions $l_{1},l_{2}$ defined as follows: $l_{1}(u,v):=l(u,v)$ for all
$(u,v)\in S$ and $l(u,v)/\alpha$ otherwise; $l_{2}(u,v):=0$ for all $(u,v)\in
S$ and $l(u,v)$ otherwise. By definition of a $\alpha$-loose cycle, it
immediately follows that for any $u,v\in S$, $d_{H_{1}}(u,v)\geq d_{G}(u,v)$.
Lemma 4 shows that the cuts in $\mathcal{C}$ can be extended to $H_{1}$ such
that $\delta_{\mathcal{C}}(u,v)\leq d_{H_{1}}(u,v)$ for each $(u,v)\in E_{1}$.
Let this cut-metric be $\mathcal{C}^{\prime}$. For notational convenience, we
create an (equivalent) $L_{1}$ embedding $h:V_{1}\rightarrow L_{1}$ from
$\mathcal{C}^{\prime}$ by forming a new coordinate for each
$C\in\mathcal{C}^{\prime}$ and setting $h(u)=0$ if $u\in C$ and $w_{C}$
otherwise.

Consider the graph $H_{2}$ with metric $l_{2}$. Since the length of all the
edges in $S$ have been set to zero in $l_{2}$, we may treat all the vertices
on the cycle $S$ as a single node, say $v_{S}$. If $d_{H_{2}}(u,v)\neq
d_{G}(u,v)$ for some $u,v\in V_{1}$, then it must be the case that
$d_{H_{2}}(u,v)=d_{H_{2}}(u,v_{S})+d_{H_{2}}(v_{S},u)$. Let $T_{1}$ be the set
of all pairs of vertices $(u,v)$ in $H_{2}$ such that the shortest path
between $u$ and $v$ in $H_{2}$ uses the vertex $v_{S}$. We use Theorem 11 to
find an embedding $g_{1}:V_{1}\rightarrow L_{1}$ such that
$d_{H_{2}}(u,v)/\beta\leq||g_{1}(u)-g_{1}(v)||\leq d_{H_{2}}(u,v)$ for all
$(u,v)\in T_{1}$.

Let $T_{2}$ be the set of all geodesic pairs in $G_{2}$ (see Section 5 for the
definition of geodesic pairs). In this case, we use Theorem 9 to find an
embedding $g_{2}:V_{1}\rightarrow L_{1}$ such that
$d_{H_{2}}(u,v)/21\leq||g_{2}(u)-g_{2}(v)||\leq d_{H_{2}}(u,v)$ for all
$(u,v)\in T_{2}$. Let $T_{3}$ be the set of all pair of vertices $(u,v)$ such
that $u,v\in f_{2}$ i.e. the set of all pairs of points on the non-geodesic
face $f_{2}$. We use Theorem 3 to find an embedding $g_{3}:V_{1}\rightarrow
L_{1}$ such that $||g_{3}(u)-g_{3}(v)||=d_{H_{2}}(u,v)$ for all $(u,v)\in
T_{3}$ and $||g_{3}(u)-g_{3}(v)||\leq d_{H_{2}}(u,v)$ for all $(u,v)\in
E_{1}$.

Let $g=(g_{1}+g_{2}+g_{3})/3$. Since $||g_{i}(u)-g_{i}(v)||\leq
d_{H_{2}}(u,v)$ for $i=1,2,3$, we have $||g_{i}(u)-g_{i}(v)||\leq
d_{H_{2}}(u,v)$ for $(u,v)\in E_{1}$. Let $T$ be the set of all pair of
vertices $u,v$ which lie on the same face, i.e. $T=\\{(u,v)|u,v\in f\text{ for
some}f\in F_{1}\\}$. Since $f_{2}$ is the only non-geodesic face in
$F_{1}\setminus S$, for any $u,v\in T$, the shortest path between $u,v$ in
$H_{2}$ either goes through $v_{S}$ or $(u,v)$ is a geodesic pair or $u,v\in
f_{2}$. Hence, $T\subseteq T_{1}\cup T_{2}\cup T_{3}$ and we have
$||g(u)-g(v)||\geq d_{H_{2}}(u,v)/\beta_{1}$ where
$\beta_{1}=\max\\{3\cdot\beta,3\cdot 21,3\cdot 1\\}=3\beta$. Let
$z:=h+\dfrac{\alpha-1}{\alpha}\cdot g$.

###### Claim 7

$||z(u)-z(v)||\leq l(u,v)$ for $(u,v)\in E_{1}$.

Proof. Consider an edge $(u,v)\in S$. Since $l_{1}(u,v)=l(u,v)$ and
$l_{2}(u,v)=0$ we have:

$||z(u)-z(v)||=||h(u)-h(v)||+\dfrac{\alpha-1}{\alpha}\cdot||g(u)-g(v)||\leq
l_{1}(u,v)+\dfrac{\alpha-1}{\alpha}\cdot l_{2}(u,v)=l(u,v)$

Now consider an edge $(u,v)\in E_{1}\setminus S$. Since
$l_{1}(u,v)=\dfrac{l(u,v)}{\alpha}$ and $l_{2}(u,v)=l(u,v)$,

$||z(u)-z(v)||=||h(u)-h(v)||+\dfrac{\alpha-1}{\alpha}\cdot||g(u)-g(v)||\leq\dfrac{1}{\alpha}\cdot
l(u,v)+\dfrac{\alpha-1}{\alpha}\cdot l(u,v)=l(u,v).$

###### Claim 8

$||z(u)-z(v)||\geq\dfrac{d_{G}(u,v)}{\alpha}$ for $(u,v)\in T$.

Proof. Let $(u,v)\in T$. We consider two cases depending on whether the
shortest $u,v$ path in $H_{2}$ uses the vertex $v_{S}$. If the shortest $u,v$
path doesn’t use the vertex $v_{S}$, then we have $d_{G}(u,v)=d_{H_{2}}(u,v)$
and,

$||z(u)-z(v)||\geq\dfrac{\alpha-1}{\alpha}\cdot||g(u)-g(v)||\geq\dfrac{1}{2}\cdot\dfrac{d_{H_{2}}(u,v)}{3\beta}\geq\dfrac{d_{G}(u,v)}{\alpha}$

Suppose that the shortest $u,v$ path uses the vertex $v_{S}$. Recall that
$v_{S}$ was formed by identifying all the vertices in $S$ as a single vertex.
We uncontract $v_{S}$ and let $u-u_{1}-v_{1}-v$ be the shortest $u,v$ path
where $u_{1},v_{1}\in S$ are the first and last vertices of $S$ on the path.
Note that the shortest $u_{1}$-$v_{1}$ path may contain some of the vertices
in $G\setminus G_{1}$. Since $\delta_{\mathcal{C}}(u_{1},v_{1})\geq
d_{G}(u_{1},v_{1})/\alpha$, we have,

$||h(u)-h(v)||\geq\dfrac{d_{G}(u_{1},v_{1})}{\alpha}-d_{H_{1}}(u_{1},u)-d_{H_{1}}(v_{1},v).$

Using the fact that $\alpha\geq 12\beta=4\beta_{1}$, we have:

$||z(u)-z(v)||\geq\dfrac{d_{G}(u_{1},v_{1})}{\alpha}-d_{H_{1}}(u_{1},u)-d_{H_{1}}(v_{1},v)+\dfrac{\alpha-1}{\alpha}\cdot\dfrac{d_{H_{2}}(u,u_{1})+d_{H_{2}}(v_{1},v)}{\beta_{1}}$

$\hskip
65.44133pt\geq\dfrac{d_{G}(u_{1},v_{1})-d_{G}(u_{1},u)-d_{G}(v_{1},v)}{\alpha}+\dfrac{1}{2}\cdot\dfrac{d_{G}(u,u_{1})+d_{G}(v_{1},v)}{\beta_{1}}$

$\hskip
65.44133pt\geq\dfrac{d_{G}(u,u_{1})+d_{G}(u_{1},v_{1})+d_{G}(v_{1},v)}{\alpha}$

$\hskip 65.44133pt=\dfrac{d_{G}(u,v)}{\alpha}$.

Using the equivalence of cut-metric and $L_{1}$-embedding, we can construct a
cut-metric $\mathcal{Z}$ from $z:V_{1}\rightarrow L_{1}$ satisfying the
conditions of the theorem.

##  8 Putting Everything Together

###### Theorem 13

Let $G=(V,E)$ be a planar graph with length function
$l:E\rightarrow\mathbb{R}_{\geq 0}$, $F$ be its set of faces and
$T=\\{(u,v)|u,v\in f\in F\\}$. Then there exists a $z:V\rightarrow L_{1}$ such
that $||z(u)-z(v)||\leq l(u,v)$ for $(u,v)\in E$ and $||z(u)-z(v)||\geq
d_{G}(u,v)/c$ for $(u,v)\in T$, where $c=144\beta^{2}$.

Proof. We prove the theorem by using induction on the number of vertices. We
first compute a $\alpha$-good length function $l^{\prime}$ by setting
$\alpha=12\beta$ in Theorem 7. If there are no non-geodesic faces w.r.t
$l^{\prime}$, then we use Theorem 9 to get an $L_{1}$ embedding with
distortion at most 21. If there exists a non-geodesic face w.r.t $l^{\prime}$,
we use the decomposition guaranteed by $\alpha$-good length function and find
an innermost non-geodesic $\alpha$-loose face. Let $G_{1}=(V_{1},E_{1})$ be
the graph obtained by removing all the vertices in $I(S_{f})$. Since $f$ is
non-geodesic w.r.t $l^{\prime}$, there exists a vertex in $I(S_{f})$. Hence,
the number of vertices in $G_{1}$ is strictly smaller than $G$ and we
inductively compute an embedding $z_{1}:V\rightarrow L_{1}$ satisfying the
conditions of the theorem. Using the equivalence between $L_{1}$-embedding and
cut-metric, we compute a cut-metric equivalent to $z_{1}$ , say
$\mathcal{Z}_{1}$. Let $\mathcal{Z}_{1}^{f}$ be the cut-metric induced by
$\mathcal{Z}_{1}$ on the cycle $S_{f}$. We use Theorem 12 to compute a cut-
metric which extends $\mathcal{Z}_{1}^{f}$ to vertices in $G\setminus G_{1}$,
say $\mathcal{Z}_{f}$. We obtain the final cut-metric by setting
$\mathcal{Z}=(\mathcal{Z}_{1}\setminus\mathcal{Z}_{1}^{f})\cup\mathcal{Z}_{f}$.
Let $z:V\rightarrow L_{1}$ be the equivalent embedding to $\mathcal{Z}$. By
induction hypothesis and statement of Theorem 12, $||z(u)-z(v)||\leq
l^{\prime}(u,v)$ for $(u,v)\in E$ and $||z(u)-z(v)||\geq
d_{G^{\prime}}(u,v)/\alpha$ for $(u,v)\in T$, where $d_{G^{\prime}}$ is the
shortest path metric on $G$ w.r.t $l^{\prime}$. The statement of the theorem
then follows by noting that $l^{\prime}$ is constructed by reducing the length
of edges w.r.t $l$ by a factor of at most $\alpha$.

##  9 Conclusions

In this paper, we proved a $\mathcal{O}(1)$ flow-cut gap when $G$ is planar
and both end points of every demand edge is incident on one of the faces.
Although our result does not directly imply any bounds on the (half)-integral
flow-cut gap, we believe that it should be possible to exploit the laminar
structure of flows in such instances to prove such a bound. Inductive
arguments have been used successfully for proving better flow-cut gaps for
planar instances, for example series-parallel graphs [3] and $k$-outer planar
graphs [4]. We believe that the techniques developed in this paper could be
useful for extending such an approach to a more general setting.

## References

  * [1] Jean Bourgain.  On lipschitz embedding of finite metric spaces in hilbert space.  Israel Journal of Mathematics, 52(1):46–52, 1985.
  * [2] Amit Chakrabarti, Lisa Fleischer, and Christophe Weibel.  When the cut condition is enough: A complete characterization for multiflow problems in series-parallel networks.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 19–26. ACM, 2012.
  * [3] Amit Chakrabarti, Alexander Jaffe, James R Lee, and Justin Vincent.  Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums.  In Foundations of Computer Science, 2008. FOCS’08. IEEE 49th Annual IEEE Symposium on, pages 761–770. IEEE, 2008.
  * [4] Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair.  Embedding k-outerplanar graphs into l1.  SIAM Journal on Discrete Mathematics, 20(1):119–136, 2006.
  * [5] Arnold Filtser.  A face cover perspective to ℓ 1 embeddings of planar graphs.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1945–1954. SIAM, 2020.
  * [6] Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair.  Cuts, trees and ℓ 1-embeddings of graphs.  Combinatorica, 24(2):233–269, 2004.
  * [7] Philip Klein, Serge A Plotkin, and Satish Rao.  Excluded minors, network decomposition, and multicommodity flow.  In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 682–690, 1993.
  * [8] Robert Krauthgamer, James R Lee, and Havana Rika.  Flow-cut gaps and face covers in planar graphs.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 525–534. SIAM, 2019.
  * [9] Nikhil Kumar.  Multicommodity flows in planar graphs with demands on faces.  In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [10] Nathan Linial, Eran London, and Yuri Rabinovich.  The geometry of graphs and some of its algorithmic applications.  Combinatorica, 15(2):215–245, Jun 1995.
  * [11] Haruko Okamura and Paul D Seymour.  Multicommodity flows in planar graphs.  Journal of Combinatorial Theory, Series B, 31(1):75–81, 1981.
  * [12] Satish Rao.  Small distortion and volume preserving embeddings for planar and euclidean metrics.  In Proceedings of the fifteenth annual symposium on Computational geometry, pages 300–306. ACM, 1999.
  * [13] Alexander Schrijver.  Combinatorial optimization: polyhedra and efficiency, volume 24.  Springer Science & Business Media, 2003.
  * [14] Paul D Seymour.  On odd cuts and plane multicommodity flows.  Proceedings of the London Mathematical Society, 3(1):178–192, 1981\.
  * [15] David P Williamson and David B Shmoys.  The design of approximation algorithms.  Cambridge university press, 2011.