% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
% The amsthm package provides extended theorem environments
%\usepackage{amsthm}
% The amsmath package provides more useful stuff
\usepackage{amsmath}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% custom math macros
\newcommand{\darts}[1]{\overleftrightarrow{#1}}
\newcommand{\arc}[1]{\overrightarrow{#1}}
\newcommand{\antiarc}[1]{\overleftarrow{#1}}
\newcommand{\rightof}{\preceq}
\newcommand{\leftof}{\succeq}

\begin{document}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{Lattices and maximum flow algorithms\\ in planar graphs}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author{Jannik Matuschke \and Britta Peis}

\address{Technische Universit\"at Berlin, 
    Institut f\"ur Mathematik\\ 
    Stra\ss e des 17.~Juni 136,
    10623~Berlin, Germany
}

%\begin{abstract}
% We show that the left/right relation on the set of simple $s$-$t$-paths in a planar graph \cite{Kl05} induces a so-called submodular lattice. We prove that this lattice is furthermore consecutive if the graph is $s$-$t$-planar, thus showing that the uppermost path algorithm of Ford and Fulkerson \cite{FF56} is a special case of a general two-phase greedy algorithm for lattice polyhedra (\cite{FP08}, \cite{Fr99}, \cite{HS78}) that even works with certain weight functions on the paths. We also show that submodularity and consecutivity cannot be achieved simultaneously by any partial order if the graph is not $s$-$t$-planar, providing a characterization of this class of planar graphs.
%\end{abstract}

\begin{keyword}
Lattice polyhedra \sep Flows in planar graphs \sep Left/right relation
\end{keyword}

\end{frontmatter}

\vspace{-0.5cm}
\section{Introduction}
\vspace{-0.5cm}

The special case of flows in planar graphs has always played a significant role in network flow theory. The predecessor of Ford and Fulkerson's well-known path augmenting algorithm -- and actually the first combinatorial flow algorithm at all -- was a special version for $s$-$t$-planar networks, i.e., those networks where $s$ and $t$ can be embedded adjacent to the infinite face \cite{FF56}. The basic idea of this \emph{uppermost path algorithm} is to iteratively augment flow along the ``uppermost'' non-saturated $s$-$t$-path in the planar embedding of the network. In 2006, Borradaile and Klein \cite{BK06} established an intuitive generalization of this algorithm to arbitrary planar graphs, which relies on a partial order on the set of $s$-$t$-paths in the graph, called the \emph{left/right relation}.

We connect these results from planar network flow theory with another field of combinatorial optimization, the optimization on lattice structures. In 1978, Hoffman and Schwartz introduced the notion of \emph{lattice polyhedra} \cite{HS78}, a generalization of Edmond's polymatroids that is based on lattices, and proved total dual integrality of the corresponding inequaltity systems if certain additional properties hold, which are defined below.

\begin{defn}
 Let $E$ be a finite set, $\mathcal{L} \subseteq 2^{E}$ and $\preceq$ be a partial order on $\mathcal{L}$. Then $(\mathcal{L}, \preceq)$ is a \emph{lattice} if for any pair of elements $S, T \in \mathcal{L}$, there is a unique largest common lower bound $S \wedge T$ called \emph{meet} and a unique least common upper bound $S \vee T$ called \emph{join}. A lattice is \emph{submodular} if $(S \wedge T) \cap (S \vee T) \subseteq S \cap T$ and $(S \wedge T) \cup (S \vee T) \subseteq S \cup T$ for all $S, T \in \mathcal{L}$. It is \emph{consecutive} if $S \cap U \subseteq T$ for all $S, T, U \in \mathcal{L}$ with $S \preceq T \preceq U$.
\end{defn}

Based on the total dual integrality result by Hoffman and Schwartz, several different versions of two-phase-greedy algorithms were developed by Frank \cite{Fr99} and Faigle and Peis \cite{FP08} in order to solve linear programming problems on lattice polyhedra like the packing problem

\vspace{-0.5cm}
\[\max\ \left\{r^{T}y ~:~ y \in \mathbb{R}^{\mathcal{L}}_{+}, \sum_{S \in \mathcal{L} : e \in S} y(S) \leq c(e) ~ \forall e \in E\right\}\]
\vspace{-0.5cm}
	
and its dual if $\mathcal{L}$ is a submodular and consecutive lattice and the objective function $r$ is supermodular and monotone\footnote{These requirements on the weight function $r$ are explained in \cite{FP08}.}. Clearly, the path formulation of the maximum flow problem is a special case of the general packing problem.

\paragraph*{Results:}
We show that the left/right relation induces a submodular lattice on the set of simple $s$-$t$-paths in a planar graph. If the network is $s$-$t$-planar, this lattice is also consecutive, thus meeting all requirements of Hoffman and Schwartz' framework. This implies that Ford and Fulkerson's uppermost path algorithm is a special case of the two-phase greedy algorithm on lattice polyhedra (with $r \equiv 1$). Even more, this algorithm can also solve a weighted flow problem, if the weights on the paths are supermodular and monotone. An additional result will show that whenever the graph is just planar but not $s$-$t$-planar, there is no partial order on the paths that induces a consecutive and submodular lattice.

\vspace{-0.5cm}
\section{The left/right relation and the path lattice}
\vspace{-0.5cm}

We are given a directed graph $G = (V, E)$ with a fixed planar embedding, a fixed infinite face $f_{\infty}$ and two designated vertices $s, t \in V$. In our setting, paths are allowed to use edges in either direction\footnote{The resulting lattice can later be restricted to directed paths, maintaining all its properties.}, i.e., every path $P$ is represented by a subset of $\darts{E} := \{\arc{e}, \antiarc{e} : e \in E\}$ such that $\arc{e} \in P$ if $P$ uses the edge $e$ in its forward direction and $\antiarc{e} \in P$ if $P$ uses $e$ in backward direction. We denote the set of all simple $s$-$t$-paths in $G$ by $\mathcal{P} \subseteq 2^{\darts{E}}$. We will analyze a partial order on $\mathcal{P}$ called left/right relation and show that it induces a submodular lattice (cf. Theorem \ref{thm_general_planar}), which is furthermore consecutive if the embedding is $s$-$t$-planar (cf. Theorem \ref{thm_stplanar}). Finally, we will show that there is no partial order on $\mathcal{P}$ that induces a consecutive and submodular lattice, if there is no $s$-$t$-planar embedding of the graph (cf. Theorem \ref{thm_characterization}).

\vspace{-0.5cm}
\subsection{The left/right relation}
\vspace{-0.5cm}

The left/right relation as presented in this subsection is a partial order on $\mathcal{P}$ due to Klein \cite{Kl05}. We consider the \emph{cycle space} of $G$, i.e., the subspace of all those vectors in $\mathbb{R}^{E}$ that fulfill flow conservation at all vertices. The elements of the cycle space are called \emph{circulations}. The vectors corresponding to the clockwise boundary of the non-infinite faces in the embedded graph form a basis of the cycle space. Thus, for every circulation, there is a unique face potential, i.e., an assignment of numbers to the faces corresponding to the circulation. We say a circulation is \emph{clockwise} if the corresponding face potential is non-negative.

A path $P \in \mathcal{P}$ induces a vector $\delta_{P} \in \mathbb{R}^{E}$ by $\delta_{P}(e) = 1$ if $\arc{e} \in P$, $\delta_{P}(e) = -1$ if $\antiarc{e} \in P$ and $\delta_{P}(e) = 0$ otherwise. It is easy to see that for two paths $P, Q \in \mathcal{P}$, the vector $\delta_{P} - \delta_{Q}$ is a circulation. We say that \emph{$P$ is left of $Q$} and write $P \leftof Q$ if this circulation is clockwise. It can be easily verified that the left/right relation arising from this definition is a partial order on $\mathcal{P}$. More details on the definition can be found in \cite{BK06} and \cite{Ma09}.

\vspace{-0.5cm}
\subsection{The path lattice in planar graphs in general}
\vspace{-0.5cm}

We give a short description of how to obtain a largest common lower bound of two paths $P, Q \in \mathcal{P}$ with respect to the left/right relation. Let $\phi$ be the face potential corresponding to the circulation $\delta_{P} - \delta_{Q}$. For \mbox{$S^{+} := \{f \in V^{\ast} : \phi(f) > 0\}$}, we define $\delta^{P \wedge Q} := \delta_{P} - \sum_{f \in S^{+}} \phi(f) \delta_{f}$. The vector $\delta^{P \wedge Q}$ induces a set of darts
\[D^{P \wedge Q} := \{\arc{e} : \delta^{P \wedge Q}(e) = 1\} \cup \{\antiarc{e} : \delta^{P \wedge Q}(e) = -1\}.\] Intuitively speaking, the set $D^{P \wedge Q}$ is obtained by subtracting the ``clockwise part'' of the circulation $P - Q$ from $P$. Unfortunately, this set is not necessarily a simple path. However, by flow decomposition, it can be decomposed into a path and several cycles, which can be shown to be clockwise. From this, it can be derived that the path actually is the meet of $P$ and $Q$. Analogously, one can construct a set $D^{P \vee Q}$ containing the join of $P$ and $Q$. A detailed proof of this result can be found in \cite{Ma09}.

\begin{thm}\label{thm_general_planar}
 $(\mathcal{P}, \preceq)$ is a submodular lattice with $P \wedge Q$ being the unique simple $s$-$t$-path contained in $D^{P \wedge Q}$ and $P \vee Q$ being the unique simple $s$-$t$-path contained in $D^{P \vee Q}$.
\end{thm}

Note that the path lattice is not consecutive in general.

\vspace{-0.5cm}
\subsection{The path lattice in $s$-$t$-planar graphs}
\vspace{-0.5cm}

In case the embedding of $G$ is $s$-$t$-planar, meet and join of the path lattice can be characterized in a more convenient way than in the general case, and even more, the lattice turns out to be consecutive. As already mentioned, Ford and Fulkerson used the existence of a unique uppermost path from $s$ to $t$ in every $s$-$t$-planar graph for their uppermost path algorithm. Formally, this uppermost path (and likewise a lowermost path) can be defined as the unique path with the infinite face to the left (right) of all of its elements.

For some paths $P, Q \in \mathcal{P}$ let the subgraph of $G$ containing only the edges of $P$ and $Q$ be denoted by $G[E(P \cup Q)]$. It can be shown that $P$ is left of $Q$ if and only if $P$ is the uppermost path in $G[E(P \cup Q)]$ (or, equivalently, $Q$ is the lowermost path in $G[E(P \cup Q)]$). Given this characterization of the left/right relation in $s$-$t$-planar graphs, it is easy to verify that if $P$ and $Q$ are incomparable, join and meet are also the uppermost and lowermost paths of $G[E(P \cup Q)]$. In order to show consecutivity, one verifies that $P \leftof Q \leftof R$ implies that $P$ and $R$ are uppermost and lowermost path of $G[E(P \cup Q \cup R)]$ as well, and thus any dart in $d \in P \cap R$ is a loop in the dual and, by cycle/cut duality, a one-element $s$-$t$-cut in the primal graph. This implies $d \in Q$.

\begin{thm}\label{thm_stplanar}
 If the embedding of $G$ is $s$-$t$-planar, $(\mathcal{P}, \rightof)$ is a consecutive and submodular lattice with $P \wedge Q$ being the lowermost path in $G[E(P \cup Q)]$ and $P \vee Q$ being the uppermost path in $G[E(P \cup Q)]$.
\end{thm}

As a direct corollary, Ford and Fulkerson's uppermost path algorithm \cite{FF56} turns out to be a special case of Phase 1 of the two-phase greedy algorithm for submodular lattice polyhedra \cite{FP08}.

\vspace{-0.5cm}
\subsection{The negative result and a characterization of $s$-$t$-planar graphs}
\vspace{-0.5cm}

As pointed out above, the path lattice is not consecutive on planar graphs in general. It can actually be shown that no graph that is planar but not $s$-$t$-planar can be equipped with a partial order of the paths that achieves consecutivity and submodularity at the same time. Together with the above positive result for $s$-$t$-planar graphs, we achieve the following characterization of $s$-$t$-planar graphs.

\begin{thm}\label{thm_characterization}
 A graph is $s$-$t$-planar if and only if it is planar and there is a partial order on the set of its $s$-$t$-paths that induces a consecutive and submodular lattice.
\end{thm}

\emph{Sketch of proof.} Consider the two graphs $K_{5}^{-}$ and $K_{3,3}^{-}$ that are obtained from the Kuratowski graphs $K_{5}$ and $K_{3,3}$ by deleting the edge connecting $s$ and $t$. It can be shown by very elementary arguments that for both $K_{5}^{-}$ and $K_{3,3}^{-}$ there is no partial order of the $s$-$t$-paths that induces a submodular and consecutive lattice. The result then follows by applying Kuratowski's Theorem.

\vspace{-0.5cm}
\section{Conclusion}
\vspace{-0.5cm}

We provided an extensive analysis of the left/right relation on the set of $s$-$t$-paths in a planar graph. The relation induces a submodular lattice, which is even consecutive if the graph is $s$-$t$-planar. The latter result implies that the uppermost path algorithm by Ford and Fulkerson is a special case of the two-phase greedy algorithm for packing problems on submodular lattice polyhedra. We furthermore showed that submodularity and consecutivity cannot be achieved simultaneously by any partial order if the graph is not $s$-$t$-planar, thus providing a characterization of this special class of planar graphs.

\begin{thebibliography}{00}

\bibitem{BK06}
G.~Borradaile, P.~Klein, An {$O(n\log n)$} algorithm for maximum {$st$}-flow in
  a directed planar graph, in: Proceedings of the {S}eventeenth {A}nnual
  {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms, ACM, New York, 2006, pp.
  524--533.

\bibitem{FP08}
U.~Faigle, B.~Peis, Two-phase greedy algorithms for some classes of
  combinatorial linear programs, in: Proceedings of the {N}ineteenth {A}nnual
  {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms, ACM, New York, 2008, pp. 161--166.

\bibitem{FF56}
L.~R. Ford, Jr., D.~R. Fulkerson, Maximal flow through a network, Canadian
  Journal of Mathematics. Journal Canadien de Math\'ematiques 8 (1956)

\bibitem{Fr99}
A.~Frank, Increasing the rooted-connectivity of a digraph by one, Mathematical
  Programming 84~(3, Ser. B) (1999) 565--576.
  399--404.

\bibitem{HS78}
A.~J. Hoffman, D.~E. Schwartz, On lattice polyhedra, in: A.~Hajnal, V.~T. S\'os
  (Eds.), {P}roceedings of the {F}ifth {H}ungerian {C}olloquium on
  {C}ombinatorics, {V}ol. {I}, Vol.~18 of Colloquia mathematica Societatis
  J\'anos Bolyai, North-Holland, Amsterdam, 1978, pp. 593--598.

\bibitem{Kl05}
P.~N. Klein, Multiple-source shortest paths in planar graphs, in: Proceedings
  of the {S}ixteenth {A}nnual {ACM}-{SIAM} {S}ymposium on {D}iscrete
  {A}lgorithms, ACM, New York, 2005, pp. 146--155.

\bibitem{Ma09}
J.~Matuschke, Lattices and maximum flow algorithms in planar graphs, Diploma
  thesis, TU Berlin (2009).
  
\end{thebibliography}

\end{document}

