math-research/papers/level_switching/paper.tex

%% filename: amsart-template.tex
%% version: 1.1
%% date: 2014/07/24
%%
%% American Mathematical Society
%% Technical Support
%% Publications Technical Group
%% 201 Charles Street
%% Providence, RI 02904
%% USA
%% tel: (401) 455-4080
%%      (800) 321-4267 (USA and Canada only)
%% fax: (401) 331-3842
%% email: tech-support@ams.org
%%
%% Copyright 2008-2010, 2014 American Mathematical Society.
%%
%% This work may be distributed and/or modified under the
%% conditions of the LaTeX Project Public License, either version 1.3c
%% of this license or (at your option) any later version.
%% The latest version of this license is in
%%   http://www.latex-project.org/lppl.txt
%% and version 1.3c or later is part of all distributions of LaTeX
%% version 2005/12/01 or later.
%%
%% This work has the LPPL maintenance status `maintained'.
%%
%% The Current Maintainer of this work is the American Mathematical
%% Society.
%%
%% ====================================================================

%     AMS-LaTeX v.2 template for use with amsart
%
%     Remove any commented or uncommented macros you do not use.

\documentclass{amsart}

\usepackage{hyperref}
\usepackage{enumitem}
\usepackage{graphicx}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\newtheorem{observation}[theorem]{Observation}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}

\begin{document}

\title{Level Switching}

%    Remove any unused author tags.

%    author one information
\author{Eric Bauerfeld}
\address{}
\curraddr{}
\email{}
\thanks{}


\subjclass[2010]{Primary }

\keywords{}

\date{}

\dedicatory{}

\begin{abstract}
\end{abstract}

\maketitle

\section{Introduction}

\section{Definitions}

Throughout, $G = (V, E)$ is a plane maximal planar graph (a triangulation)
with a fixed planar embedding $\Pi_G$. We write $|V| = n$, so $|E| = 3n - 6$
and $G$ has $2n - 4$ triangular faces.

\begin{definition}[Level source]
A \emph{level source} of $G$ is either:
\begin{itemize}
\item a face $F$ of $G$ (all vertices of $F$ are level-0 sources), or
\item a vertex $v$ of degree 3 (the singleton $\{v\}$ is a level-0 source).
\end{itemize}
\end{definition}

\begin{figure}[h]
\centering
\includegraphics[width=0.85\textwidth]{fig_level_source.png}
\caption{The two kinds of level source on a 7-vertex triangulation $T$
(K\textsubscript{4} with vertices $4,5,6$ stacked into the three
interior faces). Left: the face source $S = \{0,1,2\}$
(level-0 vertices are the corners of the highlighted triangle).
Right: the degree-$3$ vertex source $S = \{4\}$.}
\label{fig:level-source}
\end{figure}

\begin{definition}[Levels]
Given a level source $S \subseteq V$, the \emph{level} of $v \in V$ is
$\ell_G(v) = \mathrm{dist}_G(v, S)$, the graph distance from $v$ to the nearest
source vertex.
\end{definition}

\begin{figure}[h]
\centering
\includegraphics[width=0.55\textwidth]{fig_levels.png}
\caption{BFS levels from the degree-$3$ vertex source $S = \{4\}$.
The source is level $0$, its three neighbours are level $1$, and the
remaining vertices are level $2$. Colour encodes the level.}
\label{fig:levels}
\end{figure}

\begin{definition}[Level cycle]
A \emph{level cycle} of $G$ (with respect to a level source $S$) is a
simple cycle in $G$ all of whose vertices have the same level.
\end{definition}

\begin{figure}[h]
\centering
\includegraphics[width=0.55\textwidth]{fig_level_cycle.png}
\caption{A level cycle in the triangulation of Figure~\ref{fig:levels}.
The triangle $1\!-\!2\!-\!3$ is a simple cycle whose three vertices all
lie at level $1$, so it is a level cycle at level $1$.}
\label{fig:level-cycle}
\end{figure}

\begin{definition}[Edge switch]
\label{def:edge-switch}
Let $G$ be a triangulation with level source $S$, and let $e = uv$ be an
edge of a level cycle of $G$. The \emph{edge switch} at $e$ is the edge
flip on $e$: writing $uvw$ and $uvx$ for the two triangular faces of $G$
containing $e$, the edge $uv$ is removed and the edge $wx$ is added. As
with any edge flip, the result is a triangulation on the same vertex set
provided $w$ and $x$ are non-adjacent in $G$.
\end{definition}

\begin{figure}[h]
\centering
\includegraphics[width=0.95\textwidth]{fig_edge_switch.png}
\caption{An edge switch on the level cycle of
Figure~\ref{fig:level-cycle}. The chosen cycle edge $1\!-\!2$ is shared
by the triangular faces $(0,1,2)$ and $(1,2,4)$; the switch deletes
$1\!-\!2$ (red, left) and inserts $0\!-\!4$ (green, right). Vertex
colours indicate the original levels in $G$.}
\label{fig:edge-switch}
\end{figure}

\begin{definition}[Parity subgraph]
Let $G$ be a triangulation with level source $S$, and let $G'$ be a triangulation
on the same vertex set as $G$. The \emph{even parity subgraph} $E_{G,S}(G')$ is
the subgraph of $G'$ induced by $\{v \in V : \ell_G(v) \equiv 0 \pmod 2\}$. The
\emph{odd parity subgraph} is defined analogously for odd $\ell_G$.
\end{definition}

\begin{figure}[h]
\centering
\includegraphics[width=\textwidth]{fig_parity_subgraph.png}
\caption{Parity subgraphs of $G' = T$ with respect to the level structure of
Figure~\ref{fig:levels} (here we take $G = G' = T$). Left: $T$ with vertices
coloured by $\ell_G \bmod 2$ (blue $=$ even, orange $=$ odd). Middle: the
even parity subgraph $E_{G,S}(G')$, induced on $\{0, 4, 5, 6\}$; only
edges with both endpoints even appear. Right: the odd parity subgraph
$O_{G,S}(G')$, induced on $\{1, 2, 3\}$; the highlighted triangle shows
that $O_{G,S}(G')$ is not bipartite for this choice of $G'$.}
\label{fig:parity-subgraph}
\end{figure}

\begin{definition}[Facial depth]
\label{def:facial-depth}
Let $L_k$ be drawn with the outerplanar embedding inherited from $\Pi_G$,
let $D$ be the dual graph of this drawing with the outer face removed,
and let $\mathcal{B}$ be the set of inner faces of $L_k$ whose bounding
level cycle contains at least one edge of the outer cycle of $L_k$. The
\emph{facial depth} of an inner face $F$ of $L_k$ is
\[
  \mathrm{depth}(F) \;=\; \min_{F' \in \mathcal{B}} \mathrm{dist}_D(F, F'),
\]
with the convention $\mathrm{depth}(F) = \infty$ if no such $F'$ exists.
An inner face is \emph{isolated} if $\mathrm{depth}(F) \geq 1$.
\end{definition}

\begin{figure}[h]
\centering
\includegraphics[width=0.6\textwidth]{fig_facial_depth.png}
\caption{Facial depths in a maximal outerplanar graph on $12$ vertices.
The six green ear-triangles share an edge with the outer $12$-cycle and
so lie in $\mathcal{B}$ (depth $0$). The three yellow ``in-between''
triangles $(0,2,4),(4,6,8),(0,8,10)$ have only diagonal edges but each
is dual-adjacent to ears, giving them $\mathrm{depth} = 1$. The central
triangle $(0,4,8)$ is also all-diagonal; its dual neighbours are the
three depth-$1$ triangles, so it is isolated with
$\mathrm{depth} = 2$.}
\label{fig:facial-depth}
\end{figure}

\begin{definition}[Surface switch]
\label{def:surface-switch}
A \emph{surface switch} is an edge switch (Definition~\ref{def:edge-switch})
applied to an edge incident to two level cycles, one of facial depth $d$
and the other of facial depth $d - 1$.
\end{definition}

\begin{definition}[Balanced surface switch]
\label{def:balanced-surface-switch}
Let $\sigma$ be a surface switch on an edge $e = uv$ separating an inner
face $F$ of $L_k$ of depth $d \geq 1$ from an adjacent inner face
$F' = uvx$ of depth $d - 1$. We say $\sigma$ is \emph{balanced} if each
of the two edges of $\partial F'$ other than $uv$ (namely $ux$ and $vx$)
either lies on the outer cycle of $L_k$ or is shared with an inner face
of $L_k$ of depth $d - 2$.
\end{definition}

When $d = 1$ the condition reduces to ``both $ux$ and $vx$ lie on the
outer cycle of $L_k$'', because no inner face has depth $-1$; in that
case $F'$ is a triangular ``ear'' hanging off $uv$.

\section{Outerplanarity of level components}
\label{sec:outerplanar-components}

For each integer $k \geq 0$ and each $(G, S)$, write $L_k$ for the
subgraph of $G$ induced by the level-$k$ vertices. A \emph{level
component} of $G$ (with respect to $S$) is a connected component of
some $L_k$.

\begin{theorem}
\label{thm:outerplanar-component}
For every plane triangulation $G$ and every level source $S$ of $G$,
every level component of $G$ is outerplanar.
\end{theorem}

\begin{proof}
Since every subgraph of an outerplanar graph is outerplanar, it suffices
to show that each level subgraph $L_k$ is outerplanar. For $k = 0$,
$L_0$ is either a single vertex (when $S$ is a degree-$3$ vertex) or
the triangle bounding the source face (when $S$ is a face), both
outerplanar.

Fix $k \geq 1$ and let $D_k$ be the drawing of $L_k$ inherited from
$\Pi_G$. Let $F^\ast$ be the face of $D_k$ containing the source.
Suppose for contradiction that some $u \in L_k$ does not lie on
$\partial F^\ast$, so $u$ lies on the boundary of some other face of
$D_k$. Take any path $P$ in $G$ from $v_0 \in S$ to $u$. As a curve in
$\Pi_G$, $P$ starts in $F^\ast$ and ends at a point off $\partial
F^\ast$, so it must transition from $F^\ast$ to a different face of
$D_k$; in a planar embedding this can happen only at a vertex of
$D_k$, that is, at a level-$k$ vertex $w$ on $P$. Either $w \neq u$
(so $P$ has length $\geq \mathrm{dist}_G(S, w) + 1 \geq k + 1$), or
$w = u$ (contradicting $u \notin \partial F^\ast$). Since every
$S$-to-$u$ path has length $\geq k + 1$, $\mathrm{dist}_G(S, u) \geq
k + 1$, contradicting $u \in L_k$.
\end{proof}

\begin{lemma}
\label{lem:depth-descent}
Let $C$ be a level component of $G$ with respect to $S$, drawn with the
outerplanar embedding inherited from $\Pi_G$, and let $D$ be its
inner-face dual. If $F$ is an inner face of $C$ with
$\mathrm{depth}(F) = d > 0$, then $F$ is dual-adjacent to an inner
face $F'$ with $\mathrm{depth}(F') = d - 1$.
\end{lemma}

\begin{proof}
By Theorem~\ref{thm:outerplanar-component}, $C$ is outerplanar, so the
inner-face dual $D$ is a forest (a standard fact; a tree when $C$ is
$2$-connected).

Each leaf $F_\ell$ of $D$ contains a single interior edge of $C$, so
the remaining edges of $\partial F_\ell$ lie on the outer cycle of $C$.
In particular $F_\ell$ has at least one outer-cycle edge, so
$F_\ell \in \mathcal{B}$ and $\mathrm{depth}(F_\ell) = 0$. Hence every
tree component of $D$ contains an element of $\mathcal{B}$, so the
depths of all of its vertices are finite.

Choose a shortest path $F = F_0, F_1, \ldots, F_d = F^\ast$ in $D$ from
$F$ to some $F^\ast \in \mathcal{B}$ realising $\mathrm{depth}(F) = d$.
The suffix $F_1, \ldots, F_d$ witnesses $\mathrm{depth}(F_1) \leq d - 1$.
If $\mathrm{depth}(F_1) \leq d - 2$, prepending the edge $F\,F_1$ to a
witnessing path would give $\mathrm{depth}(F) \leq d - 1$, contradicting
$\mathrm{depth}(F) = d$. Hence $\mathrm{depth}(F_1) = d - 1$, and we
may take $F' := F_1$.
\end{proof}

\begin{proposition}
\label{prop:balanced-descent}
Let $\sigma$ be a balanced surface switch on the edge $e = uv$ separating
$F$ (depth $d \geq 1$) from $F' = uvx$ (depth $d - 1$), and let
$G' = G - uv + wx$ be the result of the underlying edge flip, with
$uvw, uvx$ the two triangular faces of $G$ at $uv$. Then in $L_k'$ (the
level-$k$ subgraph of $G'$, with the level assignment of $G$):
\begin{enumerate}
\item the level cycle $\partial F$ is destroyed; and
\item one or two new inner faces appear in $L_k'$, each of depth exactly
$d - 1$.
\end{enumerate}
\end{proposition}

\begin{proof}
The flip removes $uv$ from $G$, so $\partial F$ is no longer a cycle of
$L_k'$, proving (1). For (2) we split on whether the new edge $wx$
re-enters $L_k$.

\textbf{Case (i): $\{w, x\} \not\subseteq L_k$.} Then $L_k' = L_k - uv$.
The faces $F$ and $F'$ merge into a single new inner face $\widetilde F$
with boundary $(\partial F \cup \partial F') \setminus \{uv\}$. The dual
neighbours of $\widetilde F$ in $L_k'$ are exactly the former neighbours
of $F$ and $F'$ other than each other; in particular they include all
inner faces previously adjacent to $F'$ across $ux$ or $vx$, whose depths
are at most $d - 2$ by Lemma~\ref{lem:depth-descent} applied to $F'$
(when $d \geq 2$). Thus $\mathrm{depth}(\widetilde F) \leq d - 1$.

For the matching lower bound, every neighbour of $\widetilde F$ has depth
$\geq d - 2$ (neighbours inherited from $F$ have depth $\geq d - 1$;
neighbours inherited from $F'$ have depth $\geq d - 2$). When $d \geq 2$,
neither $F$ nor $F'$ has an outer-cycle edge, so neither does
$\widetilde F$, giving $\mathrm{depth}(\widetilde F) \geq d - 1$. When
$d = 1$, $F' \in \mathcal{B}$ and its outer-cycle edge (necessarily
distinct from the interior edge $uv$) survives on $\partial \widetilde F$,
so $\widetilde F \in \mathcal{B}'$ and
$\mathrm{depth}(\widetilde F) = 0 = d - 1$. In either case
$\mathrm{depth}(\widetilde F) = d - 1$, giving the unique new face
required by~(2).

\textbf{Case (ii): $\{w, x\} \subseteq L_k$.} Then $F = uvw$ and
$F' = uvx$ are triangular faces of $L_k$, and $L_k' = L_k - uv + wx$.
The chord $wx$ splits the quadrilateral $\partial(F \cup F')$ into two
triangular faces $A = uwx$ and $B = vwx$ of $L_k'$. We show
$\mathrm{depth}(A) = \mathrm{depth}(B) = d - 1$.

By symmetry it suffices to handle $A$. The dual neighbours of $A$ in
$L_k'$ are $A_{uw}$ (the inner face across $uw$, unchanged from $L_k$),
$A_{ux}$ (the inner face across $ux$, unchanged), and $B$ (across the
new edge $wx$). By balancedness of $\sigma$ applied to the edge $ux$:
\begin{itemize}
\item if $ux$ lies on the outer cycle of $L_k$, it remains on the outer
cycle of $L_k'$, so $A \in \mathcal{B}'$ and $\mathrm{depth}(A) = 0$
(which equals $d - 1$ because the balanced-with-outer-cycle case forces
$d = 1$); or
\item if $A_{ux}$ is an inner face, balancedness gives
$\mathrm{depth}(A_{ux}) = d - 2$, so
$\mathrm{depth}(A) \leq 1 + (d - 2) = d - 1$.
\end{itemize}

For the lower bound in the second sub-case ($d \geq 2$): $A$'s edges are
$uw$ (an edge of $F$, interior because $F$ has depth $d \geq 1$), $wx$
(new, not on the outer cycle), and $ux$ (interior in this sub-case), so
$A \notin \mathcal{B}'$. Moreover every neighbour of $A$ has depth $\geq
d - 2$: $A_{uw}$ inherits depth $\geq d - 1$ from being a former
neighbour of $F$, $A_{ux}$ has depth $d - 2$, and $B$ has depth $\geq
d - 2$ by the same argument applied symmetrically. Therefore
$\mathrm{depth}(A) \geq d - 1$, and combined with the upper bound,
$\mathrm{depth}(A) = d - 1$.
\end{proof}

\subsection*{When does a balanced surface switch exist?}

For a chord $uv$ of a maximal outerplanar graph, the \emph{span} of $uv$
is the minimum, over the two arcs from $u$ to $v$ on the outer cycle,
of the number of outer-cycle vertices strictly between them.

\begin{observation}
\label{obs:span1-balanced-d1}
For $d = 1$, an inner face $F$ admits a balanced surface switch on some
edge iff at least one edge of $F$ has span $1$ in the outer cycle of
$L_k$. The opposite triangle across that edge -- using the single
outer-cycle vertex between its endpoints -- is then an ear of $F$ in
$\mathcal{B}$, satisfying the $d = 1$ form of
Definition~\ref{def:balanced-surface-switch}.
\end{observation}

The smallest maximal-outerplanar configuration violating this is a
$9$-vertex outer cycle triangulated so that the unique interior face
$F = (0,3,6)$ has spans $(2,2,2)$ on its three edges
(Figure~\ref{fig:no-balanced}). Each depth-$0$ neighbour of $F$ carries
exactly one outer-cycle edge, not two, so none qualifies as an ear of
$F$; no balanced surface switch is available.

\begin{figure}[h]
\centering
\includegraphics[width=0.55\textwidth]{fig_no_balanced_switch.png}
\caption{$9$-vertex maximal outerplanar $L_k$. $F = (0,3,6)$ has
$\mathrm{depth} = 1$ and all three of its edges have span $2$, so none
of $F$'s depth-$0$ neighbours is an ear. No balanced surface switch is
available on $F$.}
\label{fig:no-balanced}
\end{figure}

\subsection*{Preprocessing toward balanced switches}

When $F$ has depth $d \geq 1$ but admits no balanced surface switch,
perform a single (unbalanced) surface switch on any edge of $F$ shared
with a depth-$(d-1)$ neighbour. By Proposition~\ref{prop:balanced-descent}
the result is at least one new depth-$(d-1)$ face; in Case~(ii) it is
accompanied by a new depth-$d$ face $A$ that replaces $F$ as the next
candidate. The hope is that the resulting $A$ admits a balanced
surface switch, or that iterating the preprocessing eventually exposes
one.

\begin{example}
\label{ex:preprocessing}
On the $9$-vertex example, the (unbalanced) surface switch on edge
$uv = 03$ -- with $F' = (0,2,3)$, third vertex $x = 2$, and $w = 6$ --
flips $03 \mapsto 26$ in $G$ and produces $A = (0,2,6)$ at depth $1$.
The new face has spans $(1, 3, 2)$ on its edges, and the ear
$(0,1,2)$ across the span-$1$ edge $02$ is now a balanced
surface-switch target on $A$ (Figure~\ref{fig:preprocessing}).
\end{example}

\begin{figure}[h]
\centering
\includegraphics[width=\textwidth]{fig_preprocessing.png}
\caption{One step of preprocessing on the $9$-vertex example. Left:
$F = (0,3,6)$ has no edge of span $1$; the chosen surface-switch edge
$uv = 03$ (red) is unbalanced. Right: after the switch $03 \mapsto 26$
(green), the new depth-$1$ face $A = (0,2,6)$ has its edge $02$ (red)
at span $1$, exposing the ear $(0,1,2)$ as a balanced surface-switch
target.}
\label{fig:preprocessing}
\end{figure}

We do not have a general termination theorem. The natural candidate
monovariant for $d = 1$ is the minimum span among edges of the current
depth-$1$ face that are shared with a depth-$0$ neighbour; in
Example~\ref{ex:preprocessing} this drops from $2$ to $1$ in a single
step. Whether such a monovariant strictly decreases under every
unbalanced surface switch -- and a corresponding statement for $d \geq
2$, where balancedness depends on depth-$(d-2)$ structure rather than
just spans -- remains open.

\subsection*{The $d \geq 2$ analog and recursive lopsidedness}

For $d \geq 2$ the obstruction to a balanced surface switch is no longer
"$F$ has no edge of span 1": it is recursive. We say a depth-$(d-1)$
neighbour $F' = uvx$ of $F$ is \emph{lopsided} if exactly one of its
non-$F$ neighbours has depth $d-2$ (the other being deeper or an
interior face of depth $d-1$). $F$ admits a balanced surface switch
iff at least one depth-$(d-1)$ neighbour is not lopsided.

The analog of the $9$-vertex example at $d = 2$ is a $21$-vertex
configuration where the unique depth-$2$ face $F = (0, 7, 14)$ has
three depth-$1$ neighbours $(0,3,7), (7,10,14), (14,17,0)$, each
lopsided: their depth-$1$ "deep side" is a degree-$3$ face
$(3,5,7), (10,12,14), (17,19,0)$ that itself reaches depth $0$ via
two ears. So the obstruction at $F$ is one layer of lopsidedness;
after a single preprocessing step the new depth-$2$ face $(3,7,14)$
sees the previously-hidden balanced descender as a direct neighbour
and the algorithm terminates immediately.

Stacking lopsidedness yields a $24$-vertex example
(Figure~\ref{fig:d2-recursive}) where every depth-$1$ neighbour of $F$
is lopsided \emph{and} the depth-$1$ degree-$3$ face inside each arm
($G_i$) is itself lopsided. Two preprocessing steps are needed before a
balanced switch becomes available: the active depth-$2$ face migrates
from $(0,8,16)$ to $(2,8,16)$ to $(4,8,16)$, at which point the
\emph{innermost} depth-$1$ face $(4,6,8)$ -- whose two non-$F$ neighbours
$(4,5,6)$ and $(6,7,8)$ are both ears -- becomes a direct neighbour and
the balanced condition is satisfied. After the balanced switch, $10$
further balanced switches drive every face to depth $0$.

\begin{figure}[h]
\centering
\includegraphics[width=\textwidth]{fig_d2_recursive.png}
\caption{Recursive lopsidedness at $d = 2$. Left: $F = (0,8,16)$ depth
$2$, every arm doubly-lopsided. Middle: one preprocessing switch
$(0,8) \mapsto (2,16)$ exposes the first lopsided layer; the new
depth-$2$ face $(2,8,16)$ still has no balanced switch. Right: a
second preprocessing switch $(8,2) \mapsto (4,16)$ reaches the inner
balanced face $K_0 = (4,6,8)$, whose two non-$F$ neighbours are both
ears; the depth-$2$ face $(4,8,16)$ now admits a balanced surface
switch on edge $(4,8)$.}
\label{fig:d2-recursive}
\end{figure}

\subsection*{Empirical termination}

On every tested configuration, iterated preprocessing terminates and
the algorithm
\[
\text{while max-depth face $F$ has $\mathrm{depth}(F) > 0$: }
\text{do a balanced switch if available, else preprocess}
\]
drives every face to depth $0$. The observed step count is

\begin{center}
\begin{tabular}{lccc}
configuration & $n$ & $d_{\max}$ & total switches \\\hline
no-balanced $d=1$ (Figure~\ref{fig:no-balanced}) & 9 & 1 & 4 \\
singly-lopsided $d=2$ (Figure~\ref{fig:d2-recursive} left only) & 21 & 2 & 8 \\
doubly-lopsided $d=2$ (Figure~\ref{fig:d2-recursive}) & 24 & 2 & 13 \\
\end{tabular}
\end{center}

Each preprocessing step appears to advance the active maximum-depth
face one vertex along the lopsided arm of the chosen depth-$(d-1)$
neighbour, peeling off one layer of recursive lopsidedness. The
remaining open question is to identify the monovariant that captures
this: a candidate is the total number of triples $(F, F', F'')$ where
$F' \in N(F)$ is lopsided and $F'' \in N(F')$ is its depth-$d-1$
"deep side". We do not yet have a proof that this strictly decreases
under every unbalanced surface switch on a maximum-depth face.

\subsection*{What the natural monovariants do not give us}

The most obvious candidate -- the lexicographic depth signature
$\big(\#\{F : \mathrm{depth}(F) \geq k\}\big)_{k \geq 1}$ -- is
\emph{weakly} but not strictly decreasing: a balanced surface switch
removes the level cycle bounding $F$ and creates one or two cycles of
depth $d - 1$, so each balanced switch strictly decreases the signature
in some component. But an unbalanced surface switch in Case~(ii)
removes one depth-$d$ face and creates one depth-$(d-1)$ face plus one
depth-$d$ face, so the signature is unchanged. The same holds for the
simpler sum $\sum_F \mathrm{depth}(F)$: on the $24$-vertex example
of Figure~\ref{fig:d2-recursive} the sum is $11$ at every preprocessing
step, dropping only when balanced switches begin.

A finer candidate is the dual-tree distance from the active
maximum-depth face $F$ to the nearest face $F^\bullet$ that admits a
balanced surface switch as a depth-$d$ face. Empirically, with the
preprocessing edge chosen along the path from $F$ to $F^\bullet$, this
distance strictly decreases by $1$ per preprocessing step; combined
with the strict drop in the depth signature at each balanced step,
$(\text{signature}, \text{tree-distance-to-}F^\bullet)$ then becomes a
lexicographically decreasing monovariant. We do not have a proof that
$F^\bullet$ always exists, nor a recipe to identify it without
look-ahead.

\subsection*{Empirical termination on random configurations}

Beyond the constructed examples, we ran the iterated algorithm
(balanced switch when available, otherwise preprocess via a deterministic
edge choice) on random triangulations of polygons of size $n$ up to $24$
(10-20 trials per size). Every trial terminated, with the worst-case
total step count growing roughly as $O(n^2)$: about $13$ steps at
$n = 24$, an order of magnitude more by $n = 40$. With a random edge
choice the algorithm still terminates empirically but takes substantially
more steps, suggesting that the deterministic strategy (advancing
toward a known $F^\bullet$) matters for efficient termination.

\begin{question}
\label{q:preprocessing-terminates}
Does iterated preprocessing always reach a balanced surface switch in
finitely many steps? More specifically: in every maximal outerplanar
$L_k$ with $d_{\max} \geq 1$, does there exist a face $F^\bullet$ that
admits a balanced surface switch -- and if so, can it always be
reached from the current maximum-depth face by a preprocessing path of
length bounded by the dual-tree diameter of $L_k$?
\end{question}

\section{Reachability via edge switches}
\label{sec:reachability}

We now sketch a positive termination argument that bypasses the local
question of balanced surface switches entirely: instead of insisting
that each switch strictly improve facial depth, we show that any
$L_k$ can be transformed by edge switches into a configuration in which
every face has depth $0$. Throughout this section we adopt the
\emph{stable-labelling convention}: the level $\ell_G(v)$ of each
vertex is fixed at the start of the procedure (by BFS from $S$ in the
initial triangulation $G$) and reused thereafter, even after edge
switches modify the triangulation. In particular, the level-$k$
subgraph $L_k$ of the current triangulation always means ``the
subgraph induced on the vertices labelled $k$ at the start''.

\subsection*{Two cases on the layer below $k$}

We split on whether any $L_k$-face has a higher-level vertex in its
interior in the planar embedding inherited from $\Pi_G$.

\textbf{Case 1: every inner face of $L_k$ is a triangle and contains
no vertex of level $\geq k+1$ in its interior.}

Under this hypothesis, for every chord $uv \in L_k$ the two $G$-triangles
at $uv$ have their third vertices in $L_k$ (since the interior of the
two $L_k$-faces adjacent to $uv$ in $\Pi_G$ contains no other vertex of
$G$). The edge switch at $uv$ is therefore always in Case~(ii) of
Proposition~\ref{prop:balanced-descent}, and acts as a flip of the
chord $uv$ in $L_k$ regarded purely as a maximal outerplanar graph.

Maximal outerplanar graphs on $n$ labelled vertices (arranged on a
common outer cycle) are exactly triangulations of a convex $n$-gon.
The set of such triangulations, with chord flips as edges, is the
1-skeleton of the associahedron and is connected; in fact any two
triangulations are joined by $O(n)$ chord flips~\cite{sleator-tarjan-thurston}.
A \emph{fan triangulation} -- the triangulation obtained by adding
chords from a single apex vertex $v_0$ to every other vertex -- has
every inner triangle bounded by an outer-cycle edge (namely the side
opposite $v_0$ in that triangle), so every face of a fan triangulation
lies in $\mathcal{B}$ and has depth $0$.

Combining: in Case~1, $L_k$ can be transformed into a fan triangulation
by $O(n)$ edge switches, after which every face has depth $0$.

\textbf{Case 2: some $L_k$-face $F$ has a vertex of level $\geq k+1$
in its interior.}

Pick any edge $uv$ of $\partial F$. The $G$-triangle at $uv$ on the
$F$-side has its third vertex $w$ inside $F$, so $w$ is a vertex of
level $\geq k+1$ and in particular $w \notin L_k$. The edge switch
at $uv$ is therefore in Case~(i) of
Proposition~\ref{prop:balanced-descent}: the edge $uv$ is removed from
$L_k$, no new edge is added to $L_k$, and the face $F$ merges with the
$L_k$-face on the opposite side of $uv$ into a single larger face. The
number of inner faces of $L_k$ strictly decreases by $1$.

\subsection*{Combining}

\begin{theorem}
\label{thm:reachability}
Under the stable-labelling convention, every $L_k$ can be transformed
by edge switches into a configuration in which every inner face of
$L_k$ has facial depth $0$, in $O(n)$ edge switches.
\end{theorem}

\begin{proof}[Proof sketch]
Apply Case~2 repeatedly while $L_k$ has any inner face with a
higher-level vertex in its interior. Each application reduces the
number of inner faces of $L_k$ by $1$, so after at most $|L_k| - 2 \leq
n - 2$ such steps we reach one of:
\begin{itemize}
\item A configuration satisfying the hypothesis of Case~1, in which
case Case~1 finishes the job in $O(n)$ flips by reaching a fan
triangulation.
\item A configuration in which $L_k$ has only one inner face -- i.e.,
$L_k$ consists of only its outer cycle, with no chords. The unique
inner face is bounded by all $n$ outer-cycle edges, so it lies in
$\mathcal{B}$ and has depth $0$.
\end{itemize}
Both outcomes leave every face at depth $0$. The total step count is
at most $(n - 2) + O(n) = O(n)$.
\end{proof}

\begin{remark}
Theorem~\ref{thm:reachability} settles the existence question
Question~\ref{q:preprocessing-terminates} affirmatively in the
following sense: \emph{some} sequence of edge switches drives every
face to depth $0$ in $O(n)$ steps. It does not, however, identify the
sequence by a local rule (the leaf-distance algorithm of
Section~\ref{sec:reachability}'s preceding discussion), and in
particular the question of which \emph{rule} produces such a sequence
without backtracking remains open.
\end{remark}

\begin{thebibliography}{9}

\bibitem{sleator-tarjan-thurston}
D.~D. Sleator, R.~E. Tarjan, W.~P. Thurston.
\emph{Rotation distance, triangulations, and hyperbolic geometry}.
Journal of the American Mathematical Society, 1988.

\end{thebibliography}

\end{document}