$x$, a contradiction. Otherwise, $x$ can reach $first^{*}_{G}(u)$,
$first^{*}_{G}(u)$ can reach $last^{*}_{G}(v)$, and $last^{*}_{G}(v)$ can
reach $x$. As a result, $first^{*}_{G}(u)$ and $last^{*}_{G}(v)$ are strongly
connected, a contradiction.

Finally, suppose $V(Y)\cap V(P)=\emptyset$. Consider the $x\to v$ subpath
$Z^{\prime}$ of $Y$. Since $Z^{\prime}$ is a satellite path, we showed that it
has to go through $w$, a contradiction. ∎

We now turn to the case when $first^{*}_{G}(u)$ and $last^{*}_{G}(v)$ are
strongly connected. Recall that by Lemma 6.3, for any $p_{j}\in V(P)$, the
vertices of $P$ that are strongly connected to $p_{j}$ constitute a subpath
$P[p_{i},p_{k}]$, where $i\leq j\leq k$. Denote by $p_{j}^{*}$ the latest
vertex of $P$ that is strongly connected to $p_{j}$, i.e., $p_{j}^{*}:=p_{k}$.
Define $W_{j}=\bigcup_{l=i}^{k}\left(\\{p_{l}\\}\cup
L_{l}\cup{L}^{\text{R}}_{l}\right)$. Let $D_{j}^{*}$
(${D_{j}^{*}}^{\text{R}}$) be the dominator tree of $G[W_{j}]$
(${G}^{\text{R}}[W_{j}]$, resp.) with start vertex $p_{j}^{*}$. Observe that
the total number of different sets $W_{j}$ equals the number of strongly
connected components of $G$ that have a non-empty intersection with $V(P)$,
and we have $W_{a}=W_{b}$ if and only if $p_{a}$ and $p_{b}$ are strongly
connected in $G$. Each vertex $v\in V(G)$ belongs to at most two sets $W_{j}$:
if $v\in V(P)$, then it belongs to a unique set $W_{j}$, whereas if $v\in
V(G)\setminus V(P)$, then there is at most one $L_{a}$ containing $v$ and at
most one ${L}^{\text{R}}_{b}$ with $v\in{L}^{\text{R}}_{b}$.

Therefore, the total size of all distinct graphs $G[W_{j}]$ is linear in the
size of $G$. Consequently, we can compute all dominator trees
$D_{j}^{*},{D_{j}^{*}}^{\text{R}}$ in linear time.

######  Lemma 8.2.

Let $u,v\in V(G)$. Suppose the following conditions are satisfied:

  1. 1.

there exists a $u\to v$ path in $G$ that goes through $V(P)$,

  2. 2.

$first^{*}_{G}(u)=p_{i}$ and $last^{*}_{G}(v)=p_{j}$ are strongly connected in
$G$.

Then for any path $Q=u\to v$ such that $V(P)\cap V(Q)\neq\emptyset$,
$Q\subseteq G$ if and only if $Q\subseteq G[W_{i}]$. Moreover, $u$ can reach
$p_{i}^{*}$ in $G[W_{i}]$ and $v$ can be reached from $p_{i}^{*}$ in
$G[W_{i}]$.

###### Proof.

We prove that no $u\to v$ path $Q$ going through $V(P)$ in $G$ goes through
the vertices of $V(G)\setminus W_{i}$. This will imply that in fact any such
$Q$ exists in $G$ if and only if it exists in $G[W_{i}]$.

We start by noting that $V(Q)\subseteq
V(P)\cup\bigcup_{i=1}^{\ell}(L_{i}\cup{L}^{\text{R}}_{i})$. Otherwise $Q$
would go through a vertex $w$ that lies neither on $P$ nor in any of $L_{i}$
or ${L}^{\text{R}}_{i}$. Since $Q$ also goes through some $p\in V(P)$, $w$
either can reach $p$, or is reachable from $p$, a contradiction.

Observe that $Q$ cannot have a satellite subpath $z\to v$, where $z\in L_{k}$
and $p_{i}^{*}\prec p_{k}$. If this was the case, $p_{k}$ could reach $v$ by a
satellite path and $last^{*}_{G}(v)\preceq p_{i}^{*}\prec p_{k}$, which would
contradict the definition of $last^{*}_{G}(v)=p_{i}$. Similarly we can prove
that $Q$ does not contain any $u\to z$ satellite subpath such that
$z\in{L_{l}}^{\text{R}}$, where $p_{l}\prec p_{i}^{*}$ and $p_{l}$ is not
strongly connected to $p_{i}^{*}$.

Suppose that for some $p_{k}\in V(P)$, $p_{i}^{*}\prec p_{k}$, we have
$p_{k}\in V(Q)$. Then the path $Q$ can be expressed as $Q=Q^{\prime}T$, where
$T=p_{t}\to v$ is a (possibly $0$-edge, if $v\in V(P)$) satellite path. If
$v\in V(P)$, then $last^{*}_{G}(v)=v$ and $v\preceq p_{i}^{*}\prec p_{k}$. But
$p_{k}$ can reach $v$, so $p_{i}^{*}$ and $p_{k}$ are strongly connected,
which contradicts the definition of $p_{i}^{*}$. So we have $v\notin V(P)$.
Let $T^{\prime}$ be the $p_{k}\to p_{t}$ suffix subpath of $Q^{\prime}$. If
$p_{k}\neq p_{t}$, then $p_{t}\preceq last^{*}_{G}(v)\preceq p_{i}^{*}\prec
p_{k}$, so $p_{t}$ can reach $p_{k}$ and thus
$p_{k},p_{i}^{*},last^{*}_{G}(v),p_{t}$ are all strongly connected, which
contradicts the definition of $p_{i}^{*}$. Therefore, $p_{k}=p_{t}$. But this
means that $p_{k}$ can reach $v$ by a satellite path and
$last^{*}_{G}(v)\preceq p_{i}^{*}\prec p_{k}$ which in turn contradicts the
definition of $last^{*}_{G}(v)$. Symmetrically we prove that $Q$ cannot go
through a vertex $p_{l}\in V(P)$ that appears on $P$ earlier than the earliest
vertex of $P$ strongly connected to $p_{i}^{*}$. We conclude that each $p\in
V(Q)\cap V(P)$ is strongly connected to $p_{i}^{*}$.

Finally, suppose that $Q$ goes through a vertex $z\in L_{k}$, where
$p_{i}^{*}\prec p_{k}$. We have already proven that $Q$ cannot contain a $z\to
v$ satellite subpath. So the $z\to v$ subpath of $Q$ has to go through a
vertex $p\in V(P)$. But we have already proven that $p$ has to be strongly
connected to $p_{i}^{*}$. Hence $p\preceq p_{i}^{*}$. So there exist paths
$p_{k}\to z$, $z\to p$, $p\to p_{i}^{*}$, and $p_{i}^{*}\to p_{k}$. Thus,
$p_{i}^{*}$ is strongly connected to $p_{k}$, which contradicts the definition
of $p_{i}^{*}$. Similarly we prove that $Q$ cannot go through a vertex
$z\in{L_{k}}^{\text{R}}$ where $p_{k}\prec p_{i}^{*}$ and $p_{k}$ is not
strongly connected to $p_{i}^{*}$. We conclude $Q\subseteq G[W_{i}]$.

To see that $u$ can reach $p_{i}^{*}$ ($p_{i}^{*}$ can reach $v$) in
$G[W_{i}]$ it is enough to note that
$last^{*}_{G}(p_{i}^{*})=first^{*}_{G}(p_{i}^{*})=p_{i}^{*}$ and apply what we
have proved for $v:=p_{i}^{*}$ ($u:=p_{i}^{*}$ respectively). ∎

To make use of Lemma 8.2, we will need one more result.

######  Lemma 8.3.

Let $G$ be a digraph and let $u,v,s$ be pairwise distinct vertices of $G$. Let
$H\subseteq G$ be such that $H$ contains (preserves) all $u\to s$ paths in $G$
and all $s\to v$ paths in $G$. Let $D$ (${D}^{\text{R}}$) be a dominator tree
with start vertex $s$ in $H$ (${H}^{\text{R}}$, resp.).

Let $d_{u}$ be the parent of $u$ in ${D}^{\text{R}}$ and let $d_{v}$ be the
parent of $v$ in $D$. Then $v$ is 2-reachable from $u$ in $G$ if and only if
$u$ can reach $v$ in each of the graphs $G-d_{u}$, $G-d_{v}$ and $G-s$.

###### Proof.

The ’’$\impliedby$‘‘ direction is trivial so we only need to prove that
existence of a path $u\to v$ in each of the graphs $G-d_{u}$, $G-d_{v}$ and
$G-s$ implies 2-reachability in $G$. Suppose there exists some $x\in
V(G)\setminus\\{u,v\\}$ lying on all $u\to v$ paths in $G$. If $x=s$, then
there is no $u\to v$ path in $G-s$.

Otherwise, if $x$ is neither an ancestor of $u$ in ${D}^{\text{R}}$ nor the
ancestor of $v$ in $D$, then there exist a path $u\to s$ in $H-x$ and there
exists a path $s\to v$ in $H-x$. Since $H-x\subseteq G-x$, $u$ can reach $v$
in $G-x$, a contradiction.

Therefore, $x$ either lies on all $u\to s$ paths in $H$, or it lies on all
$s\to v$ paths in $H$. Wlog. assume the former case, as the proof in the
latter is symmetric. Since $H$ preserves all $u\to s$ paths of $G$, $x$ lies
on all $u\to s$ paths in $G$. If $x=d_{u}$, we are done. Otherwise, $x$ is a
proper ancestor of $d_{u}$ in ${D}^{\text{R}}$, so, by Lemma 5.1, $d_{u}$ lies
on all $u\to x$ paths in $H$. Observe that in fact $d_{u}$ lies on all $u\to
x$ paths in $G$. If this was not the case, there would be a $u\to s$ path in
$H$ avoiding $d_{u}$, a contradiction. Therefore, since $d_{u}$ lies on all
$u\to x$ paths in $G$, and $x$ lies on all $u\to v$ paths in $G$, $d_{u}$ also
lies on all $u\to v$ paths in $G$. Equivalently, $u$ cannot reach $v$ in
$G-d_{u}$. ∎

Now, Lemmas 8.2 and 8.3 allow us to handle 2-reachability queries between
pairs of vertices $u,v$ such that $first^{*}_{G}(u)$ is strongly connected to
$last^{*}_{G}(v)$. Indeed, if $first^{*}_{G}(u)=p_{i}$ and
$last^{*}_{G}(v)=p_{j}$, then, by Lemma 8.2, $G[W_{i}]$ preserves all $u\to
p_{i}^{*}$ and $p_{j}^{*}\to v$ paths in $G$. Hence, by Lemma 8.3, it is
sufficient to look for a $u\to v$ path in $G-x$ using the 1-sensitivity data
structure for $w\in\\{p_{i}^{*},d_{u},d_{v}\\}$, where $d_{u}$ is the parent
of $u$ in ${D_{i}^{*}}^{\text{R}}$, and $d_{v}$ is the parent of $v$ in
$D_{j}^{*}$.

###  8.2 Looking for a separating vertex on the path

Let $G$ be a plane digraph and let $p_{1}\ldots p_{\ell}=P\subseteq G$ be a
directed path whose endpoints lie on a single face of $G$. Our goal is to
support queries of the following form: for any $u,v\in V(G)$ such that there
exists a $u\to v$ path going through $V(P)$ in $G$, find a vertex $x\in V(P)$
such that all $u\to v$ paths in $G$ go through $x$, or decide there is none.

Observe that in the previous section, the query algorithm using Lemmas 8.2 and
8.3 for the case when $first^{*}_{G}(u)$ and $last^{*}_{G}(v)$ are strongly
connected actually did not require the separating vertex $x$ that we were
looking for to lie outside of $P$. We will leverage this fact so that we can
additionally assume that $first^{*}_{G}(u)$ and $last^{*}_{G}(v)$ are not
strongly connected.

We can focus on the case when $u$ cannot reach $v$ in $G-V(P)$, since
otherwise clearly no failure of a vertex of $P$ can make $v$ unreachable from
$u$.

Similarly to the proof of Lemma 8.1, from the fact that $first^{*}_{G}(u)$ and
$last^{*}_{G}(v)$ are not strongly connected we can conclude that
$first^{*}_{G}(u)\prec last^{*}_{G}(v)$. Define $l$ to be the latest vertex of
$P$ such that $l\preceq last^{*}_{G}(v)$ and there exists a satellite path
$u\to l$. Note that $l$ exists and $first^{*}_{G}(u)\preceq l$ by
$first^{*}_{G}(u)\prec last^{*}_{G}(v)$. Similarly, let us define $f$ to be
the earliest vertex of $P$ such that $first^{*}_{G}(u)\preceq f$ and there
exists a $f\to v$ satellite path. Analogously, $f$ exists and $f\preceq
last^{*}_{G}(v)$. Note that by using the data structure of Lemma 7.4, the
vertices $f,l$ can be computed in $O(\log{n})$ time after linear
preprocessing.

######  Lemma 8.4.

Suppose for some $x\in V(P)$ there is no $u\to v$ path in $G-x$. Then
$l\preceq x\preceq f$.

###### Proof.

We prove that if $x\prec l$, then there is a $u\to v$ path in $G-x$. The proof
if $f\prec x$ is analogous. Take any satellite path $R=u\to l$ and any
$last^{*}_{G}(v)\to v$ satellite path $T$. Then, since $x\prec l\preceq
last^{*}_{G}(v)$, $R\cdot P[l,last^{*}_{G}(v)]\cdot T$ is a $u\to v$ path in
$G-x$, a contradiction. ∎

By Lemma 8.4, if $f\prec l$, no vertex of $P$ lies on all $u\to v$ paths in
$G$. Hence, in the following let us assume $l\preceq f$. Moreover, since in
$O(\log{n})$ time we can check whether a single vertex lies on all $u\to v$
paths in $G$, without loss of generality we can assume that none of the
vertices $f,l$ lies on all $u\to v$ paths in $G$. Consequently, we assume
$l\prec x\prec f$.

Let $x\in V(P(l,f))$ and consider any path $Q_{x}=u\to v$ in $G-x$. Clearly,
$Q_{x}$ can be expressed as $RST$, where $R$ is a $u\to enter({Q_{x}})$
satellite path and $T$ is a $leave({Q_{x}})\to v$ satellite path.

We now prove a few structural lemmas.

######  Lemma 8.5.

We have:

  * •

either $first^{*}_{G}(u)\preceq enter({Q_{x}})\preceq l$ or
$last^{*}_{G}(v)\prec enter({Q_{x}})$.

  * •

either $leave({Q_{x}})\prec first^{*}_{G}(u)$ or $f\preceq
leave({Q_{x}})\preceq last^{*}_{G}(v)$.

###### Proof.

We only prove the former item, as the proof of the latter is completely
analogous. $enter({Q_{x}})\prec first^{*}_{G}(u)$ is impossible by the
definition of $first^{*}_{G}(u)$. On the other hand, $l\prec
enter({Q_{x}})\preceq last^{*}_{G}(v)$ would contradict the definition of $l$.
∎

######  Lemma 8.6.

$last^{*}_{G}(v)\prec enter({Q_{x}})$ and $leave({Q_{x}})\prec
first^{*}_{G}(u)$ cannot hold simultaneously.

###### Proof.

Suppose $last^{*}_{G}(v)\prec enter({Q_{x}})$ and $leave({Q_{x}})\prec
first^{*}_{G}(u)$ at the same time. Then since $first^{*}_{G}(u)\prec
last^{*}_{G}(v)$, there is a $leave({Q_{x}})\to first^{*}_{G}(u)\to
last^{*}_{G}(v)\to enter({Q_{x}})$ path in $G$. But by the definition of
$enter({Q_{x}})$ and $leave({Q_{x}})$, there is also a $enter({Q_{x}})\to
leave({Q_{x}})$ path in $G$. Hence, $first^{*}_{G}(u)$ and $last^{*}_{G}(v)$
are strongly connected in $G$, a contradiction. ∎

######  Lemma 8.7.

Suppose $first^{*}_{G}(u)\preceq enter({Q_{x}})\preceq l$ and
$leave({Q_{x}})\prec first^{*}_{G}(u)$. Then there exists a $u\to v$ path
$Q_{x}^{\prime}$ in $G-x$ such that $enter({Q_{x}^{\prime}})=first^{*}_{G}(u)$
and $leave({Q_{x}^{\prime}})=g$, where $g$ is the latest vertex $g\prec
first^{*}_{G}(u)$ such that there exists a $g\to v$ satellite path in $G$.

###### Proof.

First note that $g$ indeed exists since $leave({Q_{x}})\prec
first^{*}_{G}(u)$. Let $R^{\prime}$ be any $u\to first^{*}_{G}(u)$ satellite
path and let $T^{\prime}$ be any $g\to v$ satellite path in $G$. Then
$R^{\prime}\cdot P[first^{*}_{G}(u),enter({Q_{x}})]\cdot S\cdot
P[leave({Q_{x}}),g]\cdot T^{\prime}$ forms a desired $u\to v$ path
$Q_{x}^{\prime}$ in $G-x$. ∎

The proof of the following lemma is symmetric to the proof of the above Lemma,
so we omit it.

######  Lemma 8.8.

Suppose $f\preceq leave({Q_{x}})\preceq last^{*}_{G}(v)$ and
$last^{*}_{G}(v)\prec enter({Q_{x}})$. Then there exists a $u\to v$ path
$Q_{x}^{\prime}$ in $G-x$ such that $leave({Q_{x}^{\prime}})=last^{*}_{G}(v)$
and $enter({Q_{x}^{\prime}})=h$, where $h$ is the earliest vertex
$last^{*}_{G}(v)\prec h$ such that there exists a $u\to h$ satellite path in
$G$.

######  Lemma 8.9.

Suppose $first^{*}_{G}(u)\preceq enter({Q_{x}})\preceq l$ and $f\preceq
leave({Q_{x}})\preceq last^{*}_{G}(v)$. Let
$u^{\prime}=first_{G-x}(first^{*}_{G}(u))$,
$v^{\prime}=last_{G-x}(last^{*}_{G}(v))$. Then:

  1. 1.

$u^{\prime}\preceq min({Q_{x}})$ and $max({Q_{x}})\preceq v^{\prime}$.

  2. 2.

There exists a $u\to v$ path in $Q_{x}^{\prime}=Q_{1}P_{1}P_{2}P_{3}Q_{2}$ in
$G-x$, where $Q_{1}$ is a $u\to u^{\prime}$ path in $G-x$, $Q_{2}$ is a
$v^{\prime}\to v$ path in $G-x$, $P_{1}$ and $P_{3}$ are possibly empty
subpaths of $P$, and $P_{2}$ is a minimal detour of $x$.

  3. 3.

If $x$ is not strongly connected to $first^{*}_{G}(u)$, then
$u^{\prime}=first_{G}(first^{*}_{G}(u))$. Similarly, if $x$ is not strongly
connected to $last^{*}_{G}(v)$, then $v^{\prime}=last_{G}(last^{*}_{G}(v))$.

###### Proof.

Clearly, $u^{\prime}\preceq first^{*}_{G}(u)$ and $last^{*}_{G}(v)\preceq
v^{\prime}$. Since ${first^{*}_{G}(u)\preceq enter({Q_{x}})\preceq l}$ and
$f\preceq leave({Q_{x}})\preceq last^{*}_{G}(v)$, we have $u^{\prime}\preceq
first^{*}_{G}(u)\prec x\prec last^{*}_{G}(v)\preceq v^{\prime}.$

Item (1) follows by applying Lemmas 7.9 and 7.10 to $Q_{x}$.

Let $Q_{1}$ be the $u\to u^{\prime}$ path and let $Q_{2}$ be any
$v^{\prime}\to v$ in $G-x$. Consider the path $Q_{x}^{\prime\prime}=Q_{1}\cdot
P[u^{\prime},enter({Q_{x}})]\cdot S\cdot P[leave({Q_{x}}),v^{\prime}]\cdot
Q_{2}$ in $G-x$. The path $Q_{x}^{\prime}=Q_{1}P_{1}P_{2}P_{3}Q_{2}$ as
required by item (2) can be obtained by applying Lemma 7.11 to
$Q_{x}^{\prime\prime}$.

Finally to prove the first part of item (3), suppose that
$first_{G}(first^{*}_{G}(u))\prec u^{\prime}$. Then every $first^{*}_{G}(u)\to
first_{G}(first^{*}_{G}(u))$ path in $G$ goes through $x$. Since
$first_{G}(first^{*}_{G}(u))\preceq first^{*}_{G}(u)\prec x$, there is also a
$first_{G}(first^{*}_{G}(u))\to first^{*}_{G}(u)$ path in $G$. Hence,
$first^{*}_{G}(u)$ and $x$ are strongly connected in $G$. The proof that
$last_{G}(last^{*}_{G}(v))=v^{\prime}$ if $x$ is not strongly connected to
$last^{*}_{G}(v)$ is analogous. ∎

Having proven the above properties, we move to describing the query procedure
that finds some $x\in V(P)$ that lies on all $u\to v$ paths, if one exists.
Suppose there exists some $x\in V(P(l,f))$ lying on all $u\to v$ paths in $G$.
Let $g$ be defined as in Lemma 8.7, and $h$ be defined as in Lemma 8.8. Such
an $x$, in order to be a separating vertex for the pair $u,v$, has to satisfy
the following conditions.

  1. (1)

By Lemma 8.7, either $g\prec first^{*}_{G}(u)$ does not exist or there is no
path $first^{*}_{G}(u)\to g$ in $G-x$. Observe that since $g$ (if exists)
satisfies $g\prec first^{*}_{G}(u)\prec x$, then there is no
$first^{*}_{G}(u)\to g$ path in $G-x$ if and only if $g$ is not strongly
connected to $first^{*}_{G}(u)$ in $G-x$.

  2. (2)

Similarly, by Lemma 8.8, either $h$, $last^{*}_{G}(v)\prec h$ does not exist
or $last^{*}_{G}(v)$ is not strongly connected to $h$ in $G-x$.

  3. (3)

By Lemma 8.9, for each minimal detour pair $(a_{x},b_{x})$ of $x$ we should
have either $a_{x}\prec first_{G-x}(first^{*}_{G}(u))$ or
$last_{G-x}(last^{*}_{G}(v))\prec b_{x}$.

By Lemmas 8.5 and 8.6, if all conditions (1)-(3) are satisfied, then we rule
out all possible configurations of $enter({Q_{x}})$ and $leave({Q_{x}})$ with
respect to $x$ on $P$. In other words, if all of these conditions hold
simultaneously, $x$ indeed lies on all $u\to v$ paths in $G$. Recall that
$first^{*}_{G}(u)$ and $last^{*}_{G}(v)$ are not strongly connected, so $x$
cannot be simultaneously strongly connected to both $first^{*}_{G}(u)$ and
$last^{*}_{G}(v)$. By Lemma 6.3, the subpath $P(l,f)$ can be split into three
possibly empty subpaths $P(l,f)=P_{u},P_{0},P_{v}$ (in this order), such that
$x\in V(P(l,f))$ is strongly connected to $first^{*}_{G}(u)$ in $G$ iff $x\in
V(P_{u})$, to $last^{*}_{G}(v)$ in $G$ iff $x\in V(P_{v})$, and to neither
$first^{*}_{G}(u)$ nor $last^{*}_{G}(v)$ iff $x\in V(P_{0})$.

Suppose first that $x\in V(P_{u})$, i.e, $x$ is strongly connected to
$first^{*}_{G}(u)$, but not to $last^{*}_{G}(v)$ (in $G$). The case when $x\in
V(P_{v})$ is symmetric. Since $x$ is not strongly connected to
$last^{*}_{G}(v)$, $h$ and $last^{*}_{G}(v)$ are strongly connected in $G-x$
if and only if they are strongly connected in $G$. Hence, condition (2) does
not depend on $x$ and implies that either $h$ does not exist or it has to be
strongly connected to $last^{*}_{G}(v)$ in $G$. Luckily, strong-connectivity
in $G$ can be tested in $O(1)$ time.

By condition (3) we obtain that no minimal detour pair $(a_{x},b_{x})$ of $x$
can satisfy $first_{G-x}(first^{*}_{G}(u))\preceq a_{x}\preceq b_{x}\preceq
last_{G}(last^{*}_{G}(v))$. This is because $x$ not strongly connected to
$last^{*}_{G}(v)$, implies, by Lemma 8.9, that
$last_{G-x}(last^{*}_{G}(v))=last_{G}(last^{*}_{G}(v))$.

Let $(a_{x}^{1},b_{x}^{1}),(a_{x}^{2},b_{x}^{2})$ be the two minimal detour
pairs of $x$ (if there is only one, put
$(a_{x}^{2},b_{x}^{2}):=(a_{x}^{1},b_{x}^{1})$; if there are none, set
$(a_{x}^{1},b_{x}^{1}):=(a_{x}^{2},b_{x}^{2}):=(x,x)$). Denote by
$\bar{a}_{x}^{i}$ the earliest vertex of $P$ such that
$a_{x}^{i}\prec\bar{a}_{x}^{i}\prec x$ and $a_{x}^{i}$ is not strongly
connected to $\bar{a}_{x}^{i}$ in $G-x$. If no such $\bar{a}_{x}^{i}$ exists,
put $\bar{a}_{x}^{i}=x$. For a fixed $x$, each $\bar{a}_{x}^{i}$ can be found
in $O(\log{n})$ time by combining binary-search with the strong-connectivity
under failures data structure as we did in Lemma 7.4. Therefore, the vertices
$\bar{a}_{x}^{i}$ for all $x\in V(P)$ and $i$ can be computed in $O(n\log{n})$
time.

Wlog. assume that $a_{x}^{1}\preceq a_{x}^{2}$ and $b_{x}^{1}\preceq
b_{x}^{2}$. Observe that $\bar{a}_{x}^{1}\preceq\bar{a}_{x}^{2}$. _Not_
satisfying the condition

$first_{G-x}(first^{*}_{G}(u))\preceq a_{x}^{i}\preceq b_{x}^{i}\preceq
last_{G}(last^{*}_{G}(v))$

can be restated as $\bar{a}_{x}^{i}\preceq first^{*}_{G}(u)\lor
last_{G}(last^{*}_{G}(v))\prec b_{x}^{i}$. So, we obtain that

$\forall_{i\in\\{1,2\\}}(\bar{a}_{x}^{i}\preceq first^{*}_{G}(u)\lor
last_{G}(last^{*}_{G}(v))\prec b_{x}^{i})$

has to be satisfied if $x\in V(P_{u})$ lies on all $u\to v$ paths in $G$. By
applying elementary transformations and using the inequalities
$\bar{a}_{x}^{1}\preceq\bar{a}_{x}^{2}$ and $b_{x}^{1}\preceq b_{x}^{2}$, the
above formula can be rewritten as $F_{x}^{1}\lor F_{x}^{2}\lor F_{x}^{3}$,
where

$\displaystyle F_{x}^{1}$ $\displaystyle=\bar{a}_{x}^{2}\preceq
first^{*}_{G}(u)),$ $\displaystyle F_{x}^{2}$
$\displaystyle=last_{G}(last^{*}_{G}(v))\prec b_{x}^{1},$ $\displaystyle
F_{x}^{3}$ $\displaystyle=\bar{a}_{x}^{1}\preceq first^{*}_{G}(u)\land
last_{G}(last^{*}_{G}(v))\prec b_{x}^{2}.$

By condition (1) we obtain that if $x\in V(P_{u})$ lies on all $u\to v$ paths
in $G$, either $g$ does not exist or $x$ has to be such that $g$ and
$first^{*}_{G}(u)$ are not strongly connected in $G-x$. To characterize all
such vertices $x$ in an algorithmically useful way, we need the following
structural lemma.

######  Lemma 8.10.

Let $G$ be a digraph. There exists two trees $T_{1},T_{2}$ with the following
property: for any vertices $u,v$ strongly connected in $G$, there exists at
most four paths $Q^{u,v}_{1},\ldots Q^{u,v}_{k}$, such that each $Q^{u,v}_{i}$
is a path in either $T_{1}$ or $T_{2}$, and all $x\in V(G)$ such that $u$ and
$v$ are not strongly connected in $G-x$ are precisely the vertices of
$Q^{u,v}_{1}\cup\ldots\cup Q^{u,v}_{k}$.

The trees $T_{1},T_{2}$ can be computed in linear time. Given $u,v$, the
endpoints of paths $Q^{u,v}_{1},\ldots Q^{u,v}_{k}$ can be computed in
constant time.

###### Proof.

The lemma is essentially proved in [31, Lemma 8.1]. There, it is shown that if
$G$ is strongly connected, the following holds. Let $H$ and ${H}^{\text{R}}$
are some loop-nesting trees of $G$ and ${G}^{\text{R}}$ respectively. Let $D$
and ${D}^{\text{R}}$ are dominator trees with the same source vertex $s$ in
$G$ and ${G}^{\text{R}}$. Let $w$ (${w}^{\text{R}}$) be the nearest common
ancestor of $u$ and $v$ in $H$ (${H}^{\text{R}}$, resp.). Then, the set
$X_{uv}$ of vertices $x\in V(G)\setminus\\{u,v\\}$ such that $u$ and $v$ are
not strongly connected in $G-x$ is equal to the set of proper ancestors of $u$
or $v$ in $D$ which are not proper ancestors of $w$ in $D$, plus the set of
proper ancestors of $u$ and $v$ in ${D}^{\text{R}}$ which are not proper
ancestors of ${w}^{\text{R}}$ in ${D}^{\text{R}}$. Observe that $X_{uv}$ can
be represented as a union of two paths in $D$ and two paths in
${D}^{\text{R}}$. The endpoints of these paths can be computed in $O(1)$ time
after preprocessing $D,{D}^{\text{R}},H,{H}^{\text{R}}$ in linear time so that
nearest common ancestor queries on these trees are supported in constant time.

The required tree $T_{1}$ ($T_{2}$) can be formed by arbitrarily connecting
the dominator trees $D$ (${D}^{\text{R}}$) of individual strongly connected
components of $G$. ∎

Hence in order for $x$ to separate $g$ and $first^{*}_{G}(u)$ in $G$, $x$ has
to lie on one of at most $4$ paths $Q_{1},\ldots,Q_{k}$ obtained from Lemma
8.10 for $u:=g$ and $v:=first^{*}_{G}(u)$.

To summarize, provided that $h$ either does not exist or is not strongly
connected to $last^{*}_{G}(v)$, $x\in V(P_{u})$ lies on all $u\to v$ paths in
$G$ if and only if the following hold at the same time:

  1. (i)

$F_{x}^{1}\lor F_{x}^{2}\lor F_{x}^{3}$,

  2. (ii)

$x\in V(Q_{1}\cup\ldots\cup Q_{k})$,

whereas if additionally $g$ does not exist or is not strongly connected to
$first^{*}_{G}(u)$, then it is enough that $x$ satisfies $F_{x}^{1}\lor
F_{x}^{2}\lor F_{x}^{3}$. Let us focus on the most involved case when $g$ is
strongly connected to $first^{*}_{G}(u)$, as otherwise $x$ has less
constraints to satisfy and dummy constraints can be added to treat the problem
analogously. Note that (i) and (ii) hold simultaneously for $x\in V(P_{u})$ if
and only if $F_{x}^{i}\land(x\in V(Q_{j}))$ holds for some of $O(1)$ pairs
$i,j$.

Let us describe how to find some $x$ (if it exists) satisfying
$F_{x}^{3}\land(x\in V(Q_{j}))$ only, since this is clearly the most involved
case. We use the following data-structural lemma.

######  Lemma 8.11.

Let $T$ be an $n$-vertex tree and suppose each $v\in V(T)$ has assigned a
$3$-dimensional label $(c^{v}_{1},c^{v}_{2},c^{v}_{3})\in[n]^{3}$. Then, in
$O(n\log^{5+o(1)}{n})$-time one can construct an $O(n\log^{2+o(1)}{n})$-space
data structure answering the following queries in $O(\log^{2+o(1)}{n})$ time:
given $u,v\in V(T)$ and a $3$-dimensional rectangle
$[a_{1},b_{1}]\times[a_{2},b_{2}]\times[a_{3},b_{3}]$, find some vertex $w\in
V(T)$ lying on the $u\to v$ path in $T$ satisfying $a_{i}\leq c^{w}_{i}\leq
b_{i}$ for $i=1,2,3$.

###### Proof.

We reduce our problem to a 4-dimensional orthogonal range reporting problem.
It is known that in $O(n\log^{5}{n}\cdot\log\log{n})$ time one can construct
an $O(n\log^{2}{n}\cdot(\log\log{n})^{3})$-space data structure that can
report some $k$ points (if they exist) in a $4$-dimensional rectangle in
$O(\log{n}(\log\log{n})^{3}+k\log\log{n})$ time [38]. We will use this data
structure for $k=1$, i.e., for reporting at most one point.

In our problem, we are given a tree and 3-dimensional labels. With so-called
heavy-path decomposition [48], one can partition a tree $T$ into a set of
vertex-disjoint paths $\mathcal{P}$ so that each path in $T$ can be expressed,
in $O(\log{n})$ time, as a concatenation of $O(\log{n})$ subpaths of paths in
$\mathcal{P}$. Equivalently, by concatenating $\mathcal{P}$ into a single path
$\mathcal{P}^{*}$, and ordering the vertices of $T$ according to their
position on $\mathcal{P}^{*}$, each path in $T$ can be expressed as a union of
$O(\log{n})$ intervals of the obtained order. We make this order our fourth
dimension. This way, we can reduce our original query to $O(\log{n})$
4-dimensional orthogonal range reporting queries (with pairwise-disjoint
fourth dimension ranges), each of which can be processed in
$O(\log{n}(\log\log{n})^{3})$ time, since we only want to find one vertex or
decide there is none. Hence
$O(\log^{2}{n}(\log\log{n})^{3})=O(\log^{2+o(1)}{n})$ query time. ∎

Now, to find $x\in V(P_{u})=V(P[r_{1},r_{2}])$ satisfying $F_{x}^{2}\land(x\in
Q_{j})$, suppose $Q_{j}$ is a path in one of the two trees $T$ from Lemma
8.10. Let $\alpha(p_{i}):=i$ for all $p_{i}\in V(P)$. We assign each vertex
$p\in V(T)\cap V(P)$ the label
$(\alpha(p),\alpha(\bar{a}_{p_{i}}^{1}),\alpha(b_{p_{i}}^{2}))$, whereas for
each vertex $v\in V(T)\setminus V(P)$ we use label $(0,0,0)$. Given this,
observe that we can find $x$ by searching for a vertex on the path $Q_{j}$ of
$T$ with a label in the rectangle
$[\alpha(r_{1}),\alpha(r_{2})]\times[0,\alpha(first^{*}_{G}(u))]\times[\alpha(last_{G}(last^{*}_{G}(v))),n]$.
By Lemma 8.11, such a search can be performed in $O(\log^{2+o(1)}{n})$ time
using a $O(n\log^{2+o(1)}{n})$-space data structure that can be constructed in
$O(n\log^{5+o(1)}{n})$ time.

Finally suppose that $x\in V(P_{0})$. This case is in fact easier than the
previous one, which can be explained as follows. When $x$ is strongly
connected to neither $first^{*}_{G}(u)$ nor $last^{*}_{G}(v)$, conditions (1)
and (2) boil down to first checking whether the vertices $g,h$ do not exist at
all or are at least are not strongly connected to $first^{*}_{G}(u)$ and
$last^{*}_{G}(v)$ respectively. Then, we only need to check whether there
exists $x\in V(P_{0})$ for which $F_{x}^{1}\lor F_{x}^{2}\lor F_{x}^{3}$
holds. As already discussed, this can be achieved with a three-dimensional
orthogonal range reporting query.

##  9 Proof of Theorem 4.4

Before we proceed with the proof, we first review the notion of loop nesting
forest and a useful characterization from [32] of the SCCs of a graph under
vertex failures.

###  9.1 Loop nesting trees

Let $G=(V,E)$ be a directed graph. A _loop nesting forest_ represents a
hierarchy of strongly connected subgraphs of $G$ [53], and is defined with
respect to a dfs tree $T$ of $G$ as follows. For any vertex $u$, the _loop_ of
$u$, denoted by $\mathit{loop}(u)$, is the set of all descendants $x$ of $u$
in $T$ such that there is a path from $x$ to $u$ in $G$ containing only
descendants of $u$ in $T$. Vertex $u$ is the _head_ of $\mathit{loop}(u)$. Any
two vertices in $\mathit{loop}(u)$ reach each other. Therefore,
$\mathit{loop}(u)$ induces a strongly connected subgraph of $G$; it is the
unique maximal set of descendants of $u$ in $T$ that does so. The
$\mathit{loop}(u)$ sets form a laminar family of subsets of $V$: for any two
vertices $u$ and $v$, $\mathit{loop}(u)$ and $\mathit{loop}(v)$ are either
disjoint or nested (i.e., one contains the other). The above property allows
us to define the _loop nesting forest_ $H$ of $G$, with respect to $T$, as the
forest in which the parent of any vertex $v$, denoted by $h(v)$, is the
nearest proper ancestor $u$ of $v$ in $T$ such that $v\in\mathit{loop}(u)$ if
there is such a vertex $u$, and nil otherwise. Then $\emph{loop}(u)$ is the
set of all descendants of vertex $u$ in $H$, which we will also denote as
$H[u]$ (the subtree of $H$ rooted at vertex $u$). Since $T$ is a dfs tree,
every cycle contains a back edge [50]. More generally, every cycle $C$
contains a vertex $u$ that is a common ancestor of all other vertices $v$ of
$T$ in the cycle [50], which means that any $v\in C$ is in $\mathit{loop}(u)$.
Hence, every cycle of $G$ is contained in a loop. A loop nesting forest can be
computed in linear time [14, 53]. In a strongly connected graph, each vertex
is contained in a loop, so $H$ is a tree. Since here we are going to apply the
loop nesting forest on a strongly connected graph, we will refer to $H$ as the
_loop nesting tree_ of $G$.

###  9.2 SCCs in digraphs under failures

######  Theorem 9.1 ([32]).

Let $G$ be a strongly connected graph, $u$ be a vertex such that $G-u$ is not
strongly connected, and let $s$ be an arbitrary vertex in $G$. Moreover, let
$D$ (resp., $D^{R}$) to be the dominator tree of $G$ (resp., $G^{R}$), and $H$
(resp., $H^{R}$) be the loop nesting tree of $G$ (resp., $G^{R}$), all rooted
at $s$. Let $C$ be a strongly connected component of $G-u$. Then one of the
following cases holds:

  * (a)

If $u\neq s$ is a non-leaf vertex in $D$ but a leaf in $D^{R}$ then either
$C\subseteq D[u]\setminus\\{u\\}$ or $C=V\setminus D[u]$.

  * (b)

If $u\neq s$ is a leaf in $D$ but a non-leaf vertex in $D^{R}$ then either
$C\subseteq D^{R}[u]\setminus\\{u\\}$ or $C=V\setminus D^{R}[u]$.

  * (c)

If $u\neq s$ is a non-leaf vertex in both $D$ and $D^{R}$ then either
$C\subseteq D[u]\setminus D^{R}[u]$, or $C\subseteq D^{R}[u]\setminus D[u]$,
or $C\subseteq D[u]\cap D^{R}[u]$, or $C=V\setminus\big{(}D[u]\cup
D^{R}[u]\big{)}$.

  * (d)

If $u=s$ then $C\subseteq D[u]\setminus u$.

Moreover, if $C\subseteq D[u]\setminus\\{u\\}$ (resp., $C\subseteq
D^{R}[u]\setminus\\{u\\}$) then $C=H[w]$ (resp., $C=H^{R}[w]$) where $w$ is a
vertex in $D[u]\setminus\\{u\\}$ (resp., $D^{R}[u]\setminus\\{u\\}$) such that
$h(w)\not\in D[u]\setminus\\{u\\}$ (resp., $h^{R}(w)\not\in
D^{R}[u]\setminus\\{u\\}$).

###  9.3 Decremental range minimum queries

In the _range minimum query_ (RMQ) problem we are given an array $A$ of size
$n$ with values in $\mathbb{R}$, and after bounded preprocessing time, for
query indices $i,j$ we want to answer the minimum value in
$\\{A[i],\dots,A[j]\\}$. In the dynamic version of the problem one wants to
support an intermixed sequence of queries and updates that alter the values on
the array $A$. In the case where the updates can only increase (resp.,
decrease) the values of $A$ the algorithm is called incremental (resp.,
decremental). We use the following result from [56].

######  Theorem 9.2 ([56]).

There exists a data structure for decremental RMQ that requires $O(n)$ space,
$O((\log n\log\log n)^{2/3})$ update time, and $O((\log n\log\log n)^{1/3})$
query time.

###  9.4 Proof of Theorem 4.4

Let us recall the theorem we are going to prove. See 4.4

Observe that instead of computing the maximum-labeled vertex, we can instead
look of the minimum label inside the SCC of $v$ in $G-x$, as the maximum can
be computed using the algorithm for minimum by assigning labels
$f^{\prime}(v)=-f(v)$. In the following we are interested in vertices with
minimum label $f(v)$.

To solve our problem, we will leverage Theorem 9.1. Without loss of generality
assume that $G$ is strongly connected, as otherwise, we can proceed with each
SCC separately since two vertices $u,v$ that are not strongly connected in $G$
are not strongly connected in $G-x$ either. Each query regarding the strongly
connected component of $v$ is answered using the data structure of the SCC of
$G$ containing $v$. We choose an arbitrary start vertex $s$. We first handle
the case $x=s$ in linear time by computing the strongly connected components
of $G-s$ and preprocessing answers to all possible queries.

Suppose $x\neq s$. By Theorem 9.1, any strongly connected component $C$ of
$G-x$ satisfies $V(S)\subseteq D[x]\cup D^{R}[x]$, or is equal to the SCC of
$s$ in $G-x$. We consider those two cases separately.

#### SCCs of $s$ in $G-x$.

We first deal with the case when the SCC $C$ containing $v$ in $G-x$ also
contains $s$. Our goal is to precompute all answers for all possible failed
vertices $x$. By Theorem 9.1, the SCC of $s$ contains precisely all vertices
in $V\setminus\\{D[x]\cup D^{R}[x]\\}$. Hence, the minimum value in the SCC of
$s$ in $G-x$ is the minimum $f(w)$ among all vertices $w$ such that $w\notin
D[x]$ and $w\notin D^{R}[x]$. Let $ord:V\to[1..n]$ be some preorder of the
dominator tree $D$, where $n=|V|$. Let $size(v)=|V(D[v])|$. Similarly let
$ord^{R}:V\to[1..n]$ be some preorder of the dominator tree $D^{R}$. Let
$size^{R}(v)=|V(D^{R}[v])|$. Clearly, all $ord,ord^{R},size,size^{R}$ can be
computed in linear time.

Notice that we have $u\notin D[x]$ iff
$ord(u)\notin[ord(x),ord(x)+size(x)-1]$. Similarly, $u\notin D^{R}[x]$ iff
$ord^{R}(x)\notin[ord^{R}(x),ord^{R}(x)+size^{R}(x)-1]$.

We map each vertex $u\in V$ to a point $(ord(u),ord^{R}(u))$ on the two
dimensional grid $[n]\times[n]$. Let $A$ be the set of obtained points;
clearly $|A|=n$. Based on our previous discussion it is clear that
$u\notin\\{D[x]\cup D^{R}[x]\\}$ if an only if

$(ord(x),ord^{R}(x))\in\left([1,ord(x)-1]\cup[ord(x)+size(x),n]\right)\times\left([1,ord^{R}(x)-1]\cup[ord^{R}(x)+size^{R}(x),n]\right).$

Hence, computing the minimum value $f(u)$ among all vertices
$u\notin\\{D[x]\cup D^{R}[x]\\}$ can be reduced to finding the minimum-labeled
point in the following four two-dimensional rectangles:

  * •

$[1,ord(x)-1]\times[1,ord^{R}(x)-1]$.

  * •

$[1,ord(x)-1]\times[ord^{R}(x)+size^{R}(x),n]$.

  * •

$[ord(x)+size(x),n]\times[1,ord^{R}(x)-1]$.

  * •

$[ord(x)+size(x),n]\times[ord^{R}(x)+size^{R}(x),n]$.

Observe that all the above rectangles are actually 2-sided, in the sense that
each side has at most one endpoint that is not equal to $1$ or $n$, i.e., not
equal to the minimum/maximum possible coordinate.

In order to precompute the minimum value in the SCC of $s$ for all possible
failures $x$, we can simply find the minimum-labeled points in $4(n-1)$
2-sided rectangles. We will only show how to compute minimum-labeled points in
the rectangles of the form $[1,ord(x)-1]\times[1,ord^{R}(x)-1]$. The remaining
cases can be handled analogously. Notice that in our case, we do not need
compute minimum-labeled points in rectangles in an online manner, as we
already know the predefined set of $n-1$ queries to execute. Hence, we can
equivalently express our task as the following offline problem. Assume we have
a set $R$ of red points (corresponding to our original points) and a set of
$B$ blue points (corresponding to the rectangles) on a two dimensional grid
$[n]\times[n]$, and for each blue point $b=(b_{x},b_{y})\in B$ we want to
identify the red point $r=(r_{x},r_{y})\in R$ such that $r_{x}\leq b_{x}$ and
$r_{y}\leq b_{y}$ with the minimum label $f(r)$.

We solve this problem as follows. We first sort the points $B\cup R$
lexicographically so that red points appear earlier than blue points with the
same coordinates; this can be done in $O(|B\cup R|+n)$ time by radix-sort. We
initialize an array $M[1..n]$, and fill $M$ with values $\infty$ (or a
sufficiently large finite value). An instance of the decremental RMQ algorithm
of Theorem 9.2 is applied on $M$. We process all points in $B\cup R$ in
lexicorgaphical order. We will maintain the invariant that $M[y]$ is equal to
the minimum label among all processed red points with second coordinate equal
to $y$.

Suppose we process the current point $p=(p_{x},p_{y})$. If $p$ is red and
$f(p)<M[p_{y}]$ then we update $M[p_{y}]:=f(p)$; otherwise, if $f(p)\geq
M[p_{y}]$, we do nothing. If the current point $p=(p_{x},p_{y})$ is blue, then
we ask the RMQ data structure for the minimum value of $M$ in the range
$[1,p_{y}]$. Notice that at the time the query is made, we have already
processed precisely the points in $R$ whose coordinates are lexicographically
no more than the coordinates of the blue point $p$. Moreover, $M[i]$ contains
the smallest label of a red point with second coordinate $i$ that we have
already processed, and hence, the minimum value in
$\\{M[1],\cdots,M[p_{y}]\\}$ is the minimum value among the points
$p^{\prime}$ that we have processed and which have their second coordinate no
larger than $p_{y}$. We conclude that the range minimum query on $M$ will
correctly return the minimum label among all red points in the range
$[1,1]\times[p_{x},p_{y}]$.

Since we make $O(n)$ updates to $M$ (and thus to the RMQ data structure) and
perform $O(n)$ queries to the RMQ data structure, the algorithm runs in
$O(n(\log n\log\log n)^{2/3})$ time.

#### SCCs in $D[x]\cup D^{R}[x]$.

We preprocess the loop-nesting-tree $H$ and we assign a weight to each edge
$h(w)w$, to be equal to the minimum label $f(v)$ where $v\in H[w]$. This can
be easily done in linear time via a simple bottom-up visit of $H$. By Theorem
9.1, for each vertex $v$ that belongs to an SCC $C\subseteq D[x]$ there exists
a $w$, such that $v\in H[w]$, for which it holds that $h(w)\notin D[x]$ and
$H[w]=C$. Our goal is to prove that the weight of $h(w)w$ is the minimum
weight in $C$ (the SCC of $v$ in $G-x$), and also the minimum weight on the
path $nca_{H}(x,v)$. This will allow us to retrieve the weight of $h(w)w$
efficiently.

Next, we prove the following two claims for a failing vertex $x$.

  * i)

If $h(w)\notin D[x]$, the nearest common ancestor $nca_{H}(w,x)$ of $w$ and
$x$ in $H$ is $h(w)$.

  * ii)

The minimum label in the SCC of $v$ in $G-x$ equals to the minimum weight on
the path from $v$ to $nca_{H}(x,v)$ in $H$.

We first prove i). Consider the DFS tree $T$ that generated the loop-nesting-
tree $H$. By the definition of $H$, $h(w)$ is the nearest ancestor of $w$ in
$T$ such that $w$ and $h(w)$ are strongly connected in $G[T[h(w)]]$, that is,
in the subgraph induced by the descendants of $h(w)$ in $T$. By Lemma 5.1,
since $h(w)\notin D[x]$, all paths from $h(w)$ to $w$ in $G$ contain $x$, and
in particular the path from $h(w)$ to $w$ in $T$. That means, $x$ lies on the
path from $h(w)$ to $w$ in $T$. The existence of the path on $T$ from $h(w)$
to $x$ to $w$ implies that $x$ is strongly connected with $h(w)$ and $w$ in
$G[T[h(w)]]$, and hence $h(w)$ is an ancestor of $x$ in $H$, by the definition
of the loop nesting tree. Since $w\not=x$, the nearest ancestor of $x$ and $w$
is $h(w)$.

Now we prove ii). By Theorem 9.1, the SCC of $v$ in $G-x$ is a subtree of $H$
rooted at a vertex $w$ such that $h(w)\notin\\{D[x]\setminus\\{x\\}\\}$.
Hence, the minimum label in the SCC of $v$ equals to the weight of the edge
$h(w)w$, by claim i). Moreover, the weight of each edge $e$ is larger than the
label of the edges of $H$ incident to all descendants of both endpoints of
edge $e$.

Given claims i) and ii), in the case where $v$ is in $D[x]$, the minimum label
in the SCC of $v$ is the minimum weight on the path between $v$ and
$nca_{H}(x,v)$ in $H$. We can identify the minimum weight on the path of a
static tree in constant time, after $O(|E(H)|)=O(n)$ time preprocessing [21].
The nearest common ancestor queries can be answered in constant time after
linear preprocessing as well [11]. We can do this analogously in the case
where $v\in D^{R}[x]$, by preprocessing $D^{R}$ and $H^{R}$.

Overall, we showed that we can answer the queries of the statement constant
time, after$O(m+n(\log n\log\log n)^{2/3})$ time preprocessing.

## References

  * [1] Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski, and Daniel Wolleb-Graf.  Faster Algorithms for All-Pairs Bounded Min-Cuts.  In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132, pages 7:1–7:15, 2019.
  * [2] Ittai Abraham, Shiri Chechik, and Cyril Gavoille.  Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels.  In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 1199–1218, 2012.  doi:10.1145/2213977.2214084.
  * [3] Alfred V. Aho and Jeffrey D. Ullman.  The Theory of Parsing, Translation, and Compiling.  Prentice-Hall, Inc., 1972.
  * [4] F. E. Allen and J. Cocke.  Graph theoretic constructs for program control flow analysis.  Technical Report IBM Res. Rep. RC 3923, IBM T.J. Watson Research Center, 1972.
  * [5] S. Allesina and A. Bodini.  Who dominates whom in the ecosystem? Energy flow bottlenecks and cascading extinctions.  Journal of Theoretical Biology, 230(3):351–358, 2004.
  * [6] S. Alstrup, D. Harel, P. W. Lauridsen, and M. Thorup.  Dominators in linear time.  SIAM Journal on Computing, 28(6):2117–32, 1999.
  * [7] M. E. Amyeen, W. K. Fuchs, I. Pomeranz, and V. Boppana.  Fault equivalence identification using redundancy information and static and dynamic extraction.  In Proceedings of the 19th IEEE VLSI Test Symposium, March 2001\.
  * [8] S. Baswana, K. Choudhary, and L. Roditty.  Fault-tolerant subgraph for single-source reachability: General and optimal.  SIAM Journal on Computing, 47(1):80–95, 2018.  arXiv:https://doi.org/10.1137/16M1087643, doi:10.1137/16M1087643.
  * [9] Surender Baswana, Keerti Choudhary, and Liam Roditty.  An efficient strongly connected components algorithm in the fault tolerant model.  Algorithmica, 81(3):967–985, Mar 2019.
  * [10] Surender Baswana, Utkarsh Lath, and Anuradha S. Mehta.  Single source distance oracle for planar digraphs avoiding a failed node or link.  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 223–232, 2012.  doi:10.1137/1.9781611973099.20.
  * [11] Michael A. Bender and Martin Farach-Colton.  The LCA problem revisited.  In LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings, pages 88–94, 2000.  doi:10.1007/10719839“˙9.
  * [12] Michael A. Bender and Martin Farach-Colton.  The level ancestor problem simplified.  Theor. Comput. Sci., 321(1):5–12, 2004.  doi:10.1016/j.tcs.2003.05.002.
  * [13] Glencora Borradaile, Seth Pettie, and Christian Wulff-Nilsen.  Connectivity oracles for planar graphs.  In Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings, pages 316–327, 2012.  doi:10.1007/978-3-642-31155-0“˙28.
  * [14] A. L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R. E. Tarjan, and J. R. Westbrook.  Linear-time algorithms for dominators and other path-evaluation problems.  SIAM Journal on Computing, 38(4):1533–1573, 2008.
  * [15] A. L. Buchsbaum, H. Kaplan, A. Rogers, and J. R. Westbrook.  A new, simpler linear-time dominators algorithm.  ACM Transactions on Programming Languages and Systems, 20(6):1265–96, 1998.  Corrigendum in 27(3):383-7, 2005.
  * [16] Timothy M. Chan and Konstantinos Tsakalidis.  Dynamic orthogonal range searching on the RAM, revisited.  In 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia, pages 28:1–28:13, 2017.  doi:10.4230/LIPIcs.SoCG.2017.28.
  * [17] Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann.  Almost optimal distance oracles for planar graphs.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 138–151, New York, NY, USA, 2019. ACM.  doi:10.1145/3313276.3316316.
  * [18] Panagiotis Charalampopoulos, Shay Mozes, and Benjamin Tebeka.  Exact distance oracles for planar graphs with failing vertices.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2110–2123, 2019.  doi:10.1137/1.9781611975482.127.
  * [19] Ho Yee. Cheung, Lap Chi. Lau, and Kai Man. Leung.  Graph connectivities, network coding, and expander graphs.  SIAM Journal on Computing, 42(3):733–751, 2013.  arXiv:https://doi.org/10.1137/110844970, doi:10.1137/110844970.
  * [20] Keerti Choudhary.  An Optimal Dual Fault Tolerant Reachability Oracle.  In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 130:1–130:13, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2016/6265, doi:10.4230/LIPIcs.ICALP.2016.130.
  * [21] Erik D. Demaine, Gad M. Landau, and Oren Weimann.  On Cartesian trees and range minimum queries.  Algorithmica, 68(3):610–625, 2014.  doi:10.1007/s00453-012-9683-x.
  * [22] Krzysztof Diks and Piotr Sankowski.  Dynamic plane transitive closure.  In Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings, pages 594–604, 2007.  doi:10.1007/978-3-540-75520-3“˙53.
  * [23] Ran Duan and Seth Pettie.  Connectivity oracles for failure prone graphs.  In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC ‘10, pages 465–474, New York, NY, USA, 2010. ACM.  doi:10.1145/1806689.1806754.
  * [24] Ran Duan and Seth Pettie.  Connectivity oracles for graphs subject to vertex failures.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 490–509, 2017.  URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.31, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.31, doi:10.1137/1.9781611974782.31.
  * [25] W. Fraczak, L. Georgiadis, A. Miller, and R. E. Tarjan.  Finding dominators via disjoint set union.  Journal of Discrete Algorithms, 23:2–20, 2013.  doi:http://dx.doi.org/10.1016/j.jda.2013.10.003.
  * [26] Harold N. Gabow.  The minset-poset approach to representations of graph connectivity.  ACM Trans. Algorithms, 12(2), February 2016.  doi:10.1145/2764909.
  * [27] L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis.  2-edge connectivity in directed graphs.  ACM Trans. Algorithms, 13(1):9:1–9:24, 2016.  Announced at SODA 2015.  doi:10.1145/2968448.
  * [28] L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis.  2-vertex connectivity in directed graphs.  Information and Computation, 261(2):248–264, 2018.  Announced at ICALP 2015.
  * [29] L. Georgiadis and R. E. Tarjan.  Finding dominators revisited.  In Proc. 15th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 862–871, 2004.
  * [30] Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis, and Przemyslaw Uznanski.  All-Pairs 2-Reachability in $O(n^{\omega}\log n)$ Time.  In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80, pages 74:1–74:14, Dagstuhl, Germany, 2017\.  URL: http://drops.dagstuhl.de/opus/volltexte/2017/7451, doi:10.4230/LIPIcs.ICALP.2017.74.
  * [31] Loukas Georgiadis, Giuseppe F. Italiano, and Nikos Parotsidis.  Strong connectivity in directed graphs under failures, with application.  CoRR, abs/1511.02913, 2015.  URL: http://arxiv.org/abs/1511.02913, arXiv:1511.02913.
  * [32] Loukas Georgiadis, Giuseppe F. Italiano, and Nikos Parotsidis.  Strong connectivity in directed graphs under failures, with applications.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1880–1899, 2017.  doi:10.1137/1.9781611974782.123.
  * [33] Loukas Georgiadis and Robert E. Tarjan.  Dominator tree certification and divergent spanning trees.  ACM Trans. Algorithms, 12(1):11:1–11:42, November 2015.  doi:10.1145/2764913.
  * [34] Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams.  Conditional Hardness for Sensitivity Problems.  In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67, pages 26:1–26:31, 2017.
  * [35] Jacob Holm, Eva Rotenberg, and Mikkel Thorup.  Planar reachability in linear space and constant time.  In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 370–389, 2015.  doi:10.1109/FOCS.2015.30.
  * [36] John E. Hopcroft and Robert Endre Tarjan.  Efficient planarity testing.  J. ACM, 21(4):549–568, 1974.  doi:10.1145/321850.321852.
  * [37] Paul Walton Purdom Jr. and Edward F. Moore.  Immediate predominators in a directed graph [H] (algorithm 430).  Commun. ACM, 15(8):777–778, 1972.  doi:10.1145/361532.361566.
  * [38] Marek Karpinski and Yakov Nekrich.  Space efficient multi-dimensional range reporting.  In Computing and Combinatorics, 15th Annual International Conference, COCOON 2009, Niagara Falls, NY, USA, July 13-15, 2009, Proceedings, pages 215–224, 2009.  doi:10.1007/978-3-642-02882-3“˙22.
  * [39] Valerie King and Garry Sagert.  A fully dynamic algorithm for maintaining the transitive closure.  Journal of Computer and System Sciences, 65(1):150–167, 2002.
  * [40] Philip N. Klein and Shay Mozes.  Optimization algorithms for planar graphs, 2017.  URL: http://planarity.org.
  * [41] T. Lengauer and R. E. Tarjan.  A fast algorithm for finding dominators in a flowgraph.  ACM Transactions on Programming Languages and Systems, 1(1):121–41, 1979.
  * [42] Edward S. Lowry and C. W. Medlock.  Object code optimization.  Commun. ACM, 12(1):13–22, 1969.  doi:10.1145/362835.362838.
  * [43] Jakub Łącki and Yahav Nussbaum and Piotr Sankowski and Christian Wulff-Nilsen.  Single source - all sinks max flows in planar digraphs.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 599–608, 2012.  doi:10.1109/FOCS.2012.66.
  * [44] E. K. Maxwell, G. Back, and N. Ramakrishnan.  Diagnosing memory leaks using graph mining on heap dumps.  In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ‘10, pages 115–124, 2010.
  * [45] Shay Mozes and Eyal E. Skop.  Efficient vertex-label distance oracles for planar graphs.  Theory Comput. Syst., 62(2):419–440, 2018.  doi:10.1007/s00224-017-9827-0.
  * [46] L. Quesada, P. Van Roy, Y. Deville, and R. Collet.  Using dominators for solving constrained path problems.  In Proc. 8th International Conference on Practical Aspects of Declarative Languages, pages 73–87, 2006.
  * [47] Piotr Sankowski.  Dynamic transitive closure via dynamic matrix inverse (extended abstract).  In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 509–517, 2004.  doi:10.1109/FOCS.2004.25.
  * [48] Daniel Dominic Sleator and Robert Endre Tarjan.  A data structure for dynamic trees.  J. Comput. Syst. Sci., 26(3):362–391, 1983.  doi:10.1016/0022-0000(83)90006-5.
  * [49] Sairam Subramanian.  A fully dynamic data structure for reachability in planar digraphs.  In Algorithms - ESA ‘93, First Annual European Symposium, Bad Honnef, Germany, September 30 - October 2, 1993, Proceedings, pages 372–383, 1993.  doi:10.1007/3-540-57273-2˙72.
  * [50] R. E. Tarjan.  Depth-first search and linear graph algorithms.  SIAM Journal on Computing, 1(2):146–160, 1972.
  * [51] R. E. Tarjan.  Finding dominators in directed graphs.  SIAM Journal on Computing, 3(1):62–89, 1974.
  * [52] R. E. Tarjan.  Efficiency of a good but not linear set union algorithm.  Journal of the ACM, 22(2):215–225, 1975.
  * [53] R. E. Tarjan.  Edge-disjoint spanning trees and depth-first search.  Acta Informatica, 6(2):171–85, 1976.
  * [54] Mikkel Thorup.  Compact oracles for reachability and approximate distances in planar digraphs.  J. ACM, 51(6):993–1024, 2004.  doi:10.1145/1039488.1039493.
  * [55] Jan van den Brand and Thatchaphol Saranurak.  Sensitive distance and reachability oracles for large batch updates.  In 60th Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2019.
  * [56] Bryan T. Wilkinson.  Amortized bounds for dynamic orthogonal range reporting.  In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014, pages 842–856, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.


Conference Paper
2022

Dynamic Transition From Mach to Regular Reflection Over a Moving Wedge

Lubna Margha1,2, Ahmed A. Hamada1, Ahmed Eltaweel3
1Department of Ocean Engineering, Texas A$\&$M University, College Station,
TX, 77843, USA
2Department of Aeronautical and Aerospace Engineering, Cairo University, Giza
12613, Egypt
3Aerospace Engineering Program, University of Science and Technology - Zewail
City, Giza, 12578, Egypt

## Abstract

The design of supersonic and hypersonic air-breathing vehicles is influenced
by the transition between the Mach Reflection (MR) and Regular Reflection (RR)
phenomena. The purpose of this study is to investigate the dynamic transition
of unsteady supersonic flow from MR to RR over a two-dimensional wedge
numerically. The trailing edge of the wedge moves downstream along the
$x$-direction with a velocity, $V(t)$ at a free-stream Mach number of $3$. An
unsteady compressible inviscid flow solver is used to simulate the phenomenon.
Further, the Arbitrary Lagrangian-Eulerian (ALE) technique is applied to
deform the mesh during the wedge motion. The dynamic transition from MR to RR
is defined by two criteria, the sonic and the Von-Neumann. Moreover, the lag
in the dynamic transition from the steady-state condition is studied using
various non-dimensional angular velocities, $\kappa$, in the range of [0.1-2].
The lag effect in the shock system is remarkable at the high values of the
non-dimensional angular velocity, $\kappa=1.5$ and $2.0$. Furthermore, because
the shock is bent upstream during the fast motion of the wedge, the transition
from MR to RR happens below the Dual Solution Domain (DSD).

Keywords: Unsteady; Regular reflection; Mach reflection; Moving wedge; Dynamic
shock waves; Supersonic flow; Dual solution domain.

## 1\. Introduction

The accurate predictions of the Regular and Mach reflections transition
phenomena are indispensable in many engineering applications, such as
supersonic and hypersonic vehicles, the explosion gas dynamics, and shock wave
focusing. When a supersonic flow impinges a symmetric sharp wedge of a fixed
small deflection angle, ($\theta$), an incident straight oblique shock wave
generates and reflects at the top symmetric plane, forming a regular reflected
shock wave (RR case, see Figure 1 (a)) for weak shock waves. While, a Mach
stem height is initiated when the incident shock wave deflects by an enough
large fixed wedge angle, generating a three shock wave configuration and slip-
line at the triple point, which is known as the Mach reflection shock wave (MR
case, see Figure 1 (b)). The structure of shock reflections over a symmetric
wedge is sensitive to the incoming shock wave’s Mach numbers ($M_{\infty}$),
compression ramp angles ($\theta$), and initial boundary conditions. Several
scholars clearly investigated the hysteresis of the transition between RR and
MR over a stationary wedge, such as Ben-Dor [1, 2, 3], Ivanov et al. [4, 5],
and Yan et al. [6, 7].

The unsteady dynamic transition from MR and RR is conducted with different
types of wedge motion. Naidoo and Skews [8, 9] studied numerically and
experimentally the unsteady supersonic flow over an impulsive rotating
symmetric wedge at different pivot points locations, such as leading edge and
trailing edge. They rapidly rotate the leading/trailing edge point at
different rates and discussed the effect of choosing the rotating rate on the
unsteady flow features and the dynamics of the shock system. Their results
concluded that the transitional point and the Mach stem height highly depend
on the rotation speed. Moreover, the rotating pivot location affects the
development of the flow field. The transition wave angle from MR to RR was
delayed and happened below the theoretical von-Neumann limit in the Dual
Solution Domain (DSD). Additionally, their results mentioned that the MR
configuration can exist for a while at a zero wedge deflection angle at a
sufficiently large rotation speed.

(a) RR shock structure.

(b) MR shock structure.

Figure 1: Schematic of the supersonic flow field over a wedge showing the RR
and MR shock structures.

Furthermore, a new mechanism was proposed by Margha et. al. [10] to control
the transition between the RR and MR by changing the wedge deflection
angle,$\theta$ at constant wedge height, $h$. They numerically studied the RR
to MR transition by fixing the wedge leading edge and moving the trailing edge
point upstream with a velocity, $V(t)$, and various frequencies, $\kappa$.
Their results showed the lag effects of using $\kappa$ on the transition flow
parameters. To extend our work, this paper is written to investigate in detail
the dynamic effects of $\kappa$ on the transition from MR to RR. A two-
dimensional symmetric wedge with an initial inclination angle of
$\theta=23^{\circ}$ is exposed to a free-stream Mach number, $M_{\infty}=3$,
and the trailing edge point is moved horizontally downstream with a range of
$\kappa=$ [0.1-2].

## 2\. Computational Model

Two-dimensional unsteady Euler equations were used to set the initial steady-
state solution at a wedge angle of $\theta=23^{\circ}$. Then, the horizontal
downstream wedge motion was modeled with different values of non-dimensional
angular velocities, $\kappa$. The motion was added to the solver by applying
the Arbitrary Lagrangian-Eulerian (ALE) technique to compute the new wedge
location at each time step. Details of the numerical method, its verification,
and the grid generation were provided in the previous work [10].

### 2.1 Model Description

The wedge’s motion and the two possible flow structures are described in
Figure 2. A wedge of fixed height, $h$, and varying length and wedge’s angle
with time, $L(t)$ and $\theta(t)$, respectively are exposed to a supersonic
flow with a Mach number of $3$. The half-height of the computational domain
is, $H$, and the total length of both the wedge and the following flat plate
is constant during the motion as $L_{t}$. The motion is started with a steady-
state wedge of $\theta_{i}=23^{\circ}$ with the Mach Reflection MR shock
configuration. Then, the trailing edge is suddenly moved downstream,
decreasing the wedge angle, with velocity, $V(t)$, and at different constant
rates, $\kappa=[0.1,0.5,1.0,1.5,2.0]$. During the motion $h$ and $L_{t}$ are
kept fixed, while $L(t)$ is increasing and $\theta(t)$ is decreasing with
time. All important parameters are given in Table 1.

Figure 2:  The flow configuration of the horizontal motion of two symmetrical wedges in a supersonic flow. Table 1: System properties and parameters. Initial wedge’s chord, $w(0)$ | $0.833m$
---|---
Initial wedge angle, $\theta(0)$ | $23^{\circ}$
Final wedge angle, $\theta(t_{f})$ | $10.5^{\circ}$
Wedge height to half domain height, $\frac{h}{H}$ | $0.3617$
Initial wedge length to half domain height, $\frac{L(0)}{H}$ | $0.85221$
Total wedge length to half domain height, $\frac{L_{t}}{H}$ | $2$
Free-stream Mach number, $M_{\infty}$ | $3$
Reduce frequency, $\kappa$ | $\left\\{\begin{matrix}0.1,0.5,\\\ 1.0,1.5,\\\ 2.0\end{matrix}\right\\}$

### 2.2 Governing Equations

Two-dimensional unsteady Euler equations for supersonic flows are used to
compute the flow over the wedge and are expressed as:

$\frac{\partial Q}{\partial t}+\frac{\partial F}{\partial x}+\frac{\partial
G}{\partial y}=0,$ (1)

where

$Q=\begin{bmatrix}\rho\\\ \rho u\\\ \rho v\\\ \rho e\end{bmatrix},\quad
F=\begin{bmatrix}\rho u\\\ \rho u^{2}+p\\\ \rho uv\\\ u(\rho
e+p)\end{bmatrix},\quad G=\begin{bmatrix}\rho v\\\ \rho uv\\\ \rho v^{2}+p\\\
v(\rho e+p)\end{bmatrix}$ (2)

The static pressure is obtained from

$p=(\gamma-1)\left(\rho e-\rho\frac{u^{2}+v^{2}}{2}\right)$ (3)

where $p$, $\rho$, and $e$ are the flow field pressure, density, and internal
energy, respectively. $u$ and $v$ are the velocity components in the Cartesian
coordinates $x$ and $y$, respectively, and $\gamma$ is the gas-specific heat
ratio, which is set for a perfect gas of $1.4$.

### 2.3 Equations of Motion

The wedge’s trailing edge point is moved horizontally downstream with velocity
$V(t)$ and a constant wedge angular velocity, $\omega=d\theta/dt$
($sec^{-1}$). Accordingly, the velocity of the wedge’s trailing edge is
expressed as:

$V_{t}(t)=\omega\ h\sqrt{1+cot^{2}(\theta(t))}$ (4)

where $h$ is the height of the wedge and it is kept fixed, and $\theta(t)$ is
the decreasing wedge angle.

Further, $\kappa$ is the non-dimensional angular velocity which is normalized
using the free-stream velocity, $V_{\infty}$, and the initial wedge stream-
wise length,$L(0)$.

$\kappa=\frac{\omega\ L(0)}{U_{\infty}}$ (5)

Additionally, the time dependant wedge angle as a function of non-dimensional
time, $\tau$., is defined as:

$\theta(\tau)=\theta(0)+\kappa\tau$ (6)

where $\theta(0)$ is the initial wedge angle at $\tau=0$, and the non-
dimensional time is defined as:

$\tau=\frac{t\ U_{\infty}}{L(0)}$ (7)

### 2.4 Computational Domain

The unsteady supersonic flow with a free-stream Mach number of $3$ over a
moving wedge was simulated using the rhoCentralDyMFoam solver. It is a
density-based solver in the free open-source CFD toolbox, OpenFOAM®$-$v2006.
Kurganov and Tadmor’s [11, 12, 13] semi-discrete and upwind-central non-
staggered techniques were implemented in the solver. A dynamic mesh was
conducted during the computational time using the Arbitrary Lagrangian-
Eulerian (ALE) technique [14], due to using the ”DyM” solver. Due to the
obvious symmetry of the flow behavior and geometry, half of the computational
domain was considered. Nine structured and curved blocks with quadrilateral
cells were used to discretize the domain and to improve the orthogonality of
the cells, as shown in Figure 3. Moreover, this figure shows the boundary
conditions over the faces of the domain. The mesh was refined to the level
that the absolute percentage error of the Mach stem height, MS, reached
$3.4\%$. This is an accepted margin of error, especially since the percentage
of error in the tangent wave angle is $0.17\%$, as discussed in detail in our
previous work [10]. The number of cells of the selected grid is $2624\times
720$ cells. Further details about the solver, the mesh generation, and the
verification were discussed by Margha et al. [10].

Figure 3: Schematic of the computational domain, the boundary, and initial
conditions, for mesh 1

## 3\. Results and Discussion

The dynamic transition from Mach to Regular reflection was investigated using
a horizontal downstream moving wedge at a free-stream Mach number of
$M_{\infty}=3$. The problem was simulated by starting with MR in a steady flow
at $\theta=23^{\circ}$, then the deflection wedge angle was suddenly reduced
to $10.5^{\circ}$. The transition from MR to RR was determined using both the
sonic and Von-Neumann criteria. The lag effect in the transition angles,
$\theta_{t}$ and $\beta_{t}$, and the Mach stem height, MS, was studied using
different non-dimensional angular velocities, $\kappa=[0.1,0.5,1.0,1.5,2.0]$.

### 3.1 Dynamic Transition from RR to MR

The impulsive motion of the trailing edge point was started from the steady
state at $\theta=23^{\circ}$, where the MR configuration exists. The tested
non-dimensional angular velocities, $\kappa$ affect the unsteady shock wave
configuration causing an obvious lag from the steady-state values. This lag
resulted in curvature in the incident shock wave angle as shown in Figure 4.
That’s why the tangent wave angle, $\beta_{tang}$, was also measured during
the unsteady simulations and was compared with the straight wave angle,
$\beta_{p}$ at the same $\theta$ and $\kappa$.

Figure 4: The pressure gradient at $\kappa=2.0$ and $\theta=15^{\circ}$, to
show the curvature in the incident wave and the difference between $\beta_{p}$
and $\beta_{{t_{tang}}}$.

(a) $\theta=15.0014^{\circ}$, MR Case

(b) $\theta=14.9878^{\circ}$, Sonic Transition

(c) $\theta=14.9743^{\circ}$

(d) $\theta=14.9607^{\circ}$, von-Neumann Transition

(e) $\theta=14.9471^{\circ}$, RR Case

(f) $\theta=14.9335^{\circ}$, RR Case

Figure 5: Mach contours when the dynamic transition from MR to RR occurs with
$\kappa=0.5$ at Sonic and von-Neumann criteria (Zoomed-in View).

The Sonic and von-Neumann criteria were used to define the transition from MR
to RR. The Sonic condition was measured when the flow behind the reflected
shock becomes sonic, $M_{\infty}=1$. While the von-Neumann condition occurred
at the point when the slip-line starts to disappear and the flow beyond the
Mach stem turns parallel to the mid-plane of symmetry. In the steady state,
the von-Neumann condition is known as the physical limit for the steady Mach
reflection. Figure 5 shows a close view of the used two criteria in measuring
the transition from MR to RR at $\kappa=0.5$. The Sonic and von-Neumann limits
happened at wedge angles $\theta_{t_{S}}=14.9878$ and
$\theta_{t_{vN}}=14.9607$, as shown in Figures 5 (b) and 5 (d), respectively.

The lag in the transition wedge and wave angles was summarized in Table 2
using the Sonic transition criteria and in Table 3 using the von-Neumann
transition criteria. The results show that the difference between the dynamic
transition angles using the two criteria was within a degree. The steady-state
von-Neumann transition for $M_{\infty}=3$ occurs at a wedge angle of
$\theta_{t_{SC}}=19.66^{\circ}$, and an incident wave angle of
$\beta_{t_{SC}}=39.34^{\circ}$. Decreasing the wedge deflection angle suddenly
with different non-dimensional angular velocities, $\kappa$ resulted in a
deviation of these angles from the von-Neumann steady-state transition angles.
This deviation increased with the increase in the value of $\kappa$, as
indicated in Tables 2 and 3. Furthermore, moving the trailing edge of the
wedge with a small value of $\kappa=0.1$ caused a deviation in the transition
wedge angle, $\theta_{t}-\theta_{t_{SC}}$, within a degree and in the
transition wave angle, $\beta_{t}-\beta_{t_{SC}}$ of $2.73^{\circ}$. For a
relatively higher $\kappa=1.0$, the lag increased, reaching around $8^{\circ}$
in the wedge angle and within $8.9^{\circ}$ in the wave angle. At
$\kappa>1.0$, such as the tested values of $\kappa=(1.5,\ 2.0)$, the
transition happens at a deflection wedge angle $\theta<10.5^{\circ}$. This can
not be studied with the current geometries, as the possible minimum wedge
angle with the fixed wedge height, $h$, is $10.25^{\circ}$ as shown in Figure
13, using the velocity gradient contours for $\kappa=2.0$. As $\theta$
decreased at a low value of $\kappa=0.1$, the MS moved downstream decreasing
its height until vanished and transition to RR occurred as shown in Figure 11.
Further, Figure 12 shows the transition at a relatively high value of
$\kappa=1.0$, while decreasing the wedge incident angle, the MS height
increased then abruptly decreased till the transition happened at the end of
the motion, $\theta_{t}=10.7^{\circ}$.

Table 2: Sonic transition angles at different values of $\kappa$. $\kappa$ | $\theta_{{t}}$ | $\beta_{{t_{p}}}$ | $\beta_{{t_{tang}}}$ |  $\tau_{t}($ms$)$
---|---|---|---|---
$0.1$ | $18.7794^{\circ}$ | $36.6112^{\circ}$ | $36.436^{\circ}$ | $42.2064$
$0.5$ | $14.9878^{\circ}$ | $33.4599^{\circ}$ | $31.8521^{\circ}$ | $16.0243$
$1.0$ | $10.7645^{\circ}$ | $30.465^{\circ}$ | $24.6111^{\circ}$ | $12.2355$
Table 3: von-Neumann transition angles at different values of $\kappa$ . $\kappa$ | $\theta_{{t}}$ | $\beta_{{t_{p}}}$ | $\beta_{{t_{tang}}}$ | $\tau_{t}$
---|---|---|---|---
$0.1$ | $18.7698^{\circ}$ | $36.6171^{\circ}$ | $36.4229^{\circ}$ | $42.3014$
$0.5$ | $14.9607^{\circ}$ | $33.4338^{\circ}$ | $31.8179^{\circ}$ | $16.0786$
$1.0$ | $10.683^{\circ}$ | $30.3767^{\circ}$ | $24.511^{\circ}$ | $12.317$

In addition, the temporal variation of the wave angle, $\beta_{p}$ during the
wedge’s trailing-edge motion for different values of $\kappa$ is shown in
Figure 6. It showed the lag in the dynamic shock system with wedge motion.
This lag affected the transfer of information from the wedge apex to the
reflected/triple point. The results indicated that there was no variation in
the wave angle, $\beta_{p}=41.478$, at the beginning period of motion, from
$\theta=23^{\circ}$ to a couple of lower angles. This is because the lag was
developing during the period due to the sudden motion of the wedge with
certain $\kappa$. For example, at high value of $\kappa=2.0$, $\beta_{p}$
stayed constant at $41.4^{\circ}$ during decreasing the wedge angle from
$23^{\circ}$ to $20^{\circ}$. The effect of the lag decreased using lower
values of $\kappa$. Moreover, Figure 8 assures the concept of the lag during
the wedge’s motion, by comparing the straight and tangent wave angles at the
reflection/triple point, $\beta_{p}$ and $\beta_{tang}$, respectively. The
deviation between the two wave angles grew with the increase of $\kappa$ from
within $4^{\circ}$ in the case of $\kappa=0.1$ to within $9^{\circ}$ in the
case of $\kappa=2.0$ at the final time of the motion of $\theta=10.5^{\circ}$.
Further, Figure 7 showed that the variation in the value of $\kappa$
insignificantly affected the lagged tangent wave angle as the curves were
almost the same.

Figure 6: The variation of the incident wave angle at reflection/triple point,
$\beta_{p}$ with decreasing wedge angle, $\theta$, using different values of
$\kappa$.  Figure 7: The variation of the tangent incident wave angle,
$\beta_{tang}$ with decreasing wedge angle, $\theta$, and different values of
$\kappa$.  Figure 8: Comparison of the incident wave angle, $\beta$ measured
at the reflection/triple point and at the tangent of the incident wave shock,
with different values of $\kappa$.

### 3.2 Mach Stem Height

Figure 9: The variation of non-Dimensional Mach stem height with wedge angle,
with different non-dimensional angular velocities, $\kappa$.

The dynamic effect of the downstream impulsive motion of the trailing edge on
the development of the non-dimensional Mach Stem height, MS$/H$ is shown in
Figure 9. At a small value of $\kappa=0.1$, the MS invisibly increased by
$3.5\%$ within a degree, then it rapidly decreased till vanished at the
transitional wedge angle of $\theta_{t}=18.78^{\circ}$. The same manner
happened at a higher $\kappa=0.5$, the MS ascended with $9.7\%$ within
$2^{\circ}$ of the decreasing wedge angle and abruptly decreased till
vanishing and RR happens. Thus, increasing the impulsive motion speed,
$\kappa$, results in decreasing the dynamic transitional wedge angle, where
the MS disappears and RR occurs. Moreover, the lag strength was significant
using high values of $\kappa=(1.5,\ 2.0)$, as the MS remained constant for a
while before the obvious growth of the MS height during the descending of the
wedge incidence. Particularly, For $\kappa=2.0$, The MS value at the minimum
wedge angle of $\theta=10.5^{\circ}$ was $19.3\%$ higher than the initial
value of the MS at the steady-state wedge angle of $\theta_{i}=23^{\circ}$.

### 3.3 Shock Reflection Domain

Analytically, when a sharp compression ramp opposes a supersonic flow, there
are many possible shock wave systems, including the RR and the MR as
summarized by Mouton [15]. The wedge angle and the free-stream Mach number
influence the formation of a certain configuration. Figure 10 shows a
comparison between the dynamic von-Neumann transition wave angle using
different motion speeds to the theoretical transition criteria on the Duel
Solution Domain, DSD. As $\theta$ decreased with a certain value of $\kappa$,
the wave angle decreased, placing the dynamic transition tangent wave angle,
$\beta_{t_{tang}}$, beyond the theoretical von-Neumann condition. For low
motion rates, such as $\kappa=0.1$, the $\beta_{t_{tang}}$ was just below the
analytical limit. Using higher non-dimensional angular velocities, such as
$\kappa=1.0$, resulted in increasing the gap between the transition wave angle
and the physical steady-state limit. This was because of the dynamic shock
system’s extreme lag.

Figure 10: Comparison of dynamic transition wave angle, $\beta_{t_{tang}}$
with the theoretical steady transition wave angle, $\beta_{t_{sc}}$.

## 4\. Conclusion

The aim of the current paper is to numerically study the dynamic transition
from MR to RR for an inviscid supersonic flow of $M_{\infty}=3$ over a moving
wedge. The motion was achieved, by decreasing the wedge angle with different
non-dimensional angular velocities, $\kappa$, and keeping the wedge height
fixed. The dynamic transitional angles and the dynamic hysteresis were
analyzed to investigate the phenomenon. This research work concludes that the
non-dimensional angular velocity of the motion lagged the shock system,
causing the occurrence of the transitional angle below the theoretical von-
Neumann criterion in the Dual-Solution Domain. Moreover, the strength of the
lag is clearly observed in the Mach stem height, where the transition did not
happen at $\kappa=1.5$ and $2.0$ with our current geometric limits. Further,
the Sonic and von-Neumann criteria happened very close to each other as the
difference in the transitional angles was within a degree.

## References

  * Ben-Dor [1999] Gabi Ben-Dor.  Hysteresis phenomena in shock wave reflections in steady flows.  _Journal of Materials Processing Technology_ , 85(1-3):15–19, 1999.
  * Ben-Dor et al. [2002] G Ben-Dor, M Ivanov, EI Vasilev, and T Elperin.  Hysteresis processes in the regular reflection $\longleftrightarrow$ mach reflection transition in steady flows.  _Progress in Aerospace Sciences_ , 38(4-5):347–387, 2002.
  * Ben-Dor [2007] Gabi Ben-Dor.  _Shock wave reflection phenomena_ , volume 2.  Springer, 2007.
  * Ivanov et al. [2001] Mikhail S Ivanov, D Vandromme, VM Fomin, AN Kudryavtsev, A Hadjadj, and DV Khotyanovsky.  Transition between regular and mach reflection of shock waves: new numerical and experimental results.  _Shock Waves_ , 11(3):199–207, 2001.
  * Ivanov et al. [1997] M Ivanov, G Markelov, A Kudryavtsev, and S Gimelshein.  Transition between regular and mach reflections of shock waves in steady flows.  In _32nd Thermophysics conference_ , page 2511, 1997.
  * Yan et al. [2003a] H Yan, R Adelgren, G Elliott, D Knight, and T Beutner.  Effect of energy addition on mr $\rightarrow$ rr transition.  _Shock Waves_ , 13(2):113–121, 2003a.
  * Yan et al. [2003b] H Yan, R Adelgren, G Elliott, D Knight, M Ivanov, D Khotyanovsky, and T Beutner.  Control of mach reflection-regular reflection transition in dual solution domain by laser energy deposition.  In _Proc. 5 th Workshop Magneto-and Plasma Aerodynamics for Aerospace Applications_ , 2003b.
  * Naidoo and Skews [2011] Kavendra Naidoo and Beric W Skews.  Dynamic effects on the transition between two-dimensional regular and mach reflection of shock waves in an ideal, steady supersonic free stream.  _Journal of fluid mechanics_ , 676:432–460, 2011.
  * Naidoo and Skews [2014] Kavendra Naidoo and BW Skews.  Dynamic transition from mach to regular reflection of shock waves in a steady flow.  _Journal of fluid mechanics_ , 750:385–400, 2014.
  * Margha et al. [2021] Lubna Margha, Ahmed A Hamada, Doyle D Knight, and Ahmed Eltaweel.  Dynamic transition from regular to mach reflection over a moving wedge.  In _ASME International Mechanical Engineering Congress and Exposition_ , volume 85581, page V004T04A006. American Society of Mechanical Engineers, 2021.
  * Kurganov and Tadmor [2000] Alexander Kurganov and Eitan Tadmor.  New high-resolution semi-discrete central schemes for hamilton–jacobi equations.  _Journal of Computational Physics_ , 160(2):720–742, 2000.
  * Kurganov et al. [2001] Alexander Kurganov, Sebastian Noelle, and Guergana Petrova.  Semidiscrete central-upwind schemes for hyperbolic conservation laws and hamilton–jacobi equations.  _SIAM Journal on Scientific Computing_ , 23(3):707–740, 2001.
  * Greenshields et al. [2010] Christopher J Greenshields, Henry G Weller, Luca Gasparini, and Jason M Reese.  Implementation of semi-discrete, non-staggered central schemes in a colocated, polyhedral, finite volume framework, for high-speed viscous flows.  _International Journal for Numerical Methods in Fluids_ , 63(1):1–21, 2010.
  * Hirt et al. [1974] Cyrill W Hirt, Anthony A Amsden, and JL Cook.  An arbitrary lagrangian-eulerian computing method for all flow speeds.  _Journal of computational physics_ , 14(3):227–253, 1974.
  * Mouton [2007] Christopher Andre Mouton.  _Transition between regular reflection and Mach reflection in the dual-solution domain_.  PhD thesis, California Institute of Technology, 2007.

(a) $\theta=23^{\circ}$

(b) $\theta=22^{\circ}$

(c) $\theta=20^{\circ}$

(d) $\theta_{t}=18.7698^{\circ}$

(e) $\theta=18.5^{\circ}$

(f) $\theta=12^{\circ}$

Figure 11: Velocity gradient contours of the dynamic shock system at a low
non-dimensional angular velocity, $\kappa=0.1$, showing the dynamic transition
from MR to RR.

(a) $\theta=23^{\circ}$

(b) $\theta=20^{\circ}$

(c) $\theta=18^{\circ}$

(d) $\theta=14^{\circ}$

(e) $\theta=12^{\circ}$

(f) $\theta=10.57^{\circ}$

Figure 12: Velocity gradient contours of the dynamic shock system at a
relatively high non-dimensional angular velocity, $\kappa=1.0$.

(a) $\theta=23^{\circ}$

(b) $\theta=20^{\circ}$

(c) $\theta=18^{\circ}$

(d) $\theta=14^{\circ}$

(e) $\theta=12^{\circ}$

(f) $\theta=10.5^{\circ}$

Figure 13: Velocity gradient contours of the dynamic shock system at a high
non-dimensional angular velocity, $\kappa=2.0$.