$\tilde{\text{O}}$ptimal Distributed Maximum Flow Approximation in Undirected Planar Graphs

Õptimal Distributed Maximum Flow Approximation in Undirected Planar Graphs Yaseen Abd-Elhaleem∗ yaseenuniacc@gmail.com

Michal Dory† mdory@ds.haifa.ac.il

Oren Weimann‡ oren@cs.haifa.ac.il

Abstract

arXiv:2608.09500v1 [cs.DC] 10 Aug 2026

Persistent efforts in recent years have been devoted to devising distributed algorithms for fundamental optimization problems in planar graphs. In particular, for Single-Source Shortest-Paths, there is an Õ(D2 )-rounds1 exact algorithm [Li, Parter STOC’19] for directed planar graphs, and an Õ(D)rounds (1 + o(1))-approximation algorithm [Rozhon, Grunau, Haeupler, Zuzic, Li STOC’22] for undirected planar graphs (where D is the graph’s hop-diameter). Recently [Abd-Elhaleem, Dory, Parter, Weimann PODC’25], a matching bound for the exact case was obtained for the Maximum st-Flow problem. Namely, an Õ(D2 )-rounds exact algorithm for directed planar graphs. However, for the approximate case, they give a D · no(1) -rounds (1 − o(1))-approximation algorithm for undirected planar graphs that works only for the special case where both s and t lie on the same face. In this paper, we remove the restriction that both s and t must lie on the same face (we also eliminate the no(1) factor). Namely, we present the first distributed near-optimal Õ(D)-rounds (1 − o(1))-approximation algorithm for Maximum st-Flow in general undirected planar graphs. Our main technical contribution is a distributed implementation of the classical Reif’s [SICOMP’83] centralized algorithm. This is achieved by a careful recursive incision procedure on the planar dual G ∗ of the graph G. It is challenging, because we need to simulate dynamic changes (incisions) over the dual graph G ∗ , while we can only communicate over the input graph G.

∗

Department of Computer Science, University of Haifa. Supported in part by the Israel Science Foundation grants No. 810/21 and 2829/25. † Department of Computer Science, University of Haifa. Supported in part by the Israel Science Foundation grant No. 2829/25. ‡ Department of Computer Science, University of Haifa. Supported in part by the Israel Science Foundation grant No. 365/26. 1 The Õ(·) notation hides poly-logarithmic factors in n.

Contents 1 Introduction 1.1 Technical Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2 7

2 Centralized Reif 2.1 Extensions of Reif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Towards a Distributed Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 9 12

3 Distributed Reif 3.1 Definition of the Graph Ĝ‘ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Properties of Ĝ‘ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Planarity and Diameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Vertex-disjoint Face-parts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Correspondence to Annuli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.4 Simulation of Ĝ‘ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Distributed Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Simulation of Minor-aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Partwise-aggregation on Annuli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Standard Minor-aggregation on Annuli . . . . . . . . . . . . . . . . . . . . . . . . 3.4.3 Minor-aggregation on Annuli with Virtual-nodes . . . . . . . . . . . . . . . . . . .

16 16 24 24 26 29 31 31 35 35 37 38

4 Approximate SSSP and Eulerian Orientation 4.1 Eulerian Orientation on Annuli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Decomposing Annuli to Edge-disjoint Paths . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Orienting Edge-disjoint Paths in Annuli . . . . . . . . . . . . . . . . . . . . . . . . 4.2 SSSP on Annuli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39 41 43 44 50

5 Distributed Reif Implementation 5.1 The Procedure ShortestCycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Finding the Minimum st-cut and Flow Value . . . . . . . . . . . . . . . . . . . . . . . . . .

51 53 56

A Deferred Proof from Section 2.1 A.1 Proof of Lemma 2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Proof of Lemma 2.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59 59 59

1

Introduction

The maximum st-flow problem asks for the maximum amount of flow that can be sent from a source vertex s to a target vertex t in a graph with edge-capacities. The problem is one of the most fundamental and well-studied optimization problems in theoretical computer science. It was first presented in 1954 by Harris and Ross [20] who used the graph to model the Soviet railway network (which happens to be a planar graph). The first algorithm for the problem was given in 1956 by Ford and Fulkerson [11] in their seminal paper (still taught in every elementary algorithms class). This paper is known for introducing the celebrated min-max theorem, stating that the value of the maximum st-flow is equivalent to that of the minimum st-cut. It is less known, that in the same paper, Ford and Fulkerson also gave the first algorithm for maximum st-flow in planar graphs where both s and t lie on the same face (called st-planar graphs). In the centralized setting, after decades of research, the maximum st-flow problem is by now almost optimally resolved. Namely, in general graphs there are by now almost-linear time (i.e., optimal up to a subpolynomial factor) algorithms, with the currently fastest being [7]. In planar graphs, there are by now near-linear time (i.e., optimal up to a logarithmic factor) algorithms, with the currently fastest being O(n log n) in directed planar graphs [4] and O(n log log n) in undirected planar graphs [23]. Distributed planar graph algorithms. In the distributed CONGEST setting [29], we are given an nvertex graph G with hop-diameter D. Communication on G occurs in synchronous rounds, where in each round O(log n) bits can be sent along every edge. The goal is to minimize the number of rounds required to solve various optimization problems on G. In this setting, the exact maximum st-flow problem for general √ graphs is still open with the state-of-the-art being n1=2+o(1) · ( n + D) rounds [9].2 The approximate version, however, is resolved (up to subpolynomial factors) [16]. Namely, up to an no(1) factor, there is a √ tight lower and upper bound of (D + n)-rounds for approximate maximum st-flow [10,30,32], as well as for many other fundamental problems such as approximate single-source shortest-paths (SSSP) [34, 35] and exact minimum spanning tree (MST) [12, 26]. The graph used for these lower bounds [10, 30, 32] is sparse, of arboricity two, but not planar. This means that planar graphs are arguably one of the most interesting graph families to which the lower bound does not apply and the only lower bound is the trivial Ω(D). Nevertheless, the maximum st-flow problem is far from being resolved in planar graphs as we now elaborate. Near-optimal Õ(D)-round distributed planar graph algorithms were given in 2016 by Ghaffari and Haeupler for computing a planar embedding [13], for MST [14], and for approximate undirected global min-cut [14]. Other Õ(D)-round algorithms soon followed for approximate SSSP [34, 35], DFS [17, 24], undirected weighted girth [1], undirected global min-cut [18], reachability [28], and planar separators [2, 17,24,27]. For other problems, Õ(D2 )-round algorithms were developed. These include directed maximum st-flow [1], weighted directed SSSP [27], directed weighted girth [28], and directed global min-cut [1]. Notice that both maximum st-flow and SSSP have exact Õ(D2 )-round algorithms. Indeed, as we next explain, these two problems are highly related in planar graphs. However, while SSSP can be approximately solved in near optimal Õ(D)-rounds in undirected graphs, no such bound was known for approximating maximum st-flow. Recently, [1] gave an almost optimal D · no(1) -rounds (1 − o(1))-approximation for maximum st-flow, but only in undirected st-planar graphs (where s and t must lie on the same face). Our result. In this paper, we present the first near-optimal Õ(D)-rounds (1 − o(1))-approximation algorithm for maximum st-flow in undirected planar graphs. This improves the algorithm of [1] that is restricted to st-planar graphs (and also has an additional no(1) factor). Formally, we prove: Theorem 1.1. Let G be an undirected weighted planar network of hop-diameter D, and let s; t be two vertices whose ID is known to all vertices of G. Then, in Õ(D) deterministic rounds we can (1 − o(1))-approximate 2

In fact, [9] solve the more general problem of minimum-cost st-flow.

1

the value of the maximum st-flow (equivalently, (1 + o(1))-approximate the value of the minimum st-cut) s.t. every vertex v ∈ G knows this value. In addition, every v ∈ G learns on which side of the minimum st-cut v is, and v ’s incident edges that belong to the cut. Notice that we find the approximate value of the maximum st-flow by finding an approximate minimum st-cut. We also find the cut itself and not just its value. Finding the corresponding flow assignment distributively in the same Õ(D) round complexity remains an interesting open question.

1.1

Technical Overview

Given a planar graph G, its dual graph G ∗ is a planar graph whose nodes correspond to the faces of G. Two nodes are connected in G ∗ if their corresponding faces in G share an edge (see Figure 1a and a formal definition in Section 1.2). In the centralized setting, the driving force behind the algorithmic improvements to maximum st-flow was the gradual understanding of the connection between maximum st-flow in G and SSSP in G ∗ . This connection was already implicitly used by Ford and Fulkerson [11]. In 1981, Hassin [21] made the connection explicit by showing that in undirected st-planar graphs G, maximum st-flow reduces to a single SSSP computation in the dual G ∗ with positive edge-lengths. The D·no(1) -rounds maximum st-flow approximation of [1] is a distributed (and approximate) implementation of Hassin’s algorithm. In 1983, Venkatesan [36] showed that in general directed planar graphs (i.e., not just st-planar graphs) maximum st-flow reduces to log – SSSP computations in the dual G ∗ with positive and negative edge-lengths, where – is the maximum st-flow value. The Õ(D2 )-rounds exact maximum st-flow algorithm of [1] is a distributed implementation of Venkatesan’s algorithm. Note that the fastest known distributed algorithm for directed SSSP that allows negative edge-lengths takes Õ(D2 ) rounds [27]. In order to obtain a faster Õ(D)-round algorithm we use a different approach by Reif [31], which enables us to use a faster approximate SSSP algorithm that works for undirected graphs with non-negative edgelengths. Namely, in 1983, Reif [31] showed that in general undirected planar graphs, maximum st-flow reduces to multiple (as many as Ω(n)) SSSP computations on G ∗ (with positive edge-lengths) that can be executed efficiently in a divide and conquer manner as we next explain. We mention that the approach of Hassin, and therefore, the distributed approximation algorithm of [1], is inherently limited to st-planar graphs. I.e., there is no clear way of extending it to work for general s and t. That is because, Hassin’s algorithm starts by augmenting G with an edge e = (t; s), then performs a single SSSP computation on the dual of the augmented graph. This is fine when s; t are on the same face, for e can be embedded inside the common face, preserving planarity (i.e., the planar dual can still be defined). However, for general s and t, adding this edge violates planarity and the planar dual cannot be defined. Therefore, another approach is required. Here comes our contribution, which is a distributed implementation of Reif’s algorithm. The technical challenge compared to the approximation algorithm of [1] is that, we need to (distributively) support multiple simultaneous SSSP computations on G ∗ while G ∗ changes dynamically during the algorithm (undergoes incisions) rather than just one SSSP computation. Centralized Reif. In Section 2 we describe Reif’s algorithm in detail. Reif finds the value of the maximum st-flow by finding the equivalent value of a minimum st-cut. In planar graphs, the minimum st-cut in G is also equivalent to the shortest cycle C in the dual graph G ∗ that encloses exactly one of the two faces s ∗ ; t ∗ of G ∗ corresponding to s; t. See Figure 1. In order to find the cycle C, Reif uses the fact that if P is a shortest path in G ∗ connecting the two faces s ∗ and t ∗ , then C must cross P exactly once. Then, Reif makes an incision along the path P , duplicating P ’s edges and vertices. This way, the shortest cycle C becomes the shortest path Pi from a vertex pi of P to its copy. See Figure 2.

2

s=s∗

s∗

s f

g

t= t∗

t∗

t

(a)

(b)

(c)

Figure 1: (a) The primal graph G in blue and its dual G ∗ in red. (b) Two distinguished vertices s and t in G, and an st-cut (dashed). (c) The faces s ∗ and t ∗ of G ∗ , and the dual cycle to the st-cut C (dashed). C encloses s ∗ but not t ∗ . The node f (resp. g ) of G ∗ belongs to the face s ∗ (resp. t ∗ ).

C s∗

P pi

Pi

p0i

t∗

p0i

p1i

p1i

Figure 2: Left: The shortest cycle C in G ∗ that crosses P once and encloses t ∗ (not s ∗ ). Middle: The graph G ∗ after incising P , the pi0 -to-pi1 path Pi corresponds to the cycle C from the left image. Right: The two annuli (recursive subgraphs) of the first recursion level after incising Pi . Finding all such paths Pi can be done with multiple executions of an SSSP algorithm on G ∗ . Moreover, since the Pi paths do not cross, they can all be found very efficiently (total O(n log n) centralized time) in a (recursive) divide-and-conquer scheme. Namely, once we find some Pi we make an incision along it, thus, splitting the graph into two subgraphs: One containing every Pj for j < i and the other containing every Pj for j > i, so we can recurse on each subgraph separately. I.e., C is either Pi or some Pj in one of the two recursive subgraphs.3 . See Figure 2. We call these recursive subgraphs annuli since each of them is a subgraph sandwiched between two paths Pi ; Pj . See Figure 3. Pi Pj

Figure 3: An annulus bounded by paths Pi ; Pj . Distributed Reif. In this paper, we show how to implement (an approximate version of) Reif’s algorithm 3

If C does not correspond to Pi , then we can always assume it is included in one of the recursive subgraphs. Otherwise, it must cross Pi , in which case we can replace segments of C with segments of Pi in order to ensure that C is entirely contained in a single recursive subgraph. For more details see Section 2.

3

distributively.4 Our main contribution (Section 3) is in showing that distributed (approximate) SSSP computations can be executed efficiently on G ∗ while G ∗ undergoes incisions. More precisely, we show that the SSSP computations over all annuli in the same recursive level can be performed in Õ(D) rounds. This is quite challenging since G ∗ is not the communication network and since the diameter of G ∗ can be much larger than that of G. That is, we want to simulate the algorithm using our original communication network G and benefit from the fact that G is a planar graph with diameter D.

Figure 4: Left: The primal graph G (blue) and its dual G ∗ (red). For clarity, the (red) node corresponding to the external face is omitted. Right: The graph Ĝ0 of [17]. Note, each face of G corresponds to a (disjoint) black cycle of Ĝ0 , and each vertex of G has its (blue) star. The red edges of Ĝ0 have a 1-1 mapping to edges of G ∗ . To do so, we create a new graph Ĝ‘ that can be simulated on G and captures all recursive (dual) annuli in level ‘ of Reif. For the base case Ĝ0 , we just want to simulate an algorithm on the dual graph G ∗ . This was already done by [1, 17], who introduced a graph Ĝ that allows us to simulate basic algorithms based on aggregate operations (usually simple operations as broadcast, SUM, OR, etc.) on the graph G ∗ using the communication network G. Intuitively, in this graph, for each dual node f ∈ G ∗ there is a cycle representing the corresponding face in G. Two cycles that correspond to different faces are disjoint, and two cycles f ; g are connected by an edge if and only if there is a dual edge (f ; g ) in G ∗ . See Figure 4. There are additional vertices and edges that make the graph Ĝ similar to G. In particular, each primal vertex v is replaced by a star connecting it to all the cycles that correspond to faces f that include v . These extra vertices and edges make sure that the graph has O(D) diameter, and has similar structure to G, which allows us to efficiently simulate algorithms on Ĝ using the communication graph G. Our goal is to extend the graph Ĝ0 = Ĝ to the graph Ĝ‘ that allows simulating algorithms simultaneously on all annuli of a recursive level ‘ of Reif. Note that a dual node f in level ‘ can be either a dual node of G ∗ , or some duplicate of a node in G ∗ that we got after making incisions. We thus refer to it as a node-part. Note that when we incise along a path that contains the node f , the edges adjacent to f are split into two parts f1 ; f2 (where the edges of the path go to both sides), so the corresponding node-parts we get after one such incision are defined by a consecutive subset of the edges adjacent to f . If we look at these edges in the primal graph G, they correspond to a connected subgraph of the corresponding face f in G, we call these connected subgraphs face-parts p(f1 ), p(f2 ). Note that face-parts are not disjoint. First, each edge in the primal graph is part of two faces (i.e., incident to two different dual nodes). In addition, the two edges of the path we incised that are incident to f go to both p(f1 ) and p(f2 ). See Figure 5. In order to simulate algorithms efficiently, we want to have a disjoint connected subgraph for each such face-part p(fi ). To achieve this, in Ĝ‘ we duplicate each edge at most four times (once for each time it appears in a face-part p(f ) where f is a level-‘ node-part). We connect these edges in a way that for 4

The reason our algorithm is approximate is solely because we use an approximate SSSP algorithm as a black-box.

4

p̂(f1 )

p(f1 )

f1

f e2

f2

e1

p(f2 )

p̂(f2 )

Figure 5: Left: A node f ∈ G ∗ (in red) and its incident edges e1 ; e2 on the incision path. After the incision, all edges between e1 ; e2 (resp. e2 ; e1 ) get incident to the first (resp. second) node-part f1 (resp. f2 ). The blue cycle is the face (corresponding to) f in G. The face-parts p(f1 ); p(f2 ) in G are highlighted (green, and orange). Note that p(f1 ); p(f2 ) overlap in the edges (whose duals are) e1 ; e2 . Right: The node-parts f1 ; f2 resulting from f after the incision (each has its own copies of e1 ; e2 ). The transformation that Ĝ‘ applies on the face-parts p(f1 ); p(f2 ) of G results in (highlighted) vertex-disjoint components p̂(f1 ); p̂(f2 ) in Ĝ‘ . These components correspond to the node-parts, and each of them has its own copy of the edges e1 ; e2 . each level-‘ node-part f : (1) there is a connected subgraph p̂(f ) in Ĝ‘ , (2) subgraphs for distinct nodeparts are disjoint, and (3) two subgraphs p̂(f ); p̂(g ) are connected by an edge iff there is a dual edge in level ‘ between the corresponding node-parts f ; g . See Figure 5 and Figure 6. We show that in the graph Ĝ‘ , there is a connected component for each level-‘ annuli. Finally, similarly to the original Ĝ, we add another set of edges and vertices that make the graph similar to the original graph G. This is again done by replacing each vertex v with some copies connected by a depth-two tree instead of a star in Ĝ0 . Each copy connects v to a subgraph p̂(f ) for each node-part f where v ∈ p(f ). See Figure 6. p̂(f1 )

f1

p̂(g1 )

f2

g1 g2

p̂(f2 ) p̂(g2 )

Figure 6: Left: four node-parts g1 ; g2 of g ∈ G ∗ , and f1 ; f2 of f ∈ G ∗ , resulting from an incision over a path of G ∗ in which f ; g participate. In particular, f ; g are neighbors and the edge (f ; g ) is duplicated as a result of the incision (its duplicates are solid red). Right: the corresponding components in Ĝ‘ of the node-parts. Note, there is an edge (red) connecting p̂(gi ) and p̂(fi ) in Ĝ‘ for the edge (gi ; fi ) in the dual after the incision (i ∈ {1; 2}). We show that the resulting graph Ĝ‘ is planar, has diameter O(D), and has a structure similar to G which allows to simulate on it algorithms efficiently using the communication network G. Moreover, Ĝ‘ has a similar structure to the union of level-‘ annuli, which allows us to simulate Reif’s algorithm efficiently on them. Defining the graph Ĝ‘ is challenging. In particular, it aims to capture a structure of G, that in a sense is global (not only faces of G, but also face-parts of G and the way they interact after incisions). Since this information is not known a priori (our aim is to learn it via Ĝ‘ ), Ĝ‘ ’s definition 5

should rely merely on a more restricted (possibly local) information. E.g. the neighborhood of vertices and whether incident edges are incised in the dual. We succeed to define the graph Ĝ‘ that achieves both. A global structure with a local construction. In fact, we define one graph Ĝ‘ that captures the topology of all annuli of the same recursion level, simultaneously. Minor-aggregation on annuli. More concretely, we can simulate minor-aggregation algorithms (a certain type of algorithms that are based on contractions and aggregate operations, see Section 3.4), which is enough in order to simulate SSSP as needed for Reif. In particular, to simulate such algorithm we need to solve the part-wise aggregation problem, where the goal is to compute an aggregate function over different sets of nodes Si (where the sets Si are connected and disjoint from each other). We show that these sets Si on the dual graph correspond to connected disjoint subgraphs on the graph Ĝ‘ . Since Ĝ‘ is a planar graph of diameter O(D), we can simulate such computations on Ĝ‘ in Õ(D) rounds using low-congestion shortcuts [14,15,19] for planar graphs (see Section 3.3 and Section 3.4 for details). Using this approach, we can already obtain a D · no(1) round complexity for the (approximate) SSSP problems we need to solve. To do so, we can use as a black-box a minor-aggregation distributed SSSP algorithm [35]. Note that we use approximate SSSP for the lack of almost-D-rounds exact distributed SSSP. Nonetheless, we show that this does not impair the correctness of Reif’s algorithm, and that we get an approximation to the minimum st-cut (or maximum st-flow). The only issue with using the SSSP of [35] is its D · no(1) round complexity. To obtain the promised Õ(D)-round complexity we need an additional ingredient described next. Improved complexity via Eulerian orientation. In order to remove the no(1) factor and achieve our promised Õ(D) bound, we wish to use another SSSP algorithm [34]. This algorithm indeed requires Õ(D) rounds, but it is not a minor-aggregation algorithm. Specifically, exactly one procedure that it uses is not in the minor-aggregation model: a procedure that finds an Eulerian Orientation to a certain (Eulerian) graph H that is (roughly) a subgraph of the input graph to the SSSP algorithm. This problem in [34] asks to find an orientation to the edges of H, so that the in-degree equals the out-degree for all nodes. In our case, H is a (Eulerian) subgraph of an annulus. In Section 4 we show how to solve this problem distributively in Õ(D) rounds for all annuli of a given recursive level. A classical (centralized) solution [3] is: (1) nodes of H pair their incident edges, locally decomposing the graph into edge-disjoint cycles. Then, (2) orient each cycle consistently (thus, each two paired edges are oriented in opposite directions as needed). Trying to simulate this on annuli, we face two challenges: (1) A node f in an annulus is not a real node (it is a face-part, simulated by many nodes of G). I.e., it does not know its neighbors and cannot pair its edges. (2) In order to orient the resulting cycles, we need to run a procedure on all of those cycles simultaneously. However, we do not know how to simulate algorithms efficiently on multiple subgraphs of annuli that are not disjoint (note that the cycles share nodes). The first challenge can be solved on the face-part p(f ) of f . I.e., pairing consecutive pairs of edges on p(f ) directly implies a pairing on f ’s edges (here we use planarity). This can be computed by simulating aggregate computations on the (connected and disjoint) subgraphs p̂(f ) in Ĝ‘ . To deal with the second challenge, we augment the graph Ĝ‘ such that the cycles we need to orient correspond to disjoint subgraphs of Ĝ‘ . This is done by splitting some of the vertices of Ĝ‘ . Once the (subgraphs that map to) cycles are disjoint, we can solve the orientation problem in Õ(D) rounds using a minor-aggregation algorithm over the graph Ĝ‘ . Organization. In the remainder of this section, we review some preliminaries. In Section 2 we discuss Reif’s centralized algorithm in detail and introduce some useful notions and extensions for its distributed implementation. In Section 3, we provide our main contribution: A distributed simulation of incisions on the dual graph G ∗ using Ĝ‘ . In Section 4 we solve the aforementioned Eulerian orientation problem. Finally, Section 5 puts everything together and provides a concrete distributed implementation of Reif’s algorithm. 6

1.2

Preliminaries

We denote by G = (V; E) the undirected edge-weighted planar network of communication, and by D the network’s (unweighted) hop-diameter. We denote by G[S] the subgraph of G induced by a set of vertices or edges S. The CONGEST model. We work in the standard distributed CONGEST model [29]. Initially, each vertex knows only its unique O(log n)-bit identifier and the identifiers of its neighbors. Communication occurs in synchronous rounds. In each round, each vertex can send each neighbor a distinct O(log n)-bit message on their common edge. We assume that the edges of G are weighted and that the weights are polynomially bounded integers. Thus, the weight of an edge can be transmitted in O(1) rounds. This is a standard assumption in the CONGEST model. Planar embedding. Let G = (V; E) be an undirected planar graph. The geometric planar embedding of G is a drawing of G on a plane so that edges intersect only in vertices. A combinatorial planar embedding of G provides for each v ∈ G, the local clockwise order of its incident edges, such that, the ordering of edges is consistent with some geometric planar embedding of G. Throughout, we assume that a combinatorial embedding of G is known locally for each vertex. This is done in Õ(D) rounds using the deterministic planar embedding algorithm of Ghaffari and Haeupler [13].

C P

x

R

y

Figure 7: A (black) cycle C crossing the (red) path P at an x-to-y subpath R. Crossing Paths. Consider a path P = p0 ; p1 ; : : : ; pt . For an internal vertex pi , all the edges incident to pi that appear between (pi−1 ; pi ) and (pi ; pi+1 ) in the clockwise order of pi are said to be on the left side of P . Symmetrically, the edges that appear between (pi ; pi+1 ) and (pi−1 ; pi ) in the clockwise order of pi are said to be on the right side of P . Let P and C be undirected paths or cycles. We say that P and C cross at subpath R if (1) P and C share a proper (not a prefix or suffix) subpath R, and (2) The edges of C that follow and precede R are in different sides of P . See Figure 7. Notice that it is possible that R contains a single vertex. The dual graph G ∗ . The dual of the embedded primal planar graph G is an embedded planar graph, denoted G ∗ (see Figure 1). The nodes of G ∗ correspond to the faces of G. For every edge e in G there is an edge e ∗ in G ∗ that connects the nodes corresponding to the two faces of G that contain e (and a self-loop when the same face appears on both sides of an edge). Observe that if two faces of G share several edges then G ∗ has several parallel edges between these faces. I.e., G ∗ might be a multi-graph even when G is a simple graph. We refer to the vertices of G as vertices and to the vertices of G ∗ as nodes. We use the well-known duality (see e.g., [25, 31]) between primal cuts and dual cycles (see Figure 1c): Fact 1.2 (Undirected Cycle-Cut Duality). A set of edges C is a simple st-cut5 in an embedded connected undirected planar graph G if and only if C is a simple cycle in G ∗ that encloses exactly one of s ∗ ; t ∗ (the faces of G ∗ corresponding to the vertices s; t of G). 5

A simple st-cut is a cut whose removal disconnects the graph into exactly two connected components, one containing s and the other t.

7

2

Centralized Reif

In undirected planar graphs (Fact 1.2), the weight of a minimum st-cut (or maximum st-flow) is equivalent to the length of the shortest cycle C in G ∗ that encloses exactly one of the faces s ∗ ; t ∗ . Reif’s centralized algorithm (Algorithm 1) from the 80’s [31] finds this cycle C in O(n log n) time, using the following. Claim 2.1 (Reif [31]). Let f (respectively g ) be any node of G ∗ that belongs to s ∗ (respectively t ∗ ). Let P be a shortest f -to-g path in G ∗ . The shortest cycle C in G ∗ that encloses exactly one of the faces s ∗ ; t ∗ is the shortest cycle in G ∗ that crosses P exactly once. Intuitively, C must cross P at least once, because it encloses exactly one of s ∗ ; t ∗ . Moreover, we can assume that not more than once, because if it crosses P at subpaths R1 and R2 then the subpath of C between R1 and R2 can be replaced with the subpath of P between R1 and R2 , which is a shortest path (note this argument only holds in undirected planar graphs). Algorithm 1: Reif’s algorithm Input: A D-diameter positively weighted undirected planar network G, and two vertices s; t ∈ G Output: A minimum st-cut 1 Compute an f -to-g shortest path P ; /* f ; g ∈ G ∗ and f ∈ s ∗ ; g ∈ t ∗ */ 2 Incise along P (results in a graph A) 3 return ShortestCycle(A, 0, |P | − 1) 4 Procedure ShortestCycle(A, j, k): /* Pj ; Pk define the annulus A */ 5 if k ≤ j + 1 then return argmin{|Pk |; |Pj |} ; /* leaf annulus */ 6 Compute Pi for i := ⌊(j + k)=2⌋ 7 Incise Pi and contract common paths (results in annuli Al ; Ar ) 8 return argmin{|Pi |, |ShortestCycle(Al , j, i)|, |ShortestCycle(Ar , i, k)|} To find C, Reif uses divide-and-conquer, based on the following. Let Ci be the shortest cycle that crosses P exactly once at a subpath that contains node pi of P . We can assume that Ci does not cross any other Cj because both are shortest cycles (the proof is similar to that of Claim 2.1). Reif’s algorithm computes all cycles Ci and declares the shortest one to be C. First, the cycle Ci is computed for i = |P |=2. The cycle Ci divides the graph G ∗ into two subgraphs: the one enclosed by Ci , and the one not enclosed by Ci . The algorithm recurses on both subgraphs.

Cj

Ck

pj

pk

Figure 8: An annulus (orange) sandwiched between two cycles Cj ; Ck . Note that at most half of P ’s vertices are strictly enclosed by Ci and at most half are not strictly enclosed by Ci . Thus, the recursion depth is logarithmic. Observe that if Ci and P share a common pi1 -topi2 subpath containing pi , then we do not need to recursively compute Ct for any i1 < t < i2 since one of Ci1 or Ci2 must be as short as Ct or shorter. A formal proof is provided later in Claim 2.4. Moreover, since 8

Ci s do not cross, all subgraphs in the same recursion level are internally disjoint. That is, every recursive subgraph (called annulus) is the subgraph sandwiched between two cycles Cj ; Ck . See Figure 8. The goal of the recursive call in the annulus bounded by Cj and Ck is to compute (inside the annulus) the cycle Ci for i = ⌊(j + k)=2⌋. Note that two annuli in the same recursion level can intersect only in their bounding cycles. Before computing all cycles Ci , Reif initially makes an incision along P (duplicating P ’s edges and vertices, see Figure 2): Definition 2.2 (Incision along P ). Splits every node pi of P into two duplicates pi0 and pi1 called node0 ) and (p 1 ; p 1 ), and each edge (p ; f ) parts. Every edge (pi ; pi+1 ) of P is replaced by two edges (pi0 ; pi+1 i i i+1 0 1 is replaced by an edge (pi ; f ) (resp. (pi ; f )) if it emanates left (resp. right) from P . There is a subtle point regarding the endpoints of P : they are incident to only one edge of P and two are required in order to define left and right. We therefore choose a non-P edge of s ∗ (resp. t ∗ ) that is incident to p0 (resp. p|P |−1 ) to define left and right (and thus the duplicates) of p0 (resp. p|P |−1 ). A broader discussion on endpoints of P appears in Remark 3.3, Section 3.1.

t = t∗

p01

p1

e0

p2

p00

e2 p0

p11

p02 p12

p10

s = s∗

Figure 9: Left: The primal graph G in blue and its dual G ∗ in red. The path P is p0 ; p1 ; p2 . The edges e0 ; e2 are the two non-P edges that are incident to P ’s endpoints in order to define the incision for them. Right: the dual graph after making an incision along P . The goal of this incision is that Ci before the incision is equal to the shortest pi0 -to-pi1 path Pi after the incision, and Pi (being a shortest path and not a cycle) can be found by an SSSP computation. Moreover, Pi does not cross Pj for any j ̸= i for the same reason that Ci does not cross Cj . Therefore, after finding Pi we can make an incision along Pi . Incising Pi is similar to incising P (Definition 2.2) in the sense that we duplicate nodes and edges of Pi . However, it is more delicate as we need to make sure not to duplicate edges of Pi that overlap with a previously incised path such as P or some Pj (which would lead to high congestion). We discuss this and formally define incisions on Pi s shortly in Section 2.1. The incision along Pi then guarantees that all the annuli in a given recursive level ‘ are connected and disjoint. We prove this formally in Section 2.2. In the centralized setting, finding Pi in an annulus can be done in time linear in the size of the annulus by using the linear time (exact) SSSP algorithm of [22]. Since the annuli in every recursion level are disjoint, this sums up to O(n) time per level and therefore to O(n log n) time overall.

2.1

Extensions of Reif

We introduce here two small changes to Reif’s algorithm (marked in red in Algorithm 2) that do not affect his original centralized version but are needed for our distributed version. 9

Algorithm 2: Extended Reif Input: A D-diameter positively weighted undirected planar network G, two vertices s; t ∈ G, and a precision parameter (log n)−O(1) ≤ ›. Output: A (1 + ›) approximate minimum st-cut 1 Compute an f -to-g shortest path P 2 Incise along P (results in a graph A) 3 return ShortestCycle(A, 0, |P | − 1) 4 Procedure ShortestCycle(A, j, k): 5 if k ≤ j + 1 then return argmin{|Pk |; |Pj |} 6 if Pj ∩ Pk ̸= ∅ then /* do not recurse on overlapping annuli */ 7 Compute a (1 + ›) approximate SSSP tree T from x ∈ Pj ∩ Pk 8 return the minimal pt0 -to-pt1 path in T for j ≤ t ≤ k 9 end 10 Compute a (1 + ›) approximate path Pi , for i := ⌊(j + k)=2⌋ 11 Let Pi′ be the maximal subpath of Pi that is internally-disjoint from (copies of) P , and let pi01 ; pi12 be the endpoints of the common subpath of Pi and (copies of) P . /* Pi intersects P with a subpath */ 12 Incise Pi′ (results in annuli Al ; Ar ) 13 return argmin{|Pi |, |ShortestCycle(Al , j, i1 )|, |ShortestCycle(Ar , i2 , k)|} Overlapping annuli. Since Reif assumes that the total number of edges over all annuli of the same level is O(n), whenever we incise a path Pi , we must make sure that we do not duplicate edges too many times. Reif takes care of this as follows. Consider the second time we want to incise an edge of G ∗ . This can only happen when there is an annulus sandwiched between two paths Pk ; Pj , and the path Pi (for i = (k +j)=2) shares a common subpath (between two nodes x and y ) with Pk or Pj (or both). See Figure 10. To cope with this, Reif used the following simple solution: Assume Pi shares a common x-to-y subpath with Pk (the case of Pj is similar), then all paths Pt for k ≤ t ≤ i must also share this x-to-y subpath. Therefore, before making an incision along Pi and recursing into the annulus sandwiched between Pk and Pi , Reif contracts the x-to-y subpath into a single edge. Similarly, if Pi and P share a common subpath then Reif contracts this subpath before recursing. Unfortunately, simulating such subpath contractions is infeasible in the distributed setting. This is because the contracted edges of G would have too many corresponding dual edges in a given level of recursion, leading to high congestion. Luckily, as we show next, this can be solved easily. First consider the case that Pi shares a common x-to-y subpath with Pk . Instead of contracting the x-to-y subpath, we apply the following simple solution: since all paths Pt for k ≤ t ≤ i must share the x-to-y subpath, we compute an SSSP tree from x, which provides the distances from x to every pt0 and pt1 . Then, for k ≤ t ≤ i, we can declare Pt to be the concatenation of the shortest pt0 -to-x and x-to-pt1 paths. This takes care of the entire Pk ; Pi annulus and (in contrast to Reif’s contraction) we are then done with the annulus (i.e., we do not recurse into it). Claim 2.3. Let A be an annulus bounded by paths Pk ; Pj where k < j. Assume that Pi for i = ⌊(j + k)=2⌋ shares a node x with Pk (resp. Pj ). Then, every path Pt for k ≤ t ≤ i (resp. i ≤ t ≤ j) is the concatenation of the x-to-pt0 and the x-to-pt1 paths in A. Proof. Every path Pt for k ≤ t ≤ i (the i ≤ t ≤ j case is similar) starts from the vertex pt0 that lies on 0 the cycle formed by pk0 ; pk+1 : : : pi0 and the prefixes of Pk and Pi ending in x. The path Pt must exit this 1 cycle since pt is external to the cycle. The only way to exit the cycle is through x and so Pt must touch x 10

x Pk

Pt

Pi

Pi

Pi

Pt

p0t

p0i1 p0t

p0i =p0i2

p1t p1a p1i =p1i2

p1t

p0i1 p0i p0t p1i p1t p1i2

y

Figure 10: Pi shares the (yellow) x-to-y subpath with Pk . All paths Pt for k ≤ t ≤ i also share this subpath. Red paths are incision duplicates of P .

Figure 11: The path Pi shares a common (yellow) subpath with P . For every node pt along this subpath we have that |Pi1 | ≤ |Pt | or |Pi2 | ≤ |Pt |. In the right (left) image, the common subpath contains (does not contain) an edge of P and its copy.

(and is therefore the concatenation of the x-to-pt0 and the x-to-pt1 paths). See Figure 10. Second, consider the case that Pi shares a common subpath with P . In this case, instead of contracting this common subpath (as Reif does), when incising along Pi we do not incise along the common subpath, and only incise on the rest of Pi . All nodes pt that lie (strictly) on the common subpath simply do not compute their Pt recursively. This is possible by the following claim (see also Figure 11). Claim 2.4. Assume that Pi shares a common pi1 -to-pi2 subpath with P . Then, for every pt where i1 < t < i2 we have that either Pi1 or Pi2 is not longer than Pt (i.e., we do not need to compute Pt ). Proof. Consider first the case where the common subpath does not contain an edge of P and its copy (see Figure 11 right). If Pt is enclosed by Pi (the other case is symmetric) then Pt must include a proper suffix of the pi1 -to-pi2 subpath of P . Otherwise, Pt has to cross Pi and we know this is forbidden. Having a shared suffix means that, while Pt is a pt0 -to-pt1 path it can also be seen as a pi02 -to-pi12 path. I.e., Pi2 cannot be longer than Pt . Now consider the case where the common subpath does contain some edges of P and their copies (see Figure 11 left), and again assume w.l.o.g. that Pt is enclosed by Pi . In this case, Pt must begin with a pt0 -to-pa1 prefix where pa1 belongs to Pi . This prefix cannot be shorter than the pt0 -to-pa1 subpath of Pi (for otherwise Pi would use it) that passes through pi01 . This implies that Pi1 cannot be longer than Pt . We conclude with a characterization of incisions on Pi s. See Figure 2 and Figure 12. Remark 2.5 (Incision along Pi ). Let A be an annulus defined by paths Pj ; Pk . Claim 2.4 and Claim 2.3 allow us to define incisions on the path Pi (i = ⌊(j + k)=2⌋) as follows. We incise (duplicate) only edges of the maximal subpath Pi′ of Pi that is internally-disjoint from P . If Pi shares a subpath with Pj or Pk , we exclude those edges too from the incision. The edges we incise as in the above remark, together with the already incised edges of Pi , imply that all edges of Pi are now incised once but not more. Moreover, this incision on Pi defines an internal (resp. external) annulus of A that is sandwiched by Pi ; Pk (resp. Pj ; Pi ). Such annuli might be discarded in case Pi intersects Pk (or Pj ) because in this case (overlapping annuli) we terminate the recursion. Henceforth, we obtain the following lemma (a full proof is provided in Appendix A). Lemma 2.6. Every edge of G ∗ is incised at most once in our implementation of Reif. 11

f′

f′

Pk Pi

Pi

Pj

Pj

p0i

p0i

Figure 12: Left: An annulus of level ‘ − 1 bounded by paths Pk ; Pj . pi0 ∈ Pi is a node-part of pi ∈ P . The node-part f ′ ∈ Pi is not a node of P . Red highlighted edges are edges of Pi incident to f ′ and pi0 . Right: the annulus defined by Pi ; Pj in level ‘. Approximate Reif. The second change we do to Reif’s algorithm is to turn it from an exact to an approximate algorithm. That is, we wish to compute P as well as every Pi with a (1 + ›)-approximate (rather than an exact) SSSP algorithm, simply because there is no distributed exact algorithm with an Õ(D) round complexity. It is not immediately clear that the correctness of Reif’s algorithm holds in this case (i.e., finds a (1 + ›)-approximate minimum st-cut). In particular, the crucial property that Pi s do not cross (which relies on the triangle inequality) does not immediately hold. However, we show that it does hold if the approximate SSSP algorithm obeys the approximate triangle inequality property (see formal definition in Appendix A). This property implies that any u-tov subpath of a (1 + ›)-approximate shortest path Pi returned by the SSSP algorithm is also a (1 + ›) approximation to the u-to-v shortest path. The approximate shortest paths algorithm of [34] that we use does not admit this property. Using a reduction of [33], we augment [34]’s SSSP algorithm to have this property (see Section 4.2). Lemma 2.7 (Approximate Reif). Using a (1 + ›)-approximate SSSP algorithm that obeys the approximate triangle inequality, setting › = O(›′ = log n) ensures that all Pi s do not cross and are (1 + ›′ )-approximate shortest pi0 -to-pi1 paths. The correctness of approximate Reif follows from the above lemma. The proof is simple and is given in Appendix A. Intuitively, starting from a (1 + ‹) approximate shortest pj0 -to-pj1 path Pj′ , we can replace each segment of Pj′ that crosses Pi with a subpath of Pi . We do the same if Pj′ intersects P until we have a path Pj that does not cross any Pi and intersects (each of the two copies of) P with at most one subpath. Doing this, each time we lose at most an additional (1 + ›) factor in the approximation.

2.2

Towards a Distributed Implementation

The challenge in applying (an approximate version of) Reif’s algorithm distributively is performing the incisions on the dual graph G ∗ . In particular, a face f of G does not exist as an atomic computational unit, meaning, there is no entity that knows (even basic) information about f . E.g. the number of edges in f , or the identities of f ’s neighbors in G ∗ and their ordering (embedding) around f . In Section 3 (our main technical contribution) we discuss how to overcome this and perform incisions on G ∗ distributively. Namely, we show that a decomposition of G ∗ by incisions can be learned and simulated without any vertex of G knowing the entire information related to a face f . Moreover, we show how to simulate minor-aggregation algorithms on G ∗ while doing incisions (i.e., on the annuli obtained from the incisions). 12

The minor-aggregation framework [18,35] is an interface for recursive edge-contraction based algorithms, that can be implemented in CONGEST using the well-known tool of low-congestion shortcuts [14, 15, 19]. The (approximate) SSSP algorithm of [34] that we use, is (mostly) a minor-aggregation algorithm. In particular, it has only one component that is not a minor-aggregation. In Section 4 we show how to overcome this. We next define some notions and prove several properties on the structure of annuli (and related graphs in G). These will be useful for the distributed implementation. We view Reif’s recursive incisions as a tree T . Definition 2.8 (Incision decomposition T ). The root of T corresponds to the entire graph G ∗ . The root has a single child corresponding to the graph obtained from G ∗ by performing an incision along the path P . Every other node of T corresponds to an annulus sandwiched between two paths Pk ; Pj as in Reif’s algorithm (it is possible that one of Pk ; Pj is empty). Such a node has at most two children defined by the annulus sandwiched between Pk ; Pi and the annulus sandwiched between Pi ; Pj for i = ⌊(j + k)=2⌋ (i.e., the two annuli resulting from making an incision along Pi ). Recall that if Pi intersects Pk , then we do not recurse into the Pk ; Pi annulus and so there is only one child (corresponding to the annulus Pi ; Pj ). Similarly for the case where Pi intersects Pj . If Pi intersects both Pj ; Pk then there are no children (this is a leaf node). Another halting condition (leaf node) is when j = k + 1, i.e., the annulus contains only two (consecutive) nodes of P . Nodes and edges of annuli in T . Recall that an incision duplicates nodes f in the current level to new duplicates in the next level. We can view this process as splitting nodes f ∈ G ∗ into two node-parts, and splitting f ’s edges between them. Note that each such node-part f ′ is incident to a consecutive subset of edges of the node f ; and recursively (in later incisions) f ′ will be split into node-parts each incident to a smaller consecutive subset of edges of f ′ . Since we duplicate incised edges, each duplicate of an edge incident to a node f ∈ G ∗ belongs to only one node-part f ′ of f . Namely, the two edges in the incision path incident to f have two copies, each in a separate node-part f ′ . We now formalize this. Definition 2.9 (Node-parts). A node-part f ′ of a node f ∈ G ∗ , defined by a pair of edges e1 ; e2 incident to f in G ∗ , is incident to all edges between e1 and e2 in f ’s clockwise order. 6 The next claim follows from the above. See Figure 12. Claim 2.10. In any level ‘ of T , all nodes in annuli of level ‘ follow the definition of node-parts (Definition 2.9). Moreover, the consecutive subsets of edges of f ∈ G ∗ that define node-parts in level ‘, are disjoint, except in their first or last edge. These (first and last) edges are (possibly) duplicated as a result of an incision, such that, each duplicate is incident to a distinct node-part. Proof. We prove formally by induction on levels of T . Obviously, the claim holds for level zero (the graph G ∗ ). In addition, from the definition of an incision on P (Definition 2.2), the claim is immediate for level one (G ∗ after incising P ). Assume the claim holds for a general level ‘ − 1 ≥ 1, we prove for level ‘. Recall, given a non-leaf annulus A defined by paths Pk ; Pj (k < j), we incise on Pi (i = ⌊(j + k)=2⌋) to obtain (node-parts of) A’s child annuli in level ‘. For non Pi nodes, no change (incision) happens, hence, the claim holds for such nodes that participate in a level ‘ annulus. Thus, it is enough to prove for nodes of Pi . A node f of G ∗ that is on Pi and was not incised earlier, is incised for the first time now, producing two node-parts in different annuli of level ‘. The claim follows from the definition of incisions on Pi Remark 2.5. We now consider a node-part f ′ ∈ Pi of a node f ∈ G ∗ that resulted from an incision in an earlier level. See Figure 12. If f ′ is an internal node of Pi and also on one of Pk or Pj (w.l.o.g. f ′ ∈ Pk ), then it defines 6

Including e1 ; e2 . We follow this convention throughout the paper, unless when stated otherwise.

13

(at most) one node-part in level ‘ containing all its edges internal to Pi (see Remark 2.5, and Figure 12). Thus, the claim holds. Otherwise, if f ′ ∈ = Pk ; Pj and was incised before, then, it lies on a common subpath of Pi and (copies of) P . By Remark 2.5 of incisions on Pi , we do not incise f ′ (the claim holds), except when f ′ is an endpoint of the internally-disjoint subpath of Pi from P . In that case, f ′ is split to (at most) two node-parts, defined by two consecutive subsets of edges of f ′ that overlap with exactly one edge (see Remark 2.5, and the node f ′ = pi0 in Figure 12). I.e., the claim still holds. The next corollary directly follows from the above proof, and is important to the distributed implementation. Corollary 2.11. Each node f ∈ G ∗ has several node-parts7 in any given level of recursions. Some of which do not proceed to the next level’s annuli. E.g. if their annuli were discarded. I.e., in each level of recursion, a node f ∈ G ∗ may have some (residual) node-parts that do not participate in any annulus. Finally, Since the nodes (node-parts) of an annulus are incident to their own copies of edges that define them, we obtain the following claim. Claim 2.12. In any given level of T , all annuli are connected and disjoint. Proof. We prove by induction on levels of T . Obviously, the claim holds for level zero (G ∗ ). In addition, from the definition of an incision on P (Definition 2.2), the claim is immediate for level one (G ∗ after incising P ). I.e., there is only one connected annulus in the level. The annulus is connected because the incision over P duplicates P , but both its duplicates are connected to the other (via the faces s ∗ ; t ∗ ). Thus, all nodes of the annulus (that were reachable to each other via P ) are reachable to each other via the cycle composed of the two copies of P and the edges of the faces s ∗ , t ∗ of G ∗ . We assume the claim holds for level ‘ − 1 ≥ 1 and prove for level ‘. Let A be an annulus of level ‘ − 1, then, it is enough to show that the claim holds for the child annuli of A (if any). Assume that A is sandwiched between paths Pk ; Pj (k ≤ j), and assume k +1 < j (otherwise A is a leaf of T ). Thus, A might have child annuli after incising Pi for i = ⌊(k + j)=2⌋. Let Pi′ be the subpath of Pi that gets incised. I.e., the maximal subpath of Pi which is internally disjoint from copies of P (see Remark 2.5). Then, assume Pi′ does not intersect Pk , thus, one child annulus of A is sandwiched between Pk ; Pi′ (otherwise, Pi′ ; Pk do not define an annulus, and the claim holds trivially). The case of Pj ; Pi′ is symmetric. We prove that this child annulus is connected and is disjoint from the other child of A (if any). The connectivity property is simple. Denote the endpoints of Pi′ by px0 ; py1 . Note that Pi′ can be completed to a cycle, denoted C, if one adds the edge (px0 ; py1 ). Adding this edge does not violate planarity, because it can be embedded inside the face that contains the copies of P . We stress that we add this edge for the sake of the proof only (i.e., this is not simulated in the algorithm). As known, any cycle in a planar graph is a separating cycle [25]. I.e., the removal of the cycle disconnects the graph into two, its interior and its exterior. In particular, nodes of C are exactly the nodes of Pi′ . Hence, incising Pi′ is the same operation as incising C and then removing the duplicates of the artificial edge (px0 ; py1 ). This obviously proves the disjointness argument because duplicates of C are node-disjoint, and each duplicate is connected either to edges that are only strictly internal or only strictly external to C. Obviously, removing the duplicate of the edge (px0 ; py1 ) to get back the child annulus of A does not weaken the disjointness argument. The connectivity property is proved via a similar argument. Note that, the annulus A after adding the artificial edge is connected (A is connected). In particular,nodes of C are connected to all nodes internal to C via the interior of C. Otherwise, there are two internal nodes f ; g that are connected via an external node h and without any node of C. This contradicts C being separating. An analogous argument holds for the exterior of C. Thus, incising C keeps its interior (exterior) connected via C itself, and therefore, the 7

In fact up to four, this follows from the definitions of incisions on P and Pi . However, we do not prove neither use this fact.

14

child annuli of C: Removing the duplicate of the edge (px0 ; py1 ) to get back the child annuli of A does not weaken the argument, because, the endpoints of the edge (px0 ; py1 ) remain connected via the copy of the path Pi′ that results from the incision. Correspondence to G (face-parts). In terms of the primal graph, a face f of G (corresponding to a node) f ∈ G ∗ gets split into smaller and smaller parts whenever f is split into node-parts. Each associated with a connected subgraph of the face f in G, called, face-part (See Figure 13):

e1

e2

Figure 13: A (dual) node-part f ′ of f ∈ G ∗ . Its incident edges (between e1 and e2 , clockwise) in solid red. Dashed red edges are in f and not in f ′ . The corresponding (primal) face-part p(f ′ ) is solid blue. Dashed blue are edges of the face f that are not in p(f ′ ). Claim 2.13 (Face-parts). A node-part f ′ of a node f ∈ G ∗ corresponds to a connected subgraph of the face f in G, that we denote as the face-part p(f ′ ). I.e., p(f ′ ) contains all edges of G whose duals are incident to f ′ . The proof follows from the formal definitions of faces and duality (see e.g., Chapter 4 of [25]). Intuitively, the face-part p(f ′ ) is a simple path (or a simple cycle when e1 = e2 ) if the face f is a simple cycle in G. Generally, p(f ′ ) can be a tree since f can be a simple cycle with attached trees in its interior. Our goal is to perform aggregations on face-parts, which will enable us to simulate minor-aggregation algorithms simultaneously on all annuli in a given level of Reif’s recursion. This extends an existing tool for aggregations on faces (as opposed to face-parts) by [17], which enables minor-aggregation algorithms on the graph G ∗ (without incisions) [1].8 This will be possible because face-parts overlap in a restricted manner: Claim 2.14. An edge e ∈ G ∗ has at most four copies in any given level of T . I.e., e ∈ G participates in at most four face-parts (two for each face of G that contains e). Proof. Every (dual) edge e is incident to two dual nodes in G ∗ . Since e is incised at most once (Lemma 2.6), then e can participate only in two node-parts (of each endpoint). I.e., for each endpoint f of e after the incision, a copy of e is created and gets incident to one node-part of f ; one whose incident edges start with e and the other whose incident edges end with e (see Definition 2.2, and Remark 2.5 where incisions are discussed). The correspondence to face-parts follows from Claim 2.13. Claim 2.15. In an annulus A, for each node-part g of a node f ∈ G ∗ there exists exactly one node-part h of f in the parent of A in T s.t. g is defined by a consecutive subset of edges of h. I.e., p(g ) is a subgraph of p(h). 8

We remark that [1] defined a different notion of face-parts in a different section of their paper and for a different purpose. However, their minor-aggregation simulation only works for the graph G ∗ with nodes that correspond to faces (and not to face-parts).

15

Proof. Let h be a node-part of f ∈ G ∗ in an annulus A′ . We assume h gets incised (otherwise the claim is trivial). In all cases of an incision on h (see Definition 2.2 and Remark 2.5) the resulting node-parts g in child annuli A of A′ , are defined by subsets of consecutive edges of h (thus of f ). Note, g cannot be defined by a subset of consecutive edges of any other node-part h′ ̸= h of f in A′ , because, the sequences of edges that defines h and h′ do not share a sequence of (ordered) edges (Claim 2.10). The claim regarding face-parts follows from the correspondence to face-parts (Claim 2.13).

3

Distributed Reif

The main building block we need in order to simulate Reif’s algorithm distributively is a method for running an approximate SSSP algorithm (such as [34, 35]) simultaneously on all annuli of a given level ‘ of T . In this section we show how to achieve this for any Minor-Aggregation algorithm [18, 35] (i.e., not only approximate SSSP, but any recursive algorithm that is based on edge-contractions). Notice that even the most basic unit such as a single node-part f in an annulus, is not an actual entity in the communication network G. We therefore simulate f by its corresponding face-part p(f ) in G. This is challenging, because the face-parts p(f ): (1) overlap in vertices and edges by Claim 2.14, (2) may have a large diameter, and (3) are connected to other incident face-parts. To overcome this, we design a certain virtual graph Ĝ‘ that is closely related to G, and that at the same time captures level-‘ annuli in T . In particular, running a minor-aggregation algorithm simultaneously on annuli translates to running an algorithm on Ĝ‘ . In addition, since Ĝ‘ is closely related to G, we will be able to simulate CONGEST efficiently on it. This allows to run minor-aggregation algorithms on annuli (dual subgraphs) via communication on G efficiently. We note that the SSSP algorithm of [34] that we use is in fact not a minor-aggregation algorithm. In Section 4 we will show how to overcome this with a small change to Ĝ‘ . Section organization. In Section 3.1 we define the graph Ĝ‘ , and we prove its properties in Section 3.2. Then, in Section 3.3 we show how to use Ĝ‘ to learn the needed distributed knowledge of a level ‘ in T . E.g. IDs of annuli and IDs of node-parts. Finally, in Section 3.4, we show that we can simulate any minor-aggregation algorithm simultaneously on all annuli of the same level ‘ of T , in a near-optimal round complexity.

3.1

Definition of the Graph Ĝ‘

For a level ‘ of T we define a graph Ĝ‘ that: (1) maps every face-part p(f ) to a unique vertex disjoint component so that we can run algorithms on all of them without worrying about them overlapping, (2) captures the topology of level-‘ annuli (represents node-parts and the edges incident to them), and (3) can be simulated efficiently on G itself. Concretely, in this graph Ĝ‘ , each p(f ) is mapped to a unique (vertexand edge-disjoint) path p̂(f ) (or to a cycle when p(f ) is an entire face of G). We begin with the special case of ‘ = 0. In this case, there is only one annulus (the graph G ∗ itself) and each p(f ) is simply an entire face of G. This case follows from [17], where they define the graph Ĝ0 (they called it Ĝ) that is defined as follows (see Figure 14): Every vertex v ∈ G has a copy vertex vf in Ĝ0 for each face f that v participates in. The edges of Ĝ0 are of three types which we call ER ; ES ; EC . ER : For every face f of G, for every two vertices u; v that lie consecutively on f there is an edge (uf ; vf ) in ER . Notice that every such edge (u; v ) in G belongs to two faces, f and g . Hence, we also have the edge (vg ; ug ) in ER . This way, the edges in ER corresponding to every face f constitute a (disjoint) cycle p̂(f ) that simulates f in Ĝ0 . ES : With the edges ER , the graph Ĝ0 is a disconnected graph that is merely a union of disjoint cycles. To make Ĝ0 connected and of diameter O(D), the edges ES are added to Ĝ0 . Namely, an additional copy 16

Figure 14: Left: The primal graph G (blue) and its dual G ∗ (red). For clarity, the (red) node corresponding to the external face is omitted. Right: The graph Ĝ0 . Blue vertices are star-center copies of v . Black vertices are copies vf of v . ER , ES , and EC edges are black, dashed blue, and red (respectively). of v (simply denoted by v ) is added to Ĝ0 . Each copy vf of v is connected to v by an edge (v ; vf ) in ES , creating a star-shaped graph in Ĝ0 for each v ∈ G. The center of the star is v , and the star edges are (v ; vf ). The choice of a star (and not a clique for example) keeps Ĝ0 planar. EC : The last set of edges EC (which was implicit in [17] and discussed more explicitly by [1]) is intended to mimic the topology of G ∗ . Namely, it connects the cycles p̂(f ); p̂(g ) with an edge ê = (vg ; vf ) iff there is an edge e ∗ = (f ; g ) in G ∗ . In [1, 17], it was shown that we can simulate minor-aggregation algorithms on G ∗ by running them on Ĝ0 . Specifically, because (1) the topology of G ∗ (captured by EC edges) allows translating problems on G ∗ into problems on Ĝ0 , which can then be solved straightforwardly on Ĝ0 because (2) ER edges turn the faces of G into disjoint cycles in Ĝ0 , and efficiently because (3) ES edges keep Ĝ0 planar and of small diameter. We now state the properties of Ĝ‘ formally. After which, we will extend the above intuition on Ĝ0 to Ĝ‘ , follow it by the formal definition of Ĝ‘ , and proofs for its properties. Theorem 3.1. There exists a connected planar graph Ĝ‘ of diameter O(D), satisfying: 1. Each face-part p(f ) of a node-part f that appears in an annulus of level ‘ maps to a unique path9 p̂(f ) in Ĝ‘ such that the different p̂(f )’s in level ‘ are vertex disjoint. In particular, every vertex v ∈ p(f ) has a copy on p̂(f ). 2. Two paths p̂(f ); p̂(g ) are connected with a unique edge ê in Ĝ‘ for each edge in an annulus of level ‘ in which the node-parts f and g are connected. 3. Each annulus A of level ‘ corresponds to a connected unique subgraph  of Ĝ‘ , s.t. a node-part f is in A iff p̂(f ) is a subgraph of Â. 4. Assuming incisions that define level ‘ annuli are distributively stored (defined next), then Ĝ‘ is constructed in O(1) communication rounds on G. 9

To be concise, we refer to p̂(f ) as a path even when p(f ) is an entire face of G (and then p̂(f ) is in fact a cycle).

17

5. A CONGEST round on Ĝ‘ can be simulated within O(1) CONGEST rounds in G. Definition 3.2 (Level ‘ distributively stored incisions). We say that the set of incision paths which define level ‘ > 0 of T - i.e., paths Pi computed in previous levels in addition to the path P - is distributively stored, if each primal vertex v ∈ G knows its incident edges whose duals appear on the incision paths. In addition, each of s; t knows its incident edge whose dual is an edge added to an endpoint of P (see Definition 2.2, and Remark 3.3 later in this section). Compared to Ĝ0 , our Ĝ‘ aims to simulate minor-aggregation algorithms simultaneously on all level‘ annuli (not only G ∗ ). I.e., we construct one graph Ĝ‘ that captures the structure of all level ‘ annuli together. Thus, to represent node-parts and the edges incident to them, we need to deal with face-parts and (not only) faces of G. This is more complicated than (the already somewhat complicated) Ĝ0 : Not only do faces of G overlap, but now also face-parts of the same face overlap. Therefore, one edge of G participates in potentially four face-parts (see Claim 2.14). The generalization of Ĝ0 to Ĝ‘ follows a similar intuition to Ĝ0 . Essentially, we want Ĝ‘ [ER ] to contain a vertex-disjoint path p̂(f ) if p(f ) is a face-part of G. To create these paths, a vertex v ∈ G has a copy v for each face-part that contains it, and an edge e ∈ G has up to four ER copies in Ĝ‘ (instead of just two in Ĝ0 ) - a duplicate per face-part that contains e (Claim 2.14). More concretely, in Ĝ0 we had a single copy vf for each face f of G that contains v . In Ĝ‘ we have two copies vfL ; vfR , one for each face-part of f that contains v (when the node f in G ∗ is split into two node-parts in level ‘). Consequently, we add more edges to the star (ES edges) of v in order to keep the diameter of Ĝ‘ small while preserving its planarity after adding the new copies of v . Thus, we extend the star from Ĝ0 of v to a depth-two tree of v in Ĝ‘ . We do that by adding the edges of the form (vf ; vfL ) and (vf ; vfR ) to ES in Ĝ‘ (in addition to the edges of the form (v ; vf ) as in Ĝ0 ). Next, similarly to Ĝ0 , there is a set EC of edges that mimics the topology of annuli of level ‘, in the sense that there is an EC edge connecting p̂(f ); p̂(g ) iff there is an edge connecting (f ; g ) in an annulus of level ‘ of T . Having those EC edges and the paths (composed of ER edges) that correspond to node-parts of level-‘ annuli, means that in Ĝ‘ [ER ∪ EC ] we have a disjoint connected component  for every level-‘ annulus A. Definition of Ĝ‘ . We proceed to define Ĝ‘ excluding an adjustment related to the endpoints of P (see Definition 2.2), which is discussed towards the end of the current subsection (Remark 3.3). In the following, we assume that the incisions of level ‘ are distributively stored as in Definition 3.2. We say that an edge e of G maps10 to an incised edge of level ‘ iff its dual participates in P or in some Pi that bounds a level-‘ annuli. Vertices. We start by discussing the vertex set V̂ of Ĝ‘ . Intuitively, we want a vertex vf for each vertex v ∈ G that lies on a face f of G. However, v has no way of detecting which faces does it lie on locally (actually, the whole purpose of Ĝ‘ is to allow us to do that). To deal with that, note, from the local view point of v , each two consecutive incident edges correspond to a face of G that contains v . Hence, what was denoted as vf is now formally denoted by vi , where, vi is associated to the ith pair of consecutive edges incident to v . We denote those edges by ei ; ei+1 (indices indicate edges’ ordering in v ’s embedding and are taken modulo deg(v )). I.e., vi can be thought of intuitively as vf if the face f contains the ith pair of edges incident to v . See for example See Figure 15a, where v1 corresponds to the face containing edges e1 ; e2 . Since the number of pairs of consecutive edges incident to v is exactly the degree of v . Then, v locally creates the copies D(v ) = {v0 ; : : : ; vdeg(v )−1 } in Ĝ‘ . This results in a copy of v in D(v ) for each pair of two consecutive edges incident to v (for each time v appears on a face).11 See Figure 15a. As mentioned 10

We emphasize important sentences in the definition also by color. Note that v might have multiple pairs of consecutive edges that are contained in the same face, and that is why we say for each time v appears on a face. 11

18

earlier, v has two more types of copies, the copy v , and the copies vfL ; vfR (which now we denote by viL ; viR following the above reasoning). Let VS := V (G). The set V̂ is defined to be the union of [ [ VS ; D(v ); and (D(v ) × {L; R}) v ∈VS

v ∈VS

More precisely, the vertices VS and D(v ) (for all v ∈ G) are always present in Ĝ‘ . However, only a subset of D(V )×{L; R} is present in Ĝ‘ . To explain this, we first give an intuition for the set D(v )×{L; R}. Since it is possible that f is split into face-parts as a result of incising the dual node f into node-parts (Definition 2.9, Claim 2.13), in which case for example, each edge in the pair of edges ei ; ei+1 corresponding to f might belong to a different face-part. I.e., if we want to map those face-parts to vertex-disjoint components of Ĝ‘ , then we must allow a scenario where each of ei ; ei+1 is incident to distinct vertices in Ĝ‘ . Therefore, additional copies of v other than vi that correspond to those edges are needed. To allow such a situation (or others related to face-parts of f and this pair of edges), two additional copies of v are created. The copy viL is associated (only) with ei and the copy viR is associated (only) with ei+1 , as opposed to vi that is associated with both. These three vertices allow different scenarios for the ith pair of edges of v . Hence, these D(v ) × {L; R} vertices are the core of the generalization from Ĝ0 to Ĝ‘ , and together with the vertices vi they map each face or face-part p(f ) that v participates in to a unique path or cycle p̂(f ) in Ĝ‘ . Now, we define which vertices of D(v )×{L; R} are present.: If no edge incident to v is dual to an incised edge, then no vertex viR or viL is present. See Figure 15a. If an incident edge ei or ei+1 is incised, then it participates in two face-parts of the face f corresponding to ei ; ei+1 (Claim 2.14). Therefore, since vi is responsible for the pair ei ; ei+1 (for f ), then when ei is incised, we add the copy viL . Hence, ei would be able to have two copies for f , one that is incident to vi , and the other to viL . Following the same reasoning, if ei+1 is incised, then it participates in two face parts of f . Thus, we add the copy viR , so that ei+1 would be able to have two copies for f , one that is incident to vi , and the other to viR . (see Figure 15b and Figure 15c). Intuitively, from v ’s local view point, ei is the left edge in the ordered pair ei ; ei+1 , hence the superscript L in viL . Analogously, ei+1 is the right edge in the ordered pair ei ; ei+1 , hence the superscript R in viR . Edges. Each edge e of G has up to four duplicates in ER , a duplicate for each face-part p(f ) that contains the edge e (Claim 2.14). The purpose of ER is to have different p(f )’s map to unique paths p̂(f ) (see Figure 16). The purpose of ES is to keep the diameter of Ĝ‘ a constant factor larger than that of G, while preserving its planarity. The purpose of EC is to simulate the dual edges in level-‘ annuli. Formally: ES : This set always contains the star edges (v ; vi ) for all v ∈ G and all vi ∈ D(v ). In addition, each of viL and viR (if present) is connected to vi with an edge (vi ; viL ) and (vi ; viR ), respectively. ER : Let e = (u; v ) be the ith edge (ei ) and the jth edge (ej ) in the local embedding of v and u respectively. We examine two cases, namely, if e corresponds to an incised edge of G ∗ and has two duplicates in level ‘ or not. Note, these are the only cases, as an edge of G ∗ is incised at most once (Lemma 2.6). If e does not map to an incised edge, then e is duplicated twice like in the original definition of Ĝ0 by [17]. Intuitively, e is contained in two faces f ; g of G, and we want to create the edge copies (vf ; uf ); (vg ; ug ) to map those faces to disjoint components p̂(f ); p̂(g ). However, as mentioned earlier, u; v do not know (shared IDs of) the faces that contain them. Thus, the definition of those edges needs to depend only on local information. In particular, it depends on the edges’ order in their endpoints’ local embedding. Locally, f is the ith face of v , and is right to the edge ei from v ’s point of view. While f is the j − 1th face for u, and from u’s view point f is left to the edge ej . Hence, the edge (vf ; uf ) is formally (vi ; uj−1 ). This edge is considered to be an edge of p̂(f ) (the path corresponding to f ). 19

u

u u

e2

e2

e1

e3

e2

e3

e1

v

e3

e1

v

v

e4

e4 e4

u6

u6

u5

uL 6

u5 uR 5

v1R

v1 v4

v2 v

(a)

v3

u6

uL 6

u5 uR 5

v2R

v1R

v1

v2L

v4

v

(b)

v2

v1

v2L

v3

v4

v2 v3L

v

v3

(c)

Figure 15: Top row: the primal graph G in blue and the nodes of the dual G ∗ in red. Only the incision path appears in G ∗ . Three cases related to the vertex v are demonstrated, left to right: (a) no incident edge of v is dual to an incision edge, (b) only the edge e2 is dual to an incision edge, and (c) both e2 ; e3 are dual to incision edges. Bottom row: the corresponding graph Ĝ‘ (from v ’s point of view) for each case. Black edges are edges of ER . Blue edges and vertices are edges of ES and vertices of VS . EC edges are omitted. Symmetrically, (vi−1 ; uj ) is the formalization of (vg ; ug ), and participates in p̂(g ). See Figure 15a. for an illustration from the local point of view of v , and Figure 16 for a global illustration. If e does map to an incised edge in level ‘, then it participates in possibly four face-parts (Claim 2.14). Thus, we create four copies of it, one per face-part that contains it. Intuitively, if e is contained in faces f ; g , then it is contained in two face-parts of f , and two face-parts of g . Moreover, it is the first edge of a face-part f 0 of f , the last edge of a face-part f 1 of f , the first edge of a face-part g 1 of g , and finally, the last edge of a face-part g 0 of g . Thus, informally, we would have four copies of e: (vfL ; uf ), (vf ; ufR ), (vg ; ugL ), (vgR ; ug ), which correspond receptively to the aforementioned cases. Following the reasoning above that: vi ; uj−1 correspond to vf ; uf (respectively), and vi−1 ; uj corresponds to R ; v ), (u L vg ; ug (respectively). Then formally we add the following edges to ER : (uj−1 i j−1 ; vi ), each L R corresponding to a distinct face-part of f . In addition, we add the edges (uj ; vi−1 ) (uj ; vi−1 ) each corresponding to a distinct face-part of g . Finally, note that since e is incised then by definition of V̂ , R ; v L ∈ D(v ) × {L; r }, u R ; u L ∈ D(u) × {L; r } that the edge we indeed have the vertex copies vi−1 i j−1 j 20

t = t∗

p01

p1

e0

p00

p2 e2 p0

p11

p02 p12

p10

s = s∗

(a) G (blue), its dual G ∗ (red), and the path P = (p0 ; p1 ; p2 ).

(c) The dual graph G ∗ after the incision along P .

(b) The graph Ĝ0 corresponding to G ∗ (with no incisions). u3

u u2 u1 uL2 uR 1

v2R v

2

v3L v3

v v1 sL1

s3

(d) The graph Ĝ1 representing G ∗ after the incision along P . ER edges are black, ES edges are blue, and EC edges (mimicking G ∗ after incising P ) are red. E.g. EC edges connecting p̂(p00 ); p̂(p10 ); p̂(p20 ) (yellow in next subfigure) correspond to the path P = (p00 ; p10 ; p20 ).

s1 s

s2

(e) The graph Ĝ1 only with ER edges, and names to some vertices. Yellow paths are p̂(p00 ); p̂(p10 ); p̂(p20 ), corresponding to the nodes pi0 from subfigure (b). Similarly, pink paths are p̂(pi1 )s that correspond to pi1 s. The vertex s is incident to an endpoint-case edge e0 whose copies in Ĝ1 are (s1L ; u2 ) and (s3 ; u3 ).

Figure 16 e is associated with. Of course, in addition to the (always present) vertex copies vi−1 ; vi ∈ D(v ), uj−1 ; uj ∈ D(u). For a local example from the view point of v , see Figure 15a where no incident edge is incised and Figure 15b where the edge e2 is incised, and the face f to its right is split to two face-parts. In this example, e is e2 for v and e6 for u, and one face-part of f contains the copy (v2L ; u5 ) of e as the first edge, while the second contains the copy (v2 ; u5R ) of e as the last edge. For a more global illustration (of the entire graph Ĝ‘ ), see Figure 16, where f = p1 and g = p0 . EC : Let e = (u; v ) be the ith edge and the jth edge in the local embedding of v and u respectively. If e = (u; v ) does not map to an incised edge, and its dual is e ∗ = (f ; g ). Then, intuitively we want one edge between the two copies of v (or u), one copy that corresponds to f , and the other to g . That is, an arbitrary one of the edges that were intuitively denoted (vf ; vg ); (uf ; ug ) are added to simulate e ∗ . Formally, one of the edges (uj−1 ; uj ); (vi ; vi−1 ) is added to EC (u and v decide arbitrarily, say 21

the vertex with the smaller ID adds the edge between its copies). This is because if (u; v ) belongs to faces f and g , then both uj and vi−1 are in p̂(g ), while both uj−1 ; vi are in p̂(f ). Thus, it is enough to add one EC edge that connects p̂(g ) and p̂(f ). If e = (u; v ) maps to an incised edge, then it corresponds to two dual edges e0∗ = (f 0 ; g 0 ) and e1∗ = (f 1 ; g 1 ), where f k and g k (for k ∈ {0; 1}) are node-parts of f ; g (respectively). Thus, we want to add the two edges that we intuitively denote (uf 0 ; ug 0 ) and (vf 1 ; vg 1 ). The first would simulate e0∗ , and the second would simulate e1∗ . Formally, we add both edges (uj ; uj−1 ); (vi−1 ; vi ). This is because if (u; v ) belongs to faces f and g of G, then uj−1 ; uj are in p̂(f 0 ); p̂(g 0 ) (respectively) s.t. the node-parts f 0 ; g 0 are incident in the annulus, and vi ; vi−1 are in p̂(f 1 ); p̂(g 1 ) (respectively) s.t. the node-parts f 1 ; g 1 are incident in the annulus. For example, see the EC edge (u1 ; u2 ) of u representing (p00 ; p10 ), and the EC edge v2 ; v3 of v representing (p01 ; p11 ) in Figure 16 (in that case g = p0 , f = p1 ). The correspondence between face-parts f 1 ; g 1 to v and f 0 ; g 0 to u in the definition is w.l.o.g. and merely a matter of notation, in order to draw the distinction that each of u; v handles a different edge of e0∗ ; e1∗ . That is, there is no known shared identifiers for f 1 ; g 1 ; f 0 ; g 0 . This fact is important in order for u; v to construct Ĝ‘ locally. At first glance this may seem not symmetric, but this is not the case and the definition is totally symmetric. Simply because u; v add the (syntactically symmetric) edges (uj ; uj−1 ); (vi−1 ; vi ) obliviously. In more detail, the semantic symmetry is as follows: v is responsible for the face-parts that end and start with its i − 1th and ith edges (respectively), which correspond to face-parts g 1 and f 1 (respectively). Similarly, u is responsible for the face-parts that end and start with its jth and j − 1th edges (respectively), and those correspond to face-parts g 0 and f 0 (respectively). Adjustments related to P ’s endpoints. Recall (Definition 2.2) that to define the incision on P ’s endpoints, we add to P an extra edge e0 incident to p0 . In G, e0 is incident to the vertex s. Analogously for P ’s last endpoint p|P |−1 , an edge e|P |−1 is added. See for example the endpoints p0 ; p2 of P in Figure 16a. Incident endpoint edges are e0 and e2 (respectively) and their node-parts after the incision as demonstrated in Figure 16c. Remark 3.3 (Incision on endpoints of P ). In order for the incision over P to be defined (see Definition 2.2), we need each of P ’s endpoints, to choose an incident non-P edge, called an endpoint-case edge, so that this edge together with the incident edge in P define how to split the endpoint into node-parts. Recall, each of those edges get incident to only one new node-part. We denote the chosen edge for the endpoint p0 by e0 , and define e0 to belong only to the node-part p00 of p0 : Edges between e0 ; (p0 ; p1 ) in p0 ’s embedding get incident to p00 , while edges between (p0 ; p1 ); e0 , except for e0 , get incident to p01 . See Figure 16c. It is important (for Reif’s correctness) that e0 ∈ s ∗ . Such edge e0 always exist as P does not entirely contain edges of the face s ∗ of G ∗ (on which p0 ) lies - this would contradict P being simple. The definition is symmetric for p|P |−1 . In order for Ĝ‘ to represent level-‘ annuli correctly, we make minor adjustments to the vertex and edge copies related to the endpoint-case edges in Ĝ‘ . Note, in the definition of Ĝ‘ we define ER edges that correspond to an edge e by examining two cases, either that e is not incised and participates in two faces, or it is incised and participates in four face-parts. However, for e0 (and e|P |−1 ), it is not incised, and participates in exactly one face and one face-part. Thus, to handle this, we simply combine both cases from the definition of Ĝ‘ . Namely. let f ̸= p0 be the other (dual endpoint) of e0 . Then e0 is treated like any non incised edge of f and is duplicated once for f . What needs to be handled differently is the copy of e0 for p0 . Namely, we need to treat it as if it is the first edge of the node-part p00 of p0 , without having another copy of it for p01 . Analogously, for e|P |−1 , it is treated as any non-incised edge in the face f ̸= p|P |−1 that contains it, but is treated as if it is the last edge of the 22

1 0 node-part p|P |−1 of p|P |−1 , without having another copy of it for p|P |−1 . In fact, in the definition of ER edges above, this terminology of first edge on face-part is used for intuition and then formalized. We still describe the changes we do formally.

p1

p1

e0

p2

p0

p0

s

(a) Left: the (non-endpoint) node p1 (red) and p(p1 ) in G (black). p1 ’s incident edges on P are (p0 ; p1 ); (p1 ; p2 ). Right: the paths of Ĝ‘ corresponding to node parts p10 ; p11 . The orange path is p̂(p10 ), and has a copy of the edges between (p0 ; p1 ); (p1 ; p2 ). The pink path is p̂(p11 ), and has a copy of the edges between (p1 ; p2 ); (p0 ; p1 ). Note, both edges (p0 ; p1 ); (p1 ; p2 ) appear in each of p̂(p10 ) and p̂(p11 ).

(b) Left: the endpoint node p0 (red) and p(p0 ) in G (black). p0 has only one incident edge (p0 ; p1 ) on P . The edge e0 is the added endpoint-case edge. Right: the paths of Ĝ‘ corresponding to node parts p00 ; p01 . The orange path is p̂(p00 ), and has a copy of edges between e0 ; (p0 ; p1 ). The pink path is p̂(p01 ), and has a copy of edges between (p0 ; p1 ); e0 , excluding e0 . Hence, only the edge (p0 ; p1 ) appears in both p̂(p00 ) and p̂(p01 ).

Figure 17: Two cases of a node, its corresponding face in G, and its corresponding face-parts after incision. (a) a non endpoint of P . (b) an endpoint of P . Let v ∈ {s; t}, and e = e0 if v = s. Otherwise, e = e|P |−1 (when v = t). In addition, let e = (u; v ) be the ith edge and the jth edge in the local embedding of v and u (respectively). If e is incised then it is handled just like any other incised edge. Otherwise, when e is not incised we apply the following changes: Vertices. We first define the copy vertices of u; v related to e in Ĝ‘ . For u, there is no change on the L , definition of its copies. I.e., uj−1 ; uj are present and potentially other copies related to them, such as uj−1 R . Because, those are added only if e is incised, and it is not. Similarly for v , we already but not ujL and uj−1 R and v L for the same reasoning have the copies vi , vi−1 and potentially others, but not the copies vi−1 i L mentioned earlier. we make no change besides adding the copy vi (see copies of s in Figure 16, subfigure (d)). This vertex copy is responsible for the first edge of the face-part of the face right to e. I.e., for the 1 copy of e that corresponds to p00 (respectively, p|P |−1 ) if v is s (respectively, t). That is, vi participates in p̂(pk1−b ), viL in p̂(pkb ), and vi−1 in the other face f ̸= pk of G in which e participates, where k = 0; b = 0 iff v = s, and k = |P | − 1; b = 1 in case v = t. Edges. For the set ES of edges, we have no change in its definition. I.e., adding the vertex ujL leads to adding the ES edge (uj ; ujL ). See edges incident to copies of s in Figure 16 (subfigures (c) and (d)). In regard of ER edges, we add the edge (viL ; uj−1 ), instead of (vi ; uj−1 ) when e is not an endpoint-case edge. Meaning (vi ; uj−1 ) is not present. I.e., this means that the copy of e in p̂(p0 ) (respectively, p̂(p|P |−1 )) 1 now goes to p̂(p00 ) (respectively, p̂(p|P |−1 )). Other ER edges related to copies of u; v are added without any changes. Finally, for EC edges, we add an arbitrary edge from (uj−1 ; uj ) and (vi−1 ; viL ), instead of 1 (uj−1 ; uj ) or (vi−1 ; vi ). Which connects p̂(p00 ) (p̂(p|P |−1 )) with a copy of e to the path p̂(f ) where f is the other dual endpoint of e. For simplicity, we always add the edge (uj−1 ; uj ) and the edge (vi−1 ; viL ) is never present. Again, see Figure 16 (for example the EC edge corresponding for e0 , is (u2 ; u3 )). Other EC edges remain without any change. 23

This completes the description of Ĝ‘ .

3.2

Properties of Ĝ‘

We now prove the properties of Ĝ‘ in order to complete the proof of Theorem 3.1. 3.2.1

Planarity and Diameter

Lemma 3.4. The diameter of Ĝ‘ is at most 4D. Proof. This follows from the fact that every edge e = (u; v ) of G turns into a path of length 4 in Ĝ‘ [ER ∪ ES ]. If e is not incised then the path is v − vi − uj − u. Otherwise, if e is incised or is an endpoint-case edge, then the path is v − vi − viL − uj − u or v − vi − viR − uj − u. Adding the edges EC can only make the diameter smaller. Lemma 3.5. Ĝ‘ is planar. Proof. For ‘ = 0, we have that Ĝ0 is planar by [1, 17]. For ‘ > 0, we show that Ĝ‘ is planar by showing how to transform Ĝ0 into Ĝ‘ using four steps, each preserving planarity. Intuitively, for each edge e that maps to an incised edge: (1) we complete the set of EC to match its definition in Ĝ‘ by adding both EC edges that correspond to e (as opposed to only an arbitrarily chosen one in Ĝ0 ), (2) we turn each of the two ER edges corresponding to e into two parallel edges (this creates four copies that participate in four faceparts), (3) we subdivide each such edge into one part that belongs to ER and another part that belongs to ES , and (4) we handle the endpoint-case edges in a similar manner. Formally: The four steps transformation. Let e = (u; v ) ∈ G be the ith and jth edge in the local embedding of v and u, respectively. Recall from Section 3.1 that in Ĝ0 no edge is an incised edge, and there are four vertices related to e: vi−1 ; vi ; uj−1 ; uj . In Ĝ‘ however, if e is an incised edge, then there are the additional R ; v L ; u R ; u L related to e. The transformation from Ĝ to Ĝ is then: vertices vi−1 0 ‘ i j−1 j 1. Adding missing EC edges. In Ĝ0 , one of the edges (vi−1 ; vi ); (uj−1 ; uj ) is in EC . This is in contrast to Ĝ‘ , where for an incised edge e ∈ G both edges (vi−1 ; vi ); (uj−1 ; uj ) are in EC (see Figure 18). This step, produces a graph Ĝ01 , whose set EC of edges is identical to the the set EC of Ĝ‘ , that is, we add the missing EC edges to Ĝ‘ . (see definition of Ĝ‘ in Section 3.1).

t = t∗ p1

e0

p2 e2 p0

s = s∗

Figure 18: Left: G (blue), its dual G ∗ (red). The incision path is P = (p0 ; p1 ; p2 ), and its endpoint-case edges are e0 ; e2 . Middle: the graph Ĝ0 . ER edges are black, ES edges are blue, and EC edges are red. Right: the graph Ĝ01 resulting from Ĝ0 after step (1) where two missing EC edges (bold red) are added.

24

Adding those edges does not violate planarity (follows from [1, 17]). In particular, even if all edges (v1 ; v2 ); : : : ; (vdeg(v ) ; v1 ) were added, then they create a cycle on the leaves of v ’s star. One can verify easily that replacing the star of a vertex with a star on a cycle for all vertices v preserves planarity. Hence, adding a subset of those edges also does not. 2. Duplicating ER edges. For every edge e of G there are two ER copies (vi−1 ; uj ) and (vi ; uj−1 ) in Ĝ01 (the resulting graph from the previous step). However, when e is incised, then in Ĝ‘ it has four ER copies. To fix this, we first duplicate each of the edges (vi−1 ; uj ); (vi ; uj−1 ). This results in two parallel edges (vi−1 ; uj ), and another two parallel edges (vi ; uj−1 ). Obviously the resulting graph, denoted Ĝ02 is planar. See Figure 19 (left). u2

u1

u2

u1 uL 2 uR 1

v2R

v2

v3

v2

v3L

v3 sL 1

s1

s1

s1

Figure 19: Left: the graph Ĝ02 resulting from Ĝ01 after duplicating ER edges that map to incised edges in step (2). Middle: the graph Ĝ03 resulting from Ĝ02 after subdividing these parallel edges. In both sides, edges that existed in Ĝ0i−1 are faded, while new edges in Ĝ0i (for i = 2; 3) are not. Right: the graph Ĝ04 = Ĝ‘ resulting from step (4) after subdividing one ER copy of each endpoint-case edge. Edges that existed in Ĝ03 are faded, while new edges are not. 3. Subdividing ER edges into ER and ES edges. We proceed with the changes on ER edges of Ĝ02 so they match the set of ER edges of Ĝ‘ . First, recall that for an incised edge e, we have the following four ER edges R ; u ), (v L L R R L R L in Ĝ‘ : (vi−1 j i−1 ; uj ), (vi ; uj−1 ), (vi ; uj−1 ). We therefore need to add the vertices vi−1 ; vi ; uj−1 ; uj and connect them properly with the existing vertices vi−1 ; vi ; uj−1 ; uj in Ĝ02 . This also includes ES edges. The missing ES edges in this case connect a vertex a ∈ {vi−1 ; vi ; uj ; uj−1 } with its copies that we add R ) is missing). See Figure 19 (middle) for an illustration. from a × {L; R} (e.g. the ES edge (vi−1 ; vi−1 These missing vertices, and missing ER and ES edges are handled with the following change to Ĝ02 : Subdivide each one of the parallel edges (from the previous step) (vi−1 ; uj ), and subdivide each one of the parallel edges (vi ; uj−1 ). This results in a graph Ĝ03 . When the first edge (vi−1 ; uj ) is subdivided R . Hence, in Ĝ 3 , we have the edges into two edges (vi−1 ; w ); (w ; uj ), we set the vertex w to be vi−1 0 R ); (v R ; u ). The edge (v R ) is an E edge and (v R ; u ) is an E edge. In a similar man(vi−1 ; vi−1 ; v j i−1 j R S i−1 i−1 i−1 ner, when subdividing the second edge (vi−1 ; uj ), we set w to be ujL (resulting with the ER edge (vi−1 ; ujL ) and the ES edge (ujL ; uj )). We apply the same logic for the other two subdivided parallel edges (uj−1 ; vi ), R ) ∈ E , (u R ; u resulting with the edges (uj−1 ; viL ) ∈ ER , (viL ; vi ) ∈ ES and (vi ; uj−1 R j−1 j−1 ) ∈ ES . For an 3 incised edge e ∈ G, the vertex and edge copies related to it in Ĝ0 now match the definition (Section 3.1) of Ĝ‘ . 4. Endpoint-case edge e. An endpoint-case edge e has two ER copies in Ĝ0 and in Ĝ03 : One ER copy participates in the cycle p̂(pk ) corresponding to pk ∈ {p0 ; p|P |−1 } is an endpoint of the path P , and the other 25

ER copy in the cycle corresponding to e’s other endpoint. More concretely, let v be s if pk = p0 or t if pk = p|P |−1 . Then, in Ĝ03 we subdivide the copy (uj−1 ; vi ) of e into the two edges: (vi ; viL ) ∈ ES and (uj−1 ; viL ) ∈ ER . Obviously, the graph remains planar after this. Finally, we do the following minor change: remove the EC edge (vi ; vi−1 ) if exists and add the EC edge (uj−1 ; uj ). This matches the definition of Ĝ‘ for the an endpoint-case edge (Section 3.1) and does not violate planarity (as we established in the first step where we added the edges of type (uj−1 ; uj )). For an illustration see Figure 19 (right). The above transformation preserves planarity, takes care of all edges (incised/not-incised/endpointcase), and matches the definition of Ĝ‘ as defined in Section 3.1. Hence, Ĝ04 = Ĝ‘ and so Ĝ‘ is planar. 3.2.2

Vertex-disjoint Face-parts

We prove the first item of Theorem 3.1 regarding Ĝ‘ . Lemma 3.6. For each level-‘ node-part f , p(f ) maps to a unique (vertex-disjoint) connected component p̂(f ) of Ĝ‘ [ER ]. Moreover, a consecutive subset of f ’s edges maps to a unique subpath of p̂(f ). In Ĝ0 each face f of G maps to a cycle p̂(f ) of ER edges [17]. The cycle p̂(f ) corresponds to an Euler tour on f . Therefore, p̂(f ) is connected. Ĝ‘ can be seen as a collection of cycles and paths. The cycles (paths) correspond to Euler tours on faces (face-parts). v

u e1

z

w

e2 x

Figure 20: Left: A node-part f (red square) of h ∈ G ∗ and its incident edges in solid red (edges between e1 and e2 , clockwise). Dashed red edges are h’s other edges. The corresponding (primal) face-part p(f ) is solid blue. Right: the path p̂(f ) in Ĝ‘ corresponding to the Euler tour v ; u; w ; z; w ; x on p(f ). The intuition behind the proof is as follows. By Definition 2.9, a node-part f , is defined by all (dual) edges between two edges e1 ; e2 incident to some node h of G ∗ (f is a part of h). We show that the Euler tour on p(f ) corresponds to p̂(f ), by starting at the (primal) edge e1 and traversing the face-part p(f ). If p(f ) is a simple path or a cycle then each of its edges is traversed once. Otherwise, we may traverse the same edge twice. This happens if the edge is a self loop in the dual (see e.g., the edge (w ; z) in Figure 20). Using duality, we show that for each two consecutive edges in the local embedding of f , there is a shared primal vertex to the edges’ counterparts in G. From here it follows that p(f ) is connected. Then, by relating the aforementioned vertices to their copies in Ĝ‘ and relating the f edges to their copies in Ĝ‘ , we get that p̂(f ) is connected. To prove that for g ̸= f , p̂(f ) is vertex-disjoint from p̂(g ), we show that the vertex and edge copies that form each of them are disjoint. Proof of Lemma 3.6. First we eliminate the case of p(f ) being an entire face of G. Claim 3.7. If p(f ) is an entire face of G, then p̂(f ) is a cycle and a maximal connected component in Ĝ‘ [ER ].

26

The claim follows from [1, 17], since in that case our definition of Ĝ‘ matches the definition of Ĝ0 from [1, 17]. This is because our definition differs from Ĝ0 only for edges that are (incident to) nodes on an incision path, and if f is not such a node, then p(f ) is an entire face of G. Thus, from now on, it suffices to discuss face-parts p(f ) (not an entire face of G). In addition, we split the proof into two parts, one that discusses connectivity, and the other discusses disjointness of p̂(f ). Connectivity. In here, we formally describe the tour on p(f ) that corresponds to p̂(f ) and relate it to Ĝ‘ by pointing out the copies of p(f ) vertices and edges that are vertices of p̂(f ) in Ĝ‘ proving: Lemma 3.8. For each level-‘ node-part f , p(f ) maps to a connected component p̂(f ) of Ĝ‘ [ER ]. In particular, a consecutive subset of f ’s edges maps to a unique subpath of p̂(f ). To prove the lemma, we first provide a claim and a definition that will be important to its proof. Claim 3.9. Let f be a dual node and e; e ′ be two incident consecutive edges in the local ordering of f . Then, e; e ′ have a shared endpoint u in p(f ) such that e ′ precedes e in u’s local ordering of its incident edges. This claim follows from basic arguments on duality [25] and can be seen as special case of Claim 2.13. We next define the first and last vertices of p(f ). These are the endpoints of p(f ) when p(f ) is a path. But p(f ) can be a tree (e.g. Figure 20), so we have a more precise definition: Definition 3.10 (first/last vertex of p(f )). Let f be a node-part of h ∈ G ∗ , defined by edges e1 ; e2 . Then, the shared primal endpoint of e1 and its predecessor edge in h is the first vertex of p(f ), and the shared endpoint of e2 and its successor edge in h is the last vertex of p(f ). We next describe the tour on p(f ) that corresponds to p̂(f ). Which combined with Claim 3.7 constitutes the proof of Lemma 3.8. Proof of Lemma 3.8. When f is a not split into parts, then p(f ) is an entire face of G and the claim holds by Claim 3.7. Now, we prove the lemma for face-parts p(f ), showing: Traversing all edges of p(f ) one at a time can be mapped to p̂(f ), s.t., each traversal on an edge of p(f ) corresponds to a copy of the same edge in p̂(f ), and two copies of consecutive edges share an endpoint (are connected). See Figure 21. First edge (the edge e1 ). Consider the first edge e1 that is incident to f . In G, e1 has two primal endpoints u; v . Assume that v is the first vertex of p(f ). Since u is not the first vertex of p(f ), and by Claim 3.9, we get that u is an endpoint in G of the successor edge of e1 in the local ordering of the node f . Denote that edge in G by (u; w ). By the same claim, (u; w ) is the predecessor of e1 in u’s local embedding. Thus, by definition of Ĝ‘ (Section 3.1) u has one vertex copy that is incident to (a copy of) e1 and to (u; w ) in Ĝ‘ . This establishes the first two edges in the tour on p(f ) which correspond to the first two edges in p̂(f ): the edges (v ; u) and (u; w ) in p(f ). Next, we specify the corresponding edges of p̂(f ). Let e1 be the i’th and j’th edge of v and u (resp.). Then, in Ĝ‘ , the copy uj of u is incident to a copy of e1 whose other endpoint is the copy viL of v . I.e., the edge (uj ; viL ) ∈ ER in p̂(f ) corresponds to traversing e1 in p(f ) from v to u. In addition, if w is not the last vertex in p(f ), then by definition of Ĝ‘ there is a copy wk of w that is incident to uj with an ER copy of the edge (w ; u). I.e., (uj ; wk ) ∈ ER is the copy for traversing (u; w ) ∈ p(f ) in p̂(f ). Edges (strictly) in between e1 and e2 . We continue in a similar manner as above until we reach the last vertex of p(f ), each time traversing the next edge on p(f ), where next is defined by the local embedding of f . More formally: (a) The current edge to be traversed is (w ; z) such that neither of w ; z is the last vertex of p(f ). In addition, in the previous step we traversed some edge e := (a; w ) in p(f ) and arrived to w (w.l.o.g.) where e is the predecessor of (w ; z) in f ’s local embedding. 27

u

u u1 uL 2

w p1

g

p2

p01 g

p0

p00

p11

v z s

w w2

p10

v2

v

p02 p12

v3L

s1

z4R

z

s

f f

(a) G (blue), its dual G ∗ (red), and (b) The dual graph G ∗ after the in- (c) The graph Ĝ1 [ER ] correspondthe path P = (p0 ; p1 ; p2 ). cision along P . ing to G ∗ after incising P .

Figure 21: The node-part p10 in image (b) is defined by edges e1 = (p0 ; p1 ); e2 = (p1 ; p2 ) that are dual to the primal edges (v ; u) and (w ; z), respectively in image (a). The face-part p(p10 ) in G is the path (v ; u; w ; z) whose first and last vertices are v and z. The corresponding path p̂(p10 ) is the path (v3L ; u1 ; w2 ; z4R ) in Ĝ1 (the yellow path in image (c)). The node-part p01 in image (b) is defined by the edges e1 = (p1 ; p0 ); e2 = (p0 ; g ) that are dual to the primal edges (u; v ) and (s; u) respectively in image (a). p01 is a node part of the endpoint node p0 ∈ P , and the edge (dual to) (s; u) is an endpoint edge. This is the reason that (p0 ; g ) is not incident to p01 , and instead p01 ’s last incident edge is e2′ = (p0 ; f ) that is dual to (v ; s). The corresponding face-part p(p01 ) is the path (u; v ; s) whose first and last vertices are u and s. In Ĝ1 the path p̂(p10 ) is (u2L ; v2 ; s1 ) (the pink path in image (c)). (b) Assume the edge (w ; z) is the k’th edge of w and the t’th edge of z. Since (w ; z) is the successor of (a; w ) in the embedding of f , then vertex wk is incident to a copy zt−1 of z with an ER edge (definition of Ĝ‘ , Section 3.1). This edge corresponds to the edge being traversed. Moreover, we arrived to w by traversing (a; w ). This is the k + 1’th edge of w (by Claim 3.9 because it precedes (z; w ) in f ’s embedding) and x’th edge of a. That is, wk is incident to the edge (ax ; wk ) ∈ p̂(f ). In other words, the two consecutive edges in p(f ) corresponding to (a; w ) and (w ; z) correspond to connected edges in p̂(f ) (edges that share an endpoint, wk ). (c) Let the next edge in f ’s embedding be (z; y ) ̸= e2 (neither of z; y is the last vertex of p(f )). The tour proceeds in a similar manner starting from (a) after setting a := w , w := z and z := y . Last edge (the edge e2 ). Eventually, the edge e2 is traversed. The case of e2 is symmetric to e1 . I.e., e2 has two endpoints u ′ ; v ′ , where v ′ is the last vertex of p(f ′ ). By definition of Ĝ‘ (Section 3.1) vi′R ′ is the last ′ , and u ′ is connected to w ′ vertex of the path p̂(f ). In addition, vi′R is connected with an E edge to u ′ R j′ j′ k′ with an ER edge, where the dual of (u ′ ; w ′ ) proceeds e2 in the embedding of f . The endpoint-case edge. If e2 is an endpoint-case edge, then let e2′ be the predecessor of e2 in the local embedding of f . Let the edge of G corresponding to e2′ be (u ′ ; v ′ ). Then, w.l.o.g. v ′ is the last vertex of p(f ), and u ′ is incident to a vertex w ′ in p(f ) s.t. the edge (u ′ ; w ′ ) is dual to the edge that precedes e2′ in the embedding of f . In this case, the last endpoint of the path p̂(f ) is simply vi′′ , which is connected to uj′′ with an ER edge, and uj′′ in turn is connected to wk′ ′ with an ER edge. See Figure 21.

28

Uniqueness. Here we show the following lemma, which combined with Lemma 3.8 (on connectivity of p̂(f )) completes the proof of Lemma 3.6 on connectivity and disjointness of p̂(f )s. Lemma 3.11. p̂(f ) is vertex-disjoint from p̂(g ) for any two level-‘ node-parts g ̸= f . For that, assume the following claim holds (we provide a proof after proving the above lemma). Claim 3.12. Each pair of (ordered) consecutive edges incident to v ∈ G is unique and belongs only to one face or face-part of an annulus of level ‘. Proof of Lemma 3.11. Note that internal vertices (non-endpoints) of p̂(f ) are of the form vi ∈ D(v ) for a vertex v ∈ p(f ). Moreover, by definition of Ĝ‘ (Section 3.1), vi is incident to two ER edges only, which belong to p̂(f ). In fact, vi is defined to only be incident to those edges as they are copies of the i’th pair of consecutive edges incident to v (for each such pair there is a copy of v in D(v ) by definition of Ĝ‘ ). Thus, by definition of Ĝ‘ , vi cannot be shared by p̂(f ) and some p̂(g ) for g ̸= f with an ER edge (this would contradict the above Claim 3.12). If p(f ) has no incised edge (p(f ) is an entire face of G), then p̂(f ) is a cycle formed of D(v )-type vertices. Then, the aforementioned reasoning is enough to derive the claim on uniqueness in this case. We proceed to the case of endpoints of p̂(f ) when it is a path (p(f ) contains incised edges and is a face-part of G). It remains to show that no endpoint of p̂(f ) is shared by any p̂(g ) where g ̸= f . For the special case where vi ∈ D(v ) is an endpoint of p̂(f ), when f is a node-part that is an endpoint of P (see Definition 2.2, Remark 3.3), we get that the reasoning given earlier still holds. This is because it can be thought of as if vi had two incident edge copies in Ĝ‘ and one of them (the one corresponding to the endpoint-case edge) got deleted (see Section 3.1 for the definition of Ĝ‘ in that case). In the general case where endpoints of p̂(f ) are of the form viL or viR , then by definition of Ĝ‘ (Section 3.1), such a vertex has only one ER edge incident to it. The primal corresponding edge e = (u; v ) to that edge has four copies in Ĝ‘ , each of them has its unique endpoints. In particular, each such ER edge copy is of the form (viL ; uj ). That is a vertex of D(u) × {L; R} and a vertex of D(v ) (or symmetrically, a vertex of D(u) × {L; R} and a vertex of D(v )). Thus, the first and last two vertices of p̂(f ) cannot be shared to any p̂(g ) where g ̸= f , because each vertex of D(u) (as proved earlier) belongs only to one p̂(f ), and its incident D(v ) × {L; R} copy is not incident to any other vertex with an ER edge, thus, it can only belong to the same p̂(f ). Proof of Claim 3.12. An (ordered) pair of of consecutive edges incident to v is contained in one face h of G, and by Claim 3.9 corresponds to a pair of consecutive edges incident to the node h in G ∗ . Let e; e ′ be such a pair of edges, in that order in h’s local ordering in G ∗ . The pair e; e ′ of edges can participate together only in one node-part of h (or only the entire node h itself if it is not split to parts), because a node-part is a consecutive set of edges of f (Definition 2.9), and by definition two node parts can share only their first and last edges with another node-part of the same node. I.e., they cannot share a pair of (ordered) edges. See Claim 2.10. Note, if e; e ′ are the only edges incident to v , then they can also participate in a face-part of the other face g of G that contains them, but in that case their clockwise ordering in (the node) g ∈ G ∗ is e ′ ; e, which is a different (ordered) pair of edges from e; e ′ . Note, Lemma 3.11 together with Lemma 3.8 concludes the proof of Lemma 3.6 that p̂(f ); p̂(g ) are connected and vertex disjoint for nodes f ̸= g of level ‘. 3.2.3

Correspondence to Annuli

We prove the second and third items of Theorem 3.1 regarding Ĝ‘ .

29

Lemma 3.13. There is an injection from edges in level ‘ of T to the set of EC edges in Ĝ‘ . For each edge (f ; g ) of level ‘, there is a unique edge ê ∈ EC in Ĝ‘ that connects p̂(f ) and p̂(g ), and there is no EC edge that connects p̂(f ) and p̂(g ) if (f ; g ) is not an edge of level ‘. Proof. We have established in Lemma 3.6 that each face-part f of G is represented by a path p̂(f ) in Ĝ‘ , such that each vertex v that is contained in p(f ) has a copy in Ĝ‘ in p̂(f ). A level-‘ edge has at least one EC edge. Let e ∗ be a level-‘ edge that connects node-parts f ; g , we show that there is an EC edge that maps to it by examining two cases. Note, the following covers are all cases, because an edge is incised at most once, by Lemma 2.6. e ∗ is not incised. In this case, e has only one dual edge in level ‘, connecting node-parts f ; g . Let e = (u; v ) in G be the dual of e ∗ and the i’th edge in v ’s local embedding, such that the face of G that contains p(g ) (resp. p(f )) is left (resp. right) to e. Hence, the face-part p(g ) (resp. p(f )) corresponds to the i − 1’th (i’th) pair of consecutive edges incident to v . By definition of Ĝ‘ (Section 3.1), since e ∗ is not incised, then e has exactly two ER copies in Ĝ‘ . One is incident to vi−1 and the other to vi . In addition, vi−1 and vi correspond to the i − 1’th and i’th pair of consecutive edges incident to v respectively. I.e., vi−1 and vi correspond to the face-parts p(g ) and p(f ) respectively, and vi−1 ; vi belong to p̂(f ); p̂(g ) respectively in Ĝ‘ . Moreover, by definition of Ĝ‘ , w.l.o.g. there is an edge (vi−1 ; vi ) ∈ EC that represents the dual edge (f ; g ). Otherwise, if (vi−1 ; vi ) does not exist, then the edge (uj−1 ; uj ) exists where e is the j’th edge in u’s local embedding (by definition of Ĝ‘ one of those two edges exist when e ∗ is not incised). In this case, the proof is symmetric (just replace u with v , i with j, and left with right). If e ∗ is an endpoint-case edge of p0 (Definition 2.2, Remark 3.3) then s is an endpoint of e and the same reasoning of a non-incised edge applies, with the difference that the edge (uj−1 ; uj ) always exists and the edge (vi−1 ; vi ) never exists iff v = s. To verify, see the definition of Ĝ‘ in this case (Section 3.1). The other case of e ∗ being the endpoint-edge of p|P |−1 is symmetric by replacing s with t. e ∗ is incised. In this case, e has two dual edges in level ‘. By Claim 2.14, in level ‘ there are two pairs of node-parts that are connected by a dual of e. We consider one such pair f ; g ∈ A of them (the proof for the other pair is identical). Assume w.l.o.g. that e is the last edge in the sequence of edges that defines the node-part f , and e is the first edge in the sequence of edges that defines the node-part g . I.e., in G we say that e is the last edge on p(f ) and is the first edge on p(g ). In addition, assume w.l.o.g that v is the last vertex on p(f ) and the first vertex of p(g ) (intuitively, an endpoint of e that is also an endpoint of p(f ) and p(g ), formally, as in Definition 3.10). Then, e’s other endpoint u is also a vertex in both p(f ) and p(g ). Assuming the edge e is the j’th edge of u, then uj−1 ; uj are copies of u on p̂(f ) and p̂(g ) respectively. Assume w.lo.g. that the face of G containing p(g ) (respectively p(f )) is the face that corresponds to the j − 1’th (respectively j’th) pair of consecutive incident edges to u. Then, from the definition of Ĝ‘ (Section 3.1) the edge (uj−1 ; uj ) ∈ EC represents the dual edge (f ; g ) ∈ A. Note, in this case the edge (vi−1 ; vi ) does not map to e, since the copies vi−1 ; vi are not in p̂(f ); p̂(g ) but in p̂(f ′ ); p̂(g ′ ) where f ′ ; g ′ are node-parts that overlap with f ; g with the edge e ∗ . I.e., the edge (vi−1 ; vi ) corresponds to the edge (g ′ ; f ′ ) which is the second duplicate of e ∗ in level-‘. In fact, the copies of v that participate in p̂(f ); p̂(g ) R ; v L (resp.) and by definition of Ĝ there is no edge of any type that connects them. are vi−1 ‘ i A level-‘ edge has at most one EC edge. Note that by the definition of Ĝ‘ , for an edge e ∈ G whose dual in G ∗ is not incised, there is only one EC edge in Ĝ‘ . Otherwise, by definition of Ĝ‘ there are exactly two EC edges in Ĝ‘ added for e, and e ∗ ∈ G ∗ is incised (exactly once, by Lemma 2.6); Thus, e has at most two duals in level ‘. One of these edges might be incident to a node-part h that is not contained in any annulus Corollary 2.11. Thus, for each edge of level ‘ there is exactly one EC edge in Ĝ‘ , and each EC edge represents exactly one edge (whether it is in an annulus or not). I.e., there is an injection from edges of level ‘ of T to the set of EC edges. 30

Lemma 3.14. Each annulus A of level ‘ corresponds to a unique connected component  of Ĝ‘ [ER ∪ EC ], s.t. node-part f ∈ A iff p̂(f ) is a subgraph of Â. Moreover e = (f ; g ) ∈ A iff ê ∈  connects p̂(f ); p̂(g ). Proof. By Lemma 3.13, any two node-parts f ; g are adjacent in an annulus of level ‘ iff there is an EC edge connecting their corresponding paths p̂(f ), p̂(g ) (which exist and are disjoint for f ̸= g by Lemma 3.6). Consider any two node-parts f ; g in an annulus A. Since an annulus is a connected graph, then f ; g are connected by a path A(f ; g ) = (f ; h1 ; h2 ; : : : ; hk ; g ) in A. In Ĝ‘ [ER ∪ EC ], each of p̂(f ), p̂(hi ), and p̂(g ) is a path by Lemma 3.6. In addition, by Lemma 3.13 there exists an EC edge connecting the corresponding paths of each two consecutive nodes of A(f ; g ). Thus, p̂(f ) and p̂(g ) belong to the same connected component in Ĝ‘ [ER ∪ EC ] as they are connected via the subgraph which is the union of the following: the path p̂(f ), the EC edge connecting p̂(f ) and p̂(h1 ), the path p̂(h1 ), the EC edge connecting p̂(h1 ) and p̂(h2 ), the path p̂(h2 ) and so on until the EC edge connecting p̂(hk ) and p̂(g ), and lastly the path p̂(g ). Denote the subgraph we just defined by Â(f ; g ). Then, the union of all Â(f ; g ) for node-parts f ; g ∈ A is defined to be Â. Now we prove that  is in fact a (maximal) connected component of Ĝ‘ [ER ∪EC ], and in particular that it does not contain any (vertex in) p̂(h) for h ∈ = A. Consider any node-part f ∈ A. f is not connected to any node-part in an annulus B ̸= A, since by definition A and B are different annuli, which by Claim 2.12 are disjoint. Thus, by Lemma 3.13 f has no EC edge that connects p̂(f ) to a p̂(g ) for g ∈ B. This with the fact that p̂(f ) and p̂(g ) are vertex disjoint means that p̂(f ) and p̂(g ) are disconnected in Ĝ‘ [ER ∪ EC ]. Thus, no vertex of p̂(g ) for g ∈ = A exists in Â. 3.2.4

Simulation of Ĝ‘

We prove the fourth and fifth items of Theorem 3.1 regarding Ĝ‘ , concluding the proof of the theorem. Lemma 3.15. For any level ‘ of T , if incisions to the level are distributively stored (as in Definition 3.2), then Ĝ‘ can be constructed in O(1) rounds. After which, each of its vertices has a unique Õ(1)-bit ID, and every vertex in G knows the information of all its copies in Ĝ‘ and their adjacent edges. Proof. A vertex v ∈ G needs to know for each incident edge e = (u; v ) the relative order of e in u’s local embedding, which can be exchanged in one round. The information related to incisions on edges incident to v is given by assumption. Finally, IDs of vertices in Ĝ‘ can be assigned locally: Each vertex v assigns its (at most) 3 deg(v ) + 1 copies an ID consisting of v ’s ID concatenated with a unique number from the range [0; 3 deg(v )]. Lemma 3.16. Any CONGEST round on Ĝ‘ can be simulated within four rounds in G. Proof. Note that the only edges that require simulation are edges of ER , as other types of edges are edges between copies of the same vertex v ∈ G, meaning that v simulates them locally. The claim follows because any edge in G has at most four ER copies in Ĝ‘ .

3.3

Distributed Knowledge

In this subsection we show how to use Theorem 3.1 (the graph Ĝ‘ ) in order to prove the following lemma. Lemma 3.17. Assuming the incisions of level ‘ are distributively stored as in Definition 3.2, the following can be computed in Õ(D) rounds. Each vertex v ∈ G, for all level-‘ node-parts f where v ∈ p(f ), knows: 1. A unique Õ(1)-bit ID of f and a unique leader vertex u ∈ p(f ). 2. A unique Õ(1)-bit ID of the level-‘ annulus A containing f , and the ID of A’s level-‘ − 1 parent annulus. 31

3. All of v ’s incident edges that are in p(f ). 4. The IDs of all node-parts h from lower levels whose p(h) contains p(f ) (see Claim 2.15). The proof is inductive, and shows how, given the information as stated in the lemma, we can extend it to the next level. To do so we rely on properties of Ĝ‘ (e.g. to identify face-parts, we run a connectivity algorithm on a subgraph of it). Then, local computations regarding knowledge of vertices to the previous level are performed, deriving the correspondence to the current level. Before that, we first briefly define a couple of distributed primitives that we will use in the proof and in Section 3.4. Low-congestion shortcuts and part-wise aggregation. The notion of low-congestion shortcuts was introduced by Ghaffari and Haeupler [14] first for planar graphs, and then extended for other graph families [15, 19] as a way to perform certain type of computation (known as aggregation) on multiple disjoint subgraphs of G simultaneously, within a round complexity proportional to D rather than the (possibly) large diameter of the input subgraphs. Concretely, consider a partition {S1 ; : : : ; SN } of V where every G[Si ] is connected: Definition 3.18 (Low-congestion shortcuts). An ¸-shortcut of G, is a set of subgraphs {H1 ; : : : ; HN } of G such that the diameter of each G[Si ] ∪ Hi is at most O(¸) and each edge of G participates in at most O(¸) subgraphs Hi . Definition 3.19 (Aggregate operators). Given a set L of b-bit strings {x1 ; : : : ; xm } and an aggregation operator ⊕ (e.g. AND /OR /SUM etc.), their aggregate i xi is defined as the result of repeatedly replacing any two strings xi ; xj with the (b-bit) string xi ⊕ xj , until a single string remains. Definition 3.20 (Part-wise aggregation). Assume each v L ∈ Si has an Õ(1)-bit string xv . The PA problem asks that each vertex of Si knows the aggregate function v ∈Si xv . The following lemma captures the relation between the PA problem and shortcuts. Lemma 3.21 (Part-wise aggregation via low-congestion shortcuts [14, 15, 19]). If G admits an ¸-shortcut that can be constructed in r rounds, then the PA problem can be solved on G in Õ(r + ¸) rounds. Since a planar graph G of hop-diameter D admits low-congestion shortcuts with ¸ = Õ(D) that can be constructed in Õ(D) rounds [14, 15, 19], we get: Corollary 3.22. The PA problem can be solved on a planar graph G of hop-diameter D in Õ(D) rounds. From the properties of Ĝ‘ (Lemma 3.16 and Lemma 3.4), in addition to Corollary 3.22, we get the following: Corollary 3.23. For any level ‘ of T , if the incisions are distributively stored as in Definition 3.2, then the PA problem can be solved on Ĝ‘ in Õ(D) rounds. Now, we are ready to prove Lemma 3.17. Proof of Lemma 3.17. Intuitively, we use Lemma 3.6 and Lemma 3.14 that relate level-‘ face-parts and annuli to Ĝ‘ , combined with the fact that the PA problem on Ĝ‘ can be solved in Õ(D) rounds (Corollary 3.23). In particular, by Lemma 3.6, each face-part p(f ) of a level-‘ node-part f corresponds to a connected component p̂(f ) in Ĝ‘ [ER ]. Thus, identifying p(f )s boils down to identifying the connected components of Ĝ‘ [ER ]. This can be done using any connectivity algorithm that terminates within Õ(1) PAs [14,17]. Similarly, using Lemma 3.14 applied to Ĝ‘ [ER ∪ EC ] we can identify the annuli of level ‘. Finally, learning the 32

correspondences between face-parts of different levels and between face-parts and annuli, is done locally by examining different cases related to the structure of Ĝ‘ and Ĝ‘−1 . In the case of ‘ = 0, the only annulus in the level is the entire graph G ∗ . In this case, it was shown in earlier work [17] how to compute the required information using Ĝ. For a general level ‘ > 0 we prove by induction, assuming that the lemma holds for level ‘ − 1 and that the incisions of level ‘ are distributively stored. First, we construct Ĝ‘ in O(1) rounds, where each vertex of G knows all the information of its copies in Ĝ‘ and their IDs (Lemma 3.15). We work in two phases, the first phase is a global phase that identifies the level-‘ annuli, and p(f )s of level-‘ node-parts f . The second phase is a local phase that computes the following correspondences: (1) face-parts of level ‘ and annuli of level ‘, (2) face-parts of level ‘ and face-parts of level ‘ − 1 (see Claim 2.15), and (3) annuli of level ‘ and annuli of level ‘ − 1. Global phase. We run a classic connectivity algorithm [14, 17] on Ĝ‘ that works in Õ(1) instances of the PA problem. By Corollary 3.23, this translates to Õ(D) rounds on G. The input to the connectivity algorithm is Ĝ‘ [ER ∪ EC ], i.e., Ĝ‘ after removing the VS vertices and ES edges (they are still used for communication). The identified connected components correspond to the annuli of level ‘ (Lemma 3.14). We mention that this connectivity algorithm assigns each component it identifies an ID, which is the maximal ID of a vertex in the component. We use these IDs as the IDs of the level-‘ annuli. They are unique since IDs of vertices of Ĝ‘ are unique as shown in Lemma 3.15. Similarly, in Õ(D) rounds we identify components of Ĝ‘ [ER ]. I.e., Ĝ‘ after removing VS vertices and ES ∪ EC edges. Connected components of this graph correspond to p(f ) for level-‘ node-parts f (Lemma 3.6). Since the ID of a path p̂(f ) for a node-part f is an ID of a vertex that lies on it (and this vertex ID is known to all other vertices of p̂(f )) then we consider this vertex as the leader of p̂(f ). Local phase. In this phase, a vertex v ∈ G aims to learn the following correspondences: 1. Between incident edges of v and face-parts p(f ) where v ∈ p(f ) and f is a level-‘ node-part. In addition, between each such p(f ) and the specific level-‘ annulus that contains f . 2. Between face-parts p(f ) of level ‘ − 1 where v ∈ p(f ) and the face-parts p(h) of level ‘ where v ∈ p(h), and h is a part of f (see Claim 2.15). 3. Between annuli B of level ‘ − 1 for which there exists a node-part f ∈ B where v ∈ p(f ) and child annuli A of B for which there exists a node-part f ′ ∈ A s.t. v ∈ p(f ′ ). 1. Face-parts p(f ) and annuli of level ‘. A connected component in Ĝ of each vertex and edge of p̂(f ) was identified in both calls to the connectivity algorithm in phase one. Thus, vertices of Ĝ‘ know the ID of their annulus (from the first call) and the ID of p̂(f ) (from the second call). Note, a vertex v ∈ G knows the information about all copies of its vertices and edges in Ĝ‘ (Lemma 3.15). Thus, for each incident edge e, v knows to which annulus and which face-parts of level ‘ does e belong. 2. Face-parts of level ‘ and face-parts of level ‘ − 1. Recall, every face-part p(f ) in level-‘ annuli is a subgraph of a unique level ‘ − 1 face-part (see Claim 2.15). Consider two node-parts g ; h in levels ‘ − 1 and ‘ (respectively) of the same node f ∈ G ∗ . Let g (respectively h) be defined by the sequence of edges between e1 and e2 (respectively e1′ and e2′ ) in f ’s embedding. Then by Claim 2.15, either the edges of h are contained in the edges of g (i.e., e1 ≤ e1′ ≤ e2′ ≤ e2 in f ’s embedding), or the edges of g and h are disjoint, except perhaps in their last or first edge (i.e., e1 ≤ e2 ≤ e1′ ≤ e2′ ). This happens in case h is a node-part of another node-part q ′ ̸= g of f (see Claim 2.10). In the former case, an edge e of h must satisfy one of the following cases: (a) If e is not incised in any level (‘ or lower), then e participates in exactly two node-parts (e’s endpoints) in each level. I.e., in level ‘ − 1 we have e = (g ; ·) and in level ‘ we have e = (h; ·), where h 33

is a part of g . Then, every endpoint v of e learns the correspondence between face-parts p(g ); p(h). Concretely, if e is the i’th edge in v ’s local embedding, then in Ĝ‘ and Ĝ‘−1 , e has two ER copies. The correspondence between p̂(g ); p̂(h) that contain these copies in the two successive levels is immediate: One copy of e is incident to the vertex vi and the other is incident to the vertex vi−1 (in each of Ĝ‘ ; Ĝ‘−1 ). Assuming f is the face left to e in v ’s local embedding (formally, the face that contains the (i − 1)’th and the i’th edge incident to v . Then, vi−1 is the copy of v that represents the parts g ; h of f in Ĝ‘−1 ; Ĝ‘ (respectively). Hence, v knows that vi ∈ p̂(g ) in Ĝ‘−1 , and that vi−1 ∈ p̂(h). Finally, because v knows the IDs of p̂(g ); p̂(h) it locally learns the correspondence between them, and equivalently between g and h and between p(g ) and p(h). If e is an endpoint-case edge, then the same proof applies except that vi is replaced by viL . (b) If e was already incised in a lower level than ‘, we handle it similarly to the above. The only difference R ;v L is that e has four copies in each of Ĝ‘ and Ĝ‘−1 , incident to the copies vi−1 i−1 ; vi ; vi of v . Then, for each of these copies, the correspondence between the components of Ĝ‘−1 and Ĝ‘ that contain it is locally learned by v . (c) If e is incised in level ‘ (e.g. e = e1′ when e1 < e1′ ). Consider first the case where e is not an endpointcase edge. Then, e has two ER copies in Ĝ‘−1 , one incident to vi and the other incident to vi−1 . In R ;v L Ĝ‘ , e has four copies, one copy for each of vi−1 i−1 ; vi ; vi . Thus, the paths in Ĝ‘ (corresponding R ;v to face-parts p(f )) that contain the copies vi−1 i−1 of v , both correspond to the path of Ĝ‘−1 that L contains the copy vi−1 of v . Similarly for vi ; vi in Ĝ‘ and vi in Ĝ‘−1 . In the case that e is an endpoint-case edge, the edge still has two ER copies in Ĝ‘−1 , however this time they are connected to vi−1 ; viL . In this case, the paths of Ĝ‘ (that represent face-parts p(f )) R ;v that contain the copies vi−1 i−1 of v , both correspond to the path of Ĝ‘−1 that contains the copy vi−1 of v , similar to the previous case. However, the paths of Ĝ‘ that contain viL ; vi in Ĝ‘ correspond to the path that contains viL in Ĝ‘−1 . I.e., the same proof as of the previous just replacing vi in Ĝ‘−1 with viL . 3. Annuli of level ‘ and annuli of level ‘ − 1. Given the correspondence between face-parts of successive levels ‘ − 1 ≥ 0 and ‘, and the correspondence between face-parts of a level k ∈ {‘ − 1; ‘} and the level k annulus that contains them. Then, the correspondence between annuli of levels ‘ − 1 and ‘ is immediate: Let annulus A be a child of annulus B. All edges of A are such that they (or copies of them) are contained in B. Let the edge e = (u; v ) in G be an edge (whose dual is) in A. Then, v knows the ID of a face-part p(g ) that contains e where g ∈ B, and the ID of a face-part p(h) where h ∈ A, and h is a part of g (see Claim 2.15). Hence, v knows the correspondence between p(h); p(g ) and the correspondence between each of them and the annulus that contains it. Then, it learns that B is a child of A. Node-parts that are not in annuli. By Corollary 2.11, every node f of G ∗ has some node-parts that participate in level-‘ annuli and other (complementing) node-parts that do not participate in any level-‘ annulus. Note however, the definition of Ĝ‘ does not make the distinction between node-parts in annuli and node-parts that are not in any annuli. Thus, if we consider all graphs that result from the incisions that lead to level ‘, and not only annuli, everything we proved also applies to them. In particular, such complementing node-parts h are still assigned IDs by Lemma 3.17. Moreover, their connected components p(h) are identified by their corresponding p̂(h) in Ĝ‘ . In Section 5, where we put everything together, we discuss this in more detail and show how a vertex v learns about such node-parts h where v ∈ p(h). We show that v learns that h should be discarded from participating in annuli of level ‘ (other information on such a node-part h is then treated as garbage). 34

3.4

Simulation of Minor-aggregation

We define the minor-aggregation model as first defined by [35]. The goal of this model is to eliminate low-level implementation details of CONGEST, allowing a clean interface for recursive edge-contraction based algorithms. The model compiles to a sequence of part-wise aggregation problems, which can then be implemented efficiently in CONGEST via the low-congestion shortcuts framework (see Section 3.3 for definitions). Definition 3.24 (Minor-aggregation model [35]). Given an undirected graph G = (V; E), both vertices and edges are computational entities (i.e. have their own processor and their own private memory). Each vertex has a unique Õ(1)-bit ID. Communication occurs in synchronous rounds. All entities wake up at the same time, each vertex knows its ID, and each edge knows its endpoints’ IDs. Each round of communication consists of the following three steps (in that order): 1. Contraction step. Each edge e chooses a value in {0; 1}. Contracting all edges that chose 1 defines a minor G ′ = (V ′ ; E ′ ) of G. The nodes V ′ of G ′ are subsets of V called super-nodes. ′ 2. Consensus L step. Each node v ∈ V chooses an Õ(1)-bit value xv . For each super-node s ∈ V , let ys = v ∈s xv , where ⊕ is a pre-defined aggregation operator. All v ∈ s learn ys .

3. Aggregation step. Each edge e = (a; b) ∈ E ′ learns ya and yb , then chooses two Õ(1)-bit values, ′ zN e;a and ze;b . For each super-node s ∈ V , let I(s) be the set of incident edges of s, then zs = e∈I(s) ze;s , where ⊗ is a pre-defined aggregation operator. All v ∈ s learn the same zs . We mention that [18] have defined an extended version of the model that supports adding virtual nodes (nodes that do not exist in the graph and need to be simulated). We discuss this in Section 3.4.3. We need this for the SSSP algorithm of [34] and to turn it into one that obeys the approximate triangleinequality. See Section 4 for more details. Thus, we focus on simulating the standard model as defined above. It was shown by [35] that using low-congestion shortcuts, any minor-aggregation algorithm can be simulated in the standard CONGEST model. It is easy to check that the consensus and aggregation steps of the minor-aggregation model can indeed be phrased as PA problems, and it was shown in [35] that the contraction step can be broken to a series of O(log n) PA problems. Hence: Lemma 3.25 (Minor-aggregation to CONGEST via PA [18, 35]). If there exists an N-round CONGEST algorithm on G for solving the PA problem on a graph H, then and r -round minor-aggregation algorithm on H can be simulated in Õ(r · N) CONGEST rounds on G, For planar graphs, when H = G we have that Õ(fi · N) = Õ(fi · D) (from Corollary 3.22), and we have the same bound when H = G ∗ (from [1]). We aim to show a similar result for simulating the minor-aggregation model on all annuli of the same level simultaneously: Theorem 3.26. Any r -round minor-aggregation algorithm can be simulated simultaneously within Õ(r D) CONGEST rounds in G on all annuli of level ‘ in T , where each annulus may contain additional Õ(1) arbitrarily connected virtual nodes. The output of a node-part f in such level-‘ annulus is known to all vertices that lie on the corresponding p(f ) in G, and the output of an edge e ∗ is known to the endpoints of e in G. Finally, the output of a virtual node in annulus A is known to all v ∈ p(f ) for f ∈ A. 3.4.1

Partwise-aggregation on Annuli

To prove Theorem 3.26, we first prove that the PA problem can be solved in Õ(D) rounds on all annuli of the same level simultaneously. Then, we use that to prove Theorem 3.26 similarly to [1, 35]. 35

Lemma 3.27. Let A1 ; : : : ; Ak be the level-‘ annuli. For every i, let Pi = Ai;1 ; Ai;2 ; : : : be a given partition of Ai into node-disjoint connected subgraphs, such that: (1) level ‘ is distributively stored, (2) each vertex v ∈ G, for each node-part f ∈ Ai s.t. v ∈ p(f ), knows the ID of the part Ai;j that contains f , (3) for each node-part f ∈ Ai , there is a leader xf . Then, for any predefined L vertex v ∈ p(f ) that knows the Õ(1)-bit input string L aggregate operator , in Õ(D) rounds, each vertex v ∈ G learns the function g ∈Ai;j xg for each part Ai;j where there exists f ∈ Ai;j s.t. v ∈ p(f ). Proof. We first show that each Ai;j corresponds to a unique subgraph of Ĝ‘ . Recall that we simulate the annuli Ai using Ĝ‘ . In particular, Ai corresponds to a connected component Âi of Ĝ‘ [ER ∪ EC ] (Lemma 3.14). Moreover, the node-parts of Ai correspond to vertex-disjoint subgraphs (paths) of Âi (Lemma 3.6 and Lemma 3.14). Thus, a partition Pi of Ai induces a partition P̂i of Âi . In particular, for each part Ai;j there is a part Âi;j in P̂i that contains all vertices that lie on a path p̂(f ) of Âi;j for a node f ∈ Ai;j . Note: Claim 3.28. Âi;j is connected. The claim follows from Lemma 3.14, and concretely: (1) each p̂(f ) is connected (Lemma 3.6), (2) there is an EC edge connecting p̂(f ); p̂(g ) iff the edge (f ; g ) ∈ Ai;j (Lemma 3.13), and (3) Ai;j is connected by assumption. That is, P̂i is a partition of Ai into node-disjoint connected subgraphs. The next claim follows from: (1) all p̂(f ); p̂(g ) are disjoint for any f ̸= g in Ai (Lemma 3.6), and (2) Pi is a partition so a node f ∈ Ai is in exactly one part Ai;j ∈ Pi . Claim 3.29. Each two parts Âi;j ̸= Âi;j ′ in P̂i are vertex-disjoint. Let P̂ be the union of all partitions P̂1 ; : : : ; P̂k together with the star-center vertices VS = V (the only Ĝ‘ vertices that do not appear in any P̂i ). Then P̂ can be seen as a partition P̂ of Ĝ‘ itself. Thus, we have: Claim 3.30. P̂ is a partition of Ĝ‘ into vertex-disjoint connected subgraphs. Computing PA on P̂ where the input of a leader vertex of a node-part f in p̂(f ) is xf and otherwise an identity element, results in the same output of computing PA on the union of P1 ; : : : ; Pk in level ‘ of T . Thus, we compute part-wise aggregations on P̂ in Ĝ‘ in order to simulate part-wise aggregations on P. We explain the input and output format to the part-wise aggregation task in more detail. First, note that the VS star-centers and the edges ES do not participate as input because they do not appear on any p̂(f ) or Âi;j of Ĝ‘ (Lemma 3.6 and Lemma 3.14). They are used exclusively for communication. Initially, all vertices in a part Âi;j know the ID of Âi;j . This is because v ∈ G knows, for each f ∈ Ai where v ∈ p(f ), the ID of Ai;j that f belongs to (assumption), and because v knows the correspondence between its copies in Ĝ‘ and p̂(f ) (Lemma 3.17). In addition, the partition P̂ into vertex-disjoint subgraphs is known to the vertices of Ĝ‘ (Lemma 3.15). Recall that in the PA task, each node f in a part of the partition has an Õ(1)-bit input, and the aggregate operator is computed over all inputs of nodes that are in the same part (Definition 3.20). When computing a PA task over nodes of Ai , the input of f ∈ Ai is required to be known to the leader vertex of p̂(f ) in Ĝ‘ (see Lemma 3.17). Then, aggregations inside all Âi;j simulate aggregations inside Ai;j , where only the input of the leader of p̂(f ) is considered as an input (all other vertices on p̂(f ) participate with an identity element). If the PA task is over inside-part edges or over outgoing edges of parts Ai;j , then each vertex vi of Ĝ‘ that is incident to an edge ê = {vi ; vi+1 } ∈ EC (recall, edges of EC map 1-1 to edges of Ai s by Lemma 3.13), knows if ê’s input should or should not be considered in the aggregation. As vi knows the ID of the part Âi;j that contains it, and knows the ID of Âi;j ′ that contains vi+1 locally (because both vi ; vi+1 are simulated by v ∈ G). Note that this is the only case, i.e., for i ̸= i ′ there are no edges between any part Ai;j and Ai ′ ;j ′ because Ai and Ai ′ are distinct annuli (disconnected graphs) in level ‘. Hence, aggregations on all Âi;j simulate aggregations on the parts Ai;j , where any Ĝ‘ vertex knows whether it should participate in the aggregation and if so with which input (as explained above). 36

Finally, by Corollary 3.23, the PA task on Ĝ‘ for the partition P̂ (i.e., computing aggregations on all Âi;j simultaneously) is done in Õ(D) rounds. Upon termination, all vertices in Ĝ‘ \ V know the output value of their part. This directly translates from Ĝ‘ to G, as each vertex of G knows all information of its copies in Ĝ (Lemma 3.16). In particular, v ∈ G knows the output of a node any f that is contained in an annulus Ai of level ‘ s.t. v ∈ p(f ). This concludes the proof of Lemma 3.27. 3.4.2

Standard Minor-aggregation on Annuli

Next, we use the above lemma in order to simulate minor-aggregation algorithms on level-‘ annuli, concluding Theorem 3.26. Proof of Theorem 3.26. Let A1 ; A2 ; : : : ; Ak be the level-‘ annuli. We explain how to simulate the minor aggregation model using PA on an arbitrary annulus Ai of level ‘. The parallelization to all annuli in the same level follows from Lemma 3.27. In particular, each of the r rounds of the minor-aggregation algorithm is simulated by a fixed number of rounds in Õ(D), s.t. the PA problem being solved in any given moment is the same for all annuli Ai . I.e., we would have a problem if different annuli of level ‘ are in different stages of the minor-aggregation algorithm. The issue is then that some annuli may want to change the partition on which we solve PA (according to the algorithm they run), meaning that in Ĝ‘ we would need to construct low-congestion shortcuts again despite the fact that perhaps other annuli did not finish their PA task yet. This issue is easily solved by scheduling the update of partitions ( i.e., reconstruction of lowcongestion shortcuts in Ĝ‘ ) to start at specific rounds that are given by the simulation algorithm. E.g. divide the time into intervals of t = D logc n (for some constant c) rounds, such that the partitions are updated at the beginning of each interval, and the aggregation task is computed in the remaining time until the beginning of the next interval. We proceed to the simulation for the annulus Ai . Let s = {f1 ; f2 ; : : :} be a super-node of Ai (fi ∈ V (Ai )). The vertices of Ĝ‘ that map to s are the vertices that lie on the paths p̂(fi ) of Ĝ‘ that represent p(fi ). Then, the computational power of a super-node of Ai is simulated by all vertices of Ĝ‘ that map to it. The computational power of an edge in (a minor of) Ai is simulated by the endpoints of its corresponding EC edge in Ĝ‘ (Theorem 3.1, Lemma 3.13). We use Lemma 3.27 as a black-box for PA on Ai in order to implement the simulation. There are three (ordered) steps in a minor-aggregate round: contraction, consensus, and aggregation. There is an additional implicit initial step at the start of each round for electing a leader of each supernode. We follow [35] and show how all steps compile down to PA in Ai . Obviously, we differ from [35] for simulating the model on dual (rather than primal) subgraphs (the annuli). For that purpose, we consider our communication graph to be Ĝ‘ and not G (Lemma 3.16). 1. Electing a leader (and contraction). In the contraction step, we need to contract every edge with value one. First, we merge clusters of nodes of Ai over their outgoing edges of value one (clusters eventually define super-nodes of Ai ). Second, we assign each cluster an ID that is known to all vertices of Ĝ‘ that simulate it. Initially, a cluster is a single node of Ai . Then, clusters are grown to match the set of supernodes of (the minor of) Ai in the current round of the minor-aggregation algorithm being simulated. To implement this, we first detect connected components of Ĝ‘ [ER ] (paths and cycles of Ĝ‘ that map to nodes f ∈ Ai ), where the ID of a node f of Ai is the maximal ID of a vertex in Ĝ‘ that lies on p̂(f ). This is done in Õ(D) rounds as explained in the proof of Lemma 3.17. Now, each vertex of Ĝ‘ knows its connected component, and each node of Ai is defined as a cluster. We can apply Lemma 3.27 (PA in Ai ) due to the fact that all vertices of Ĝ‘ that correspond to a node f ∈ Ai in a cluster, know the same ID for that cluster. The merging process follows Boruvka’s classic scheme, that does O(log n) star-shaped merges. The classic implementation is similar to that of [14, 17, 18]. Namely, the PA task on Ai is when each cluster defines a part in the partition of V (Ai ) and the aggregate operator is computed over the clusters’ outgoing 37

edges that chose a value of 1 in the contraction step. This determines the merges as follows: the operator computed is over labels of neighboring clusters incident to those edges, where each cluster is labeled as a joiner or a receiver. Joiners suggest merges and receivers accept them (i.e., receivers are the star centers in the star-shaped merges). Randomly, the labels are decided by a fair coin flip that the cluster’s leader tosses and broadcasts to the entire cluster. Deterministically, the classic algorithm for 3-coloring by Cole and Vishkin [8] is used (E.g. see [18] for more details). In any case, at most Õ(1) merges are repeatedly done until clusters match super-nodes of G ∗ . In each phase of merges, all nodes of the same cluster maintain the cluster’s ID to be the maximum ID of a node f ∈ Ai that is in the cluster (then, clusters’ IDs define the partition of Ai into clusters, which is the input of the next phase of the O(log n) merging phases). The vertex of Ĝ‘ that has that maximum ID is considered to be the leader of vertices in Ĝ‘ that map to the super-nodes represented by the cluster. At the end of each merging phase Lemma 3.27 (PA on Ai ) is applied. Overall, it is applied repeatedly Õ(1) times, and after Õ(D) rounds the clusters are the super-nodes and all vertices of Ĝ‘ that simulate the same super-node have a shared leader and ID. 2. Consensus. After assigning IDs to clusters, each vertex of Ĝ‘ knows the ID of the cluster that it maps to, which is used as the part ID in the part-wise aggregation tasks on Ai . Regarding input, the input is perhaps unique per node of Ai , and the elected leader in Ĝ‘ knows it for the node f ∈ Ai that it leads. Hence, Lemma Lemma 3.27 is applicable and is used to implement the consensus step in Õ(D) rounds on G. 3. Aggregation. After performing the consensus step, each endpoint vi in Ĝ‘ of an edge in EC informs the other endpoint vi+1 with the consensus value of the cluster that vi maps to. After that, each endpoint vi ∈ Ĝ‘ of an edge e ∈ EC that maps to the edge e ∗ = (a1 ; a2 ) (where a1 ; a2 are distinct super-nodes of the minor of Ai ) thinks of the edge e as if it was assigned the value/weight of ze;ai if vi is in the cluster (that maps to) ai . Otherwise (when the endpoints a1 ; a2 of e map to the same cluster), vi considers the identity element as input for e. Again, the aggregation is done by Lemma 3.27 in Õ(D) rounds on G. Finally, the two endpoints of each edge know the output of the aggregate operator. Thus, they can choose zero or one for that edge (the input to the next contraction step). Note, after the simulation finishes, each vertex v of G knows the output value of the super-node that contains f ∈ Ai where v ∈ p(f ), and the output of each dual edge e ∗ that corresponds to an incident edge to v . This information is known to v from its copies in Ĝ‘ that simulate f and e ∗ (Lemma 3.15). 3.4.3

Minor-aggregation on Annuli with Virtual-nodes

We aim to simulate the extended minor-aggregation model, which is the model as defined in Definition 3.24 after adding to the annulus Õ(1) arbitrary connected virtual-nodes. See [18] for a formal definition and discussions. We need to use this (in a black-box manner) in order to have an SSSP algorithm that runs in Õ(D) rounds and obeys the approximate-triangle inequality. The proof that we can implement this model is also a black-box corollary of implementing the standard model (Definition 3.24). I.e., is a corollary of the above Section 3.4.2. In particular, [18] show that there is a standard minor-aggregation algorithm (compiler) that simulates the extended model with a multiplicative overhead proportional to the amount of virtual nodes. Thus, we use that result in a black-box manner (see Section 4.1 and Theorem 14 of [18] for details), which immediately allows us to simulate the extended model, concluding the proof of the stimulation theorem on annuli (Theorem 3.26). Lemma 3.31 (Theorem 14 of [18]). Let Alg be a r -round minor-aggregation algorithm, and Hv ir t be a connected virtual graph obtained from a connected input graph H, that contains ˛ virtual nodes. There is a O(˛ · r )-round (standard) minor-aggregation algorithm Alg ′ that runs in H and simulates Alg on Hv ir t . Upon termination, each non-virtual node f ∈ H learns all information learned by f and all virtual nodes.

38

We elaborate on how this translates to simulating extended minor-aggregation algorithms on all annuli of level ‘, where each annulus may contain up to Õ(1) virtual nodes. At the beginning this may seem not possible, for in certain levels of recursion we might have up to Ω(n) annuli, and thus a total of Ω(n) virtual nodes across the level that need to be simulated. However, those virtual nodes are simulated the same way we simulate annuli. That is, each annulus corresponds to a distinct connected component of Ĝ‘ (and thus G) that simulates it. The same component is also responsible for the virtual nodes of the annuli it simulates.

4

Approximate SSSP and Eulerian Orientation

This section proves the following theorem on running SSSP simultaneously on all annuli of the same level. Theorem 4.1. Let › be a parameter known to all v ∈ G. Assume all level-‘ incisions are distributively stored, and for each level-‘ annulus Ai the ID of a source node fi is known to all v ∈ G where v ∈ p(fi ). Then, in Õ(D=›2 ) rounds, a (1 + ›)-approximate SSSP tree Ti rooted at fi is computed for all i simultaneously. Moreover: 1. Ti obeys the approximate triangle inequality (as defined in Appendix A). 2. For each node-part g ∈ Ai , the length of the fi -to-g path in Ti is known to every vertex v ∈ p(g ). 3. Each vertex v ∈ G knows for each incident edge e, in what trees Ti (a copy of) e’s dual is contained (and the IDs of its endpoints in Ti ). To prove Theorem 4.1, we wish to use the approximate SSSP algorithm of [34]. This raises three obstacles. First, an annulus can be a multi-graph and to use the algorithm of [34] we need to turn it into a simple graph. Second, we need to turn the algorithm of [34] into one that obeys the approximate triangle inequality. Both these obstacles are easily resolved by simulating two minor-aggregation procedures from previous works [1, 33], which is possible by using Theorem 3.26. See Section 4.2 for more details. The third obstacle is the most challenging: The original algorithm of [34] is not (fully) a minoraggregation algorithm. Specifically, all its components do work in the minor-aggregation model except for one - an Eulerian orientation oracle. The oracle was implemented in [34] using Õ(1) CONGEST rounds and Õ(1) instances of the PA problem. This is not good enough for our purposes as we do not know how to simulate CONGEST on annuli (in fact, it is not known whether CONGEST can be even simulated on G ∗ itself without suffering the trivial O(n) blow-up in round complexity). We discuss this in this section, where we define and refine the Eulerian orientation oracle to run in Õ(D) rounds on all annuli of the same level simultaneously. After solving the problem in Section 4.1, we complete the proof of Theorem 4.1 in Section 4.2. The Eulerian orientation oracle OEul er . In this problem one is given an Eulerian graph H as an input (a graph is Eulerian iff all its degrees are even), and needs to orient its edges such that the in-degree equals the out-degree for all nodes of H. The problem that we need to solve in order to implement [34] SSSP algorithm on annuli is the following. Definition 4.2 (OEuler , Definition 3.8 of [34]). Let A be the input graph to the SSSP algorithm. The problem asks to find an Eulerian orientation to an Eulerian graph H, which is a subgraph of Av ir t , where Av ir t is A with up to Õ(1) additional virtual nodes. A simple (centralized) solution. We describe a classic simple solution, the barriers of turning it into a distributed solution, and how to surpass them. See also Figure 22. 39

Lemma 4.3 ([3]). The following procedure solves the Eulerian Orientation problem: 1. Local step. Decompose H into edge-disjoint cycles by pairing the edges incident to each node v ∈ H. 2. Global step. Identify and consistently direct each cycle of the decomposition.

Figure 22: Left: an Eulerian graph where edges with the same color incident to a node are paired. Note that pairing of edges corresponds to edge-disjoint closed walks (cycles) of the graph. Right: The resulting two-regular graph from splitting each node v into deg(v )=2 nodes (a node per two paired edges). To see how the local step gives a decomposition into edge-disjoint cycles, imagine splitting each node v ∈ H into deg(v )=2 nodes, each incident to two paired edges of v . Then, the resulting graph is a union of node-disjoint cycles (see Figure 22 right). Clearly, there is a 1-1 mapping between those cycles and cycles of H defined by the edge pairing. Note, each two paired edges incident to a vertex v ∈ H participate in exactly one cycle. Directing this cycle in a consistent manner, directs paired edges of each node that participates in the cycle in opposite directions. Note that when the degrees are not all even, then each node might have one unpaired edge, and the resulting graph is of maximum degree two, which is a union of cycles and paths. We emphasize this because in certain cases of the distributed algorithm, we may also deal with paths. Towards a solution on annuli. Indeed, this approach of pairing edges is the main idea to solve the problem in various models of computation. E.g. the parallel algorithms of [3, 5], the distributed HYBRID algorithm of [6], and even the CONGEST algorithm of [34] that we cannot run on annuli. The main issue with this approach in the CONGEST model is to run an algorithm on all cycles simultaneously in order to direct each of them. That is because the cycles are not node-disjoint and may be of large diameter. Of course, the cycles being edge disjoint intuitively should help but it is not clear how. The work of [34] deals with those challenges and devises a fairly complicated algorithm that solves the problem for various graph families with different round complexity tradeoffs. We face a similar challenge although we are in a different setting. Namely, we can run minor-aggregation algorithms on annuli but not on multiple edge-disjoint subgraphs of them. However, we show that the centralized approach can be adapted to direct a set of edge-disjoint paths (cycles) of each annulus. The solution uses tools developed in the previous section. In particular, we show that such a set of paths of annuli maps to a related set of edge-disjoint subgraphs in Ĝ‘ . Then, with a small change to Ĝ‘ , those subgraphs are made vertex-disjoint. Thus, we can work in all of them simultaneously using low-congestion shortcuts in order to orient the paths of annuli. We define a notion edge paring that utilizes planarity, so that it can be used to implement the centralized Lemma 4.3 distributively in annuli. Definition 4.4 (Annuli edge pairing). Let f be a node-part defined by edges e; e ′ (see Definition 2.9). An edge pairing splits edges incident to f into pairs of consecutive edges in f ’s local embedding. I.e., into pairs (ei ; ei+1 ) for e ≤ ei < ei+1 ≤ e ′ . We say that an edge paring is distributively stored if: For each node 40

f , each incident edge e knows whether it is the first or the second edge in f ’s pair that contains it. If f ’s degree is odd, then one edge of f is allowed to be not paired. That edge knows itself.

4.1

Eulerian Orientation on Annuli

We now show how to solve the Eulerian Orientation problem, as required by the SSSP algorithm of [34] (see Definition 4.2). Lemma 4.5 (OEuler for annuli). There is an Õ(D)-round algorithm that implements the Eulerian orientation oracle OEuler (Definition 4.2) for all level-‘ annuli simultaneously. The solution of [34] consists of two steps. First, virtual nodes of H get eliminated, producing an Eulerian subgraph H ′ of A (Lemma 6.4 and Proposition 6.5 of [34]). H ′ is then handled using different approaches related to the graph’s family (Section 6.2 of [34]). To implement these steps in the minoraggregation model, we follow a similar scheme to [34]. Namely, we show that their procedure for handling virtual nodes can be implemented using our techniques for all level-‘ annuli. Afterwards, we handle the remaining subgraphs differently, by implementing the centralized procedure (Lemma 4.3) for annuli. Both procedures are not implementable in the minor-aggregation model straightforwardly. However, they can be implemented easily (not particularly in the minor-aggregation model) if the following two primitives are available: (1) pairing edges in order to define a set of edge-disjoint paths, and (2) directing each of those paths in a consistent manner. Thus, we assume that those tasks can be solved near-optimally on annuli and provide a proof to Lemma 4.5. After which, we prove that we can indeed solve these tasks (which is the main contribution of this section). I.e., for now we assume the following two lemmas (proofs of which are provided in Section 4.1.1 and Section 4.1.2). Lemma 4.6 (Pairing annuli edges). Assume a given subgraph H for each annulus A of level ‘. For all annuli of level ‘ (simultaneously), we compute and distributively store (as in Definition 4.4) an edge pairing of all nodes f ∈ H within Õ(D) rounds. Lemma 4.7 (Orienting edge-pairing induced paths). Assume a distributively stored (as in Definition 4.4) edge pairing of a subgraph H for each annulus of level ‘. Then, within Õ(D) rounds on G, one can consistently orient the edge-pairing induced paths in all annuli simultaneously. Upon termination, each edge of H knows its direction. Given the above two lemmas, we now prove Lemma 4.5. Proof of Lemma 4.5. Recall (Definition 4.2) that for each level-‘ annulus A the problem asks to find an Eulerian orientation to an Eulerian graph H, which is a subgraph of Av ir t , where Av ir t is A with up to Õ(1) additional (arbitrarily-connected) virtual nodes. H is a graph produced by the SSSP algorithm of [34]. Concretely, by the Õ(1) minor-aggregation rounds simulated on A in the other steps of [34]’s algorithm, before the Eulerian orientation step, which we solve here. We follow [34] and work in two phases. The first eliminates virtual nodes from H (and some other edges) leaving a residual Eulerian graph H ′ that contains no virtual nodes (H ′ is a subgraph of A). The second phase solves the problem on H ′ . Phase two. We discuss the second phase first. It follows directly from the above Lemma 4.6 and Lemma 4.7. I.e., after the first phase terminates, we get the subgraph H ′ of A (for all A of level ‘). We then need to solve the Eulerian orientation problem on all graphs H ′ for all annuli A of level ‘. Namely, by the end of the first phase, each edge of A knows whether it is in H ′ or not. Then, we apply the centralized approach of Lemma 4.3 on H ′ , implemented as follows: via Lemma 4.6, for all annuli of level ‘ simultaneously, we compute an edge-pairing of H ′ within Õ(D) rounds. This results in a decomposition of each annulus into a set of edge-disjoint cycles, each of which needs to be consistently oriented. Then, by Lemma 4.7, we 41

simulate the global step of orienting the resulting cycles. This is also done within Õ(D) rounds, for all annuli of level ‘ simultaneously (by Lemma 4.7). Note, the input format of Lemma 4.7 matches the output format of Lemma 4.6 (both follow Definition 4.4). Next, we focus on phase one. First, we discuss the idea and components as in [34]. Then, we prove that we can implement it for all annuli of the level simultaneously within Õ(D) rounds. General idea of phase one. We explain the intuitive idea that [34] apply to handle the case of a single virtual node f . We want to find edge-disjoint cycles that contain all edges incident to f . To do so, they find a set of edge-disjoint paths of H \ {f }, where each of them can be closed to a cycle by adding exactly one pair of f ’s edges. Orienting each of these paths implies an orientation on the pair of f ’s edges that participate in the same cycle. This takes care of all edges of f and some other edges of H. Hence, we can eliminate f . Moreover, since the edges of H that get directed are edges of cycles, removing those cycles keeps a residual Eulerian graph H ′ that does not contain any virtual node. There are two key steps in extending this approach to the case of Õ(1) virtual nodes. The first is to find a certain set of edge-disjoint paths in H that does not contain any virtual edge, and then orient them. Those paths extend the above idea of one virtual node to many. In particular, orienting those paths induces an orientation to all edges of H whose (exactly) one endpoint is a virtual node. This is done in Lemma 6.4 of [34] (also a variant of Lemma 4.3.2 of [29]), which we cannot use as black-box on annuli (it is not a minor-aggregation procedure) but we can implement it using our tools, as we explain shortly in the part of the proof that discusses the implementation of phase one. The second step is to handle edges between different virtual nodes. Those edges were not oriented in the previous step. Both steps are done by Proposition 6.5 of [34], which in the first step applies the aforementioned Lemma 6.4 of [34] multiple times. Then, in the second, broadcasts a total of Õ(1)-bits. Concretely, the broadcast information is roughly the virtual-node to virtual-node edges in addition to some other Õ(1) edges. Then, orienting those edges can be solved locally as they are known to the entire graph. Since broadcast is an aggregate operation, then broadcasting Õ(1)-bits can be implemented in the minor-aggregation model within Õ(1) rounds. Note, we have no problem simulating this on all annuli of level ‘ simultaneously in Õ(D) rounds (by Theorem 3.26). Thus, all we need in order to implement phase one on all annuli of the same level is an implementation of Lemma 6.4 of [34] for finding a certain set of edge-disjoint paths and orienting them (discussed next). Claim 4.8 (Proposition 6.5 of [34]). Given an implementation of Lemma 6.4 of [34] that runs within Õ(D) rounds, in additional Õ(D) rounds all edges incident to virtual nodes of H are oriented (possibly with some other edges) leaving a Eulerian subgraph H ′ of A. Implementation of phase one. We are asked to find a set of edge-disjoint paths that obeys a certain structure. Concretely, Lemma 6.4 of [34] asks for the following: Input: A rooted spanning tree T of H minus the virtual nodes, and a set of marked nodes S ⊆ V (T ).12 Output: A set of edge-disjoint paths that are subpaths of T , such that all nodes of S (except for possibly one) are endpoints of exactly one path. In addition, each of those paths needs to be oriented. To find those paths, first we find the tree T , then, in order to find such a set of paths, a simple Õ(1) minoraggregation round subtree sum procedure is performed on T . Second, a step of pairing edges completes computing the paths (using Lemma 4.6). After which, the paths get oriented using Lemma 4.7. We explain each step and its implementation. 12

For more context, S is the set of non-virtual neighbors of the virtual nodes of H. Our implementation is independent from this fact.

42

1. Finding T and subtree sums. In Proposition 6.5 of [34] the spanning tree T of A is computed using Õ(1) instances of the PA problem (Definition 3.20) and Õ(1) CONGEST rounds. However, by Example 4.4 of [35], T is computed by a Õ(1) round minor-aggregation procedure that computes a (minimum) spanning tree. After computing T , we need to apply the subtree sums procedure that defines the desired paths. In particular, using this subtree sums computation, nodes of T mark some of their incident edges that need to be paired. Then, pairing marked edges locally defines the required set of paths. For context, those edges indicate merging requests that define paths. I.e., the computation of [34] is as follows. For each node g ∈ T , let xg = 1 if g ∈ S and xg = 0 otherwise. We want to compute the subtree sum sg for every g ∈ T . This defines paths as follows. If sg is odd, g will be connected in a path with its parent (unless g is the root). Each edge connecting such a node to its parent marks itself; indicating a request of g to its parent f to be paired with another child of f , or possibly the parent of f if all other children of f are paired to each other. I.e., f simply needs to pair its marked edges. This subtree sum procedure can be easily implemented in Õ(D) rounds on all annuli of level ‘ using a classic Õ(1) rounds minor-aggregation procedure as a black-box (simulated by Theorem 3.26). E.g. Lemma 16 of [18], or Lemma B.8 of [34] (see also Lemma 5.2 later in the section). 2. Pairing edges. As mentioned, a node f needs to match its marked edges. However, in our case f does not have a list of its children and did not learn the IDs of marked edges as this is not feasible in the minor-aggregation model (and requires a round complexity proportional to f ’s degree). However, we know how to deal with this. I.e., this problem of pairing edges can be solved on all annuli A of level ‘ simultaneously within Õ(D) rounds. Simply, we apply Lemma 4.6 on the graph H after removing all its virtual nodes (i.e., on a subgraph of A). The pairing we find is distributively stored as in Definition 4.4 (roughly, each marked edge knows whether it is the first or the last in its pair, and knows an ID of the pair). This knowledge is enough to orient the formed paths by the edge-pairing as we explain next. 3. Orienting the paths. After pairing the edges and distributively store the edge pairing, we use Lemma 4.7 in order to consistently orient each of those paths, for all annuli of level ‘ simultaneously within Õ(D) rounds. It follows from claim 4.8 (Proposition 6.5 of [34]) that, within additional Õ(D) rounds, we take care of all virtual nodes of H (and some other edges) leaving an Eulerian subgraph H ′ of A that needs to be handled. That graph is handled as explained at the beginning of the proof. This concludes Lemma 4.5 for implementing the Eulerian orientation oracle OEuler (Definition 4.2). 4.1.1

Decomposing Annuli to Edge-disjoint Paths

We now prove Lemma 4.6, stating that for all annuli A of level ‘, simultaneously, in Õ(D) rounds we can pair edges of any given subgraph H of A as in Definition 4.4. Since we can run only minor-aggregation algorithms on annuli, we have a significant problem: A node cannot pair its incident edges because it does not know their IDs, and learning the IDs of neighbors in this model has round complexity that is proportional to the maximum degree of a node, which may be Ω(n). However, this problem can be solved easily using Ĝ‘ : Use aggregations on p̂(f ) in order to enumerate edges of a node f . This defines a pairing of the edges incident to f . E.g. edges that are assigned numbers 2k − 1; 2k are paired, for 1 ≤ k ≤ deg(f )=2. Proof of Lemma 4.6. Let A be an annulus of level ‘, and assume a given subgraph H of A s.t. each edge of A knows whether it is in H. We show how to pair edges of H. We focus on a single node f ∈ A, the parallelization to all nodes in A, and to all annuli of level ‘ is discussed at the end of the proof. 43

Note that f has two types of edges (in H or not). In order to pair edges of H as described, we assign numbers (IDs) to edges of H according to their order in f ’s embedding, then each edge of an odd number is paired with the next edge (of even number). That is, the edges 2k − 1; 2k are together for 1 ≤ k ≤ ⌊degH (f )=2⌋. If there is a residual edge then it is not paired. Hence, the problem is reduced to finding such an enumeration of edges. Such an enumeration of edges can be computed via p̂(f ) in Ĝ‘ as we explain next. We are able to compute this enumeration of f ’s edges in H by computing subtree sums on p̂(f ): (1) Assign p̂(f ) a root, which is an endpoint of p̂(f ) in case it is a path, and otherwise (when it is a cycle) an arbitrary vertex. (2) If p(f ) is not an entire face of G, then p̂(f ) is a path (tree). Otherwise, p(f ) is an entire face of G, p̂(f ) is a cycle, and we want to compute a spanning path of it. To do so, the root eliminates one of its incident edges in p̂(f ), defining a spanning path of p̂(f ). Now we are ready to perform the subtree sum on a (spanning path of) p̂(f ): Each vertex of Ĝ‘ incident to an ER edge that corresponds to an H edge, learns that the input to that edge is one, all other edges’ input is zero.13 This subtree sums on edges is reduced easily to subtree sums on vertices (the input to a vertex is the input to the edge connecting it to its parent). After computing the subtree sums, (3) The vertices of p̂(f ) can locally learn the numbers of their incident edges (in case p̂(f ) is a cycle, then the eliminated edge can be assigned a number by the root if it is in H). Thus, the pairing can be deduced locally and be distributively stored. I.e., the endpoints u; v of an edge e in G know whether (the dual in A of) e is in H, and if so, u; v know for each ER copy of e whether it is the first (assigned an odd number) in its pair or not (assigned an even number). I.e., for each endpoint of (the dual of) e in the annulus A, u; v know whether e is the first in its pair. Since u; v simulate the edge e in the minor-aggregation simulation of A, then one can say that the edge in A knows the information about itself that u; v know. Electing a leader and the subtree sums procedure can be performed via simple minor-aggregation procedures performed on p̂(f ) as the input graph. E.g. electing a leader can be done in one round of computing the maximal ID of a vertex to be the leader, and subtree sums can be performed within Õ(1) minor-aggregation rounds (for example, by using the algorithm from Lemma 5.2 in the next section). The reason we can simulate a round of the minor aggregation model on p̂(f ) within near-optimal Õ(D) rounds, is that planar graphs of diameter O(D) allow such simulation (Theorem 17 of [18]; [34, 35]). By Theorem 3.1, Ĝ‘ is such a graph where a CONGEST round on it is simulated by O(1) rounds on G. Finally, the parallelization to all nodes of level ‘ (all p̂(f ) in Ĝ‘ ) follows for two reasons: (1) For all nodes f ̸= g of level ‘, the graphs p̂(f ) and p̂(g ) are connected, and are vertex-disjoint (Theorem 3.1). (2) Running a minoraggregation algorithm in multiple vertex-disjoint subgraphs (p̂(f ), p̂(g )) of a graph (Ĝ‘ ) in parallel can be simulated within the same round complexity of running the algorithm on a single subgraph (Corollary 11 of [18]; [34, 35]). 4.1.2

Orienting Edge-disjoint Paths in Annuli

It is not hard to see that an edge pairing in an annulus corresponds to a collection of edge-disjoint paths (see the discussion following Lemma 4.3). We aim to orient each of those paths consistently. I.e., to prove Lemma 4.7. Trying to do that on annuli straightforwardly does not work, as each path might be very long and the round complexity would depend on the paths’ diameter. To tackle this problem, we turn to Ĝ‘ and observe that the problem on annuli corresponds to a similar problem on Ĝ‘ . In particular, we take a primal point of view on edge-pairings in annuli. Then, we derive several properties related to Ĝ‘ and paths given by the edge-pairing. After which, we employ those structural properties to obtain a new graph Ĝ‘′ whose structure is related to the paths induced by the edge-pairing. In particular, paths defined by the 13

We note that an edge of H might have two corresponding ER edges in p̂(f ). In that case, we want to assign only one them an input, and the other zero. Those edges are incident to two copies uj ; uk of the same node u, thus, u and their other endpoints can locally coordinate and choose an arbitrary ER copy of the edge to assign it an input.

44

edge-pairing correspond to vertex-disjoint subgraphs of this new graph. By performing computations on those subgraphs, we simulate an orientation procedure, producing the promised orientation of the paths. Paths defined by edge pairings and Ĝ‘ . Note that when Definition 4.4 is applied to a node f in a subgraph H of the annulus A (f ∈ A), then the definition discusses f ’s incident edges in H. See also Figure 23. Taking a primal point of view on an edge pairing, we note that each two paired edges of f are

Figure 23: Left: A node f and an edge pairing of it in a subgraph H of A. Edges of A \ H incident to f are red. Paired edges of H are demonstrated by colors: orange, pink, green. The gray edge is the only nonpaired edge, because f ’s degree in H is odd. Right: The corresponding face-part p(f ) and its partition into internally-disjoint subpaths p̂(f )i , which is demonstrated by shadow colors. Note the mapping between subpaths p̂(f )i and paired edges of f in H. Note that a pair of edges in H (for example the green pair) might map to a subpath of p̂(f ) that contains edges whose dual is not in H. This keeps the paths p̂(f )i connected. In addition, some edges of p̂(f ) whose dual is not in H do not participate in any path p̂(f )i ; For example, the edges of A \ H in between the gray and pink edges (clockwise). on a unique subpath of p̂(f ). This is because two consecutive edges of f are also consecutive in p̂(f ). Moreover, those subpaths overlap only with their endpoints. See Figure 23. Therefore: Lemma 4.9. Let H be a subgraph of an annulus A, and assume a given edge pairing of H. For a node f ∈ H, any two paired edges correspond to a subpath of p̂(f ), denoted p̂(f )i for the i’th pair. The paths p̂(f )i ; p̂(f )j are internally disjoint for any i ̸= j. Since there are edges of A not in H, p̂(f ) minus the paths p̂(f )i may contain some other paths corresponding to those edges. Proof. A pair of consecutive edges of f in H corresponds to a sequence of edges of f in A. This sequence contains the two paired edges in H and all A edges between them in f ’s embedding. In addition, any two disjoint sequences of edges of f corresponds to edge-disjoint subpaths of p̂(f ), by Lemma 3.6. Edges of A \ H that are not in between two paired edges (in the local ordering of f ) correspond to their own subpaths of p̂(f ). Using this lemma, we can make the paths p̂(f )i vertex disjoint by simply splitting their endpoints in Ĝ‘ . This allows us to perform computations on components of the resulting graph in order to simulate orienting the paths of H defined by the edge pairing. Concretely, let Q = q1 ; q2 ; : : : be some path in an annulus, defined by the given pairing of edges. I.e., for each node qj , its incident edges (qj−1 ; qj ); (qj ; qj+1 ) are paired and participate in Q (one of those edges might be empty if qj is an endpoint of Q when Q is a path and not a cycle). In addition, by Theorem 3.1 each edge of an annulus (in particular of Q) has a corresponding EC edge in Ĝ‘ . Moreover, by Lemma 4.9 this pair of edges of qj corresponds to a subpath p̂(qj )ij of p̂(qj ) (ER edges). Then (see also Figure 24): Claim 4.10. The path Q corresponds to a subgraph Q̂ of Ĝ‘ [ER ∪ EC ], defined as follows: the subpath p̂(q1 )i1 of p̂(q1 ), the EC edge mapping to edge (q1 ; q2 ), the subpath p̂(q2 )i2 of p̂(q2 ), the EC edge mapping to (q2 ; q3 ), and so on. 45

Proof. We rephrase the claim: For qj ∈ Q, the EC edges in Ĝ‘ corresponding to its (up to) two edges (qj−1 ; qj ); (qj ; qj+1 ) in Q are in fact connected. In particular, the subpath p̂(qj )ij (consisting of ER edges) of p̂(qj ) connects them. The vertices of this subpath are not incident to any EC edge that corresponds to (an edge of) H except for (qj−1 ; qj ); (qj ; qj+1 ). Next, we prove that this is correct. The edges (qj−1 ; qj ), (qj ; qj+1 ) are paired by qj , and by Lemma 4.9 two paired edges correspond to a subpath p̂(qj )ij of p̂(qj ) whose (ER ) edges correspond to qj ’s edges in A. The local ordering of those edges is in between the edges (qj−1 ; qj ); (qj ; qj+1 ). Moreover, by definition of Ĝ‘ , an EC edge that corresponds to an edge e is incident to a an endpoint of an ER copy of e. Hence, the only edges of p̂(qj )ij that correspond to H edges, are the edges that correspond to (qj−1 ; qj ); (qj ; qj+1 ). Finally, by definition of Ĝ‘ , the path p̂(qj )ij consists only of ER edges.

Figure 24: Left: an annulus and a subgraph whose edges are paired into cycles Q (highlighted). For simplicity, a node of the graph is omitted. Its incident edges are all edges missing an endpoint. Right: the graph Ĝ‘ [ER ∪EC ]. ER edges are black, EC edges are red, and the highlighted edges constitute subgraphs Q̂ that corresponds to cycles Q. From the above claim, we can deduce: Claim 4.11. For any two paths Q ̸= Q′ defined by the given edge pairing, Q̂ and Q̂′ are edge-disjoint. Proof. Since Q; Q′ are edge-disjoint, then Q̂ and Q̂′ do not share any EC edge (each H edge has a corresponding unique EC edge, by Lemma 3.13). Thus, the only way for Q̂ and Q̂′ to not be edge-disjoint is for Q; Q′ to intersect in a node in H. That is because, if all their nodes are different, their corresponding face-parts in Ĝ‘ are vertex disjoint by Lemma 3.6. I.e., the subpaths of those face-parts with some EC edges constitute Q̂; Q̂′ , and since none of them are shared, then Q̂; Q̂′ are vertex-disjoint. Therefore, assume Q; Q′ intersect in nodes, and let q be such an arbitrary node. Note, the pair of edges in Q and the pair of edges in Q′ that are incident to q are disjoint (by definition of edge pairing, Definition 4.4). Then, by Lemma 4.9, the subpath of p̂(q) corresponding to the two edges of q in Q and the subpath of p̂(q) corresponding to the two edges of q in Q′ are edge disjoint, and if they intersect it is only in their endpoints. Now we to use the above claims in order to perform computations on the subgraphs Q̂ of Ĝ‘ , which will simulate computations on the paths Q defined by the given edge-pairing in (subgraphs H of) annuli of level ‘. We are able to perform computations in parallel on the subgraphs Q̂ despite them being (only)

46

edge-disjoint in Ĝ‘ . However, we show next that by a small change to Ĝ‘ , resulting in a graph denoted Ĝ‘′ , we make Q̂; Q̂′ vertex-disjoint. Which is then used to consistently orient the paths Q. The graph Ĝ‘′ . We focus on a single annulus A and a single node q ∈ H, and explain the change we do on Ĝ‘ . We split p̂(q) so that all p̂(q)i become vertex-disjoint. To do so, for all i, a shared endpoint to p̂(q)i and p̂(q)i+1 in Ĝ‘ gets expanded into two vertices, one that is defined to be in p̂(q)i and the other to be in p̂(q)i+1 .

(a)

(b)

(c)

Figure 25: (a) The graph Ĝ‘′ . (b) The graph Ĝ‘′ with only components Q̂ that correspond to paths Q obtained from the edge pairing. Note that they are vertex-disjoint. (c) The cycles Q after contracting ER edges of subgraphs Q̂. Note, each cycle Q corresponds to the EC edges of a certain component Q̂, and to a cycle Q (see Figure 23) We describe the change on Ĝ‘ formally (recall the definition of Ĝ‘ in Section 3.1). If p̂(q)i ; p̂(q)i+1 do not share a vertex, then they already are vertex-disjoint and are taken care of. So in the rest of the proof we assume they share an endpoint (that is the only way they can intersect with vertices by Lemma 4.9). Such a vertex connects the last edge of p̂(q)i with the first edge of p̂(q)i+1 . Those edges are ER edges (p̂(q) consists of ER edges by definition of Ĝ‘ ). Concretely, the ER copy of last(q)i intersects the ER copy of f ir st(q)i+1 with a vertex; where, last(q)i is the second edge in the i’th paired edges of q in H. Analogously, f ir st(q)i+1 is the first edge of the i +1’th paired edges of q in H. The vertex that is shared to last(q)i and f ir st(q)i+1 is a vertex of the type vk ∈ D(v ) for some v ∈ G, as those are the only vertices that are incident to two ER edges (by Section 3.1). Then, expanding vk to two vertices, one for each of p̂(q)i ; p̂(q)i+1 , makes them vertex disjoint. See Figure 25 for Ĝ‘′ , and Figure 23 for Ĝ‘ and the paths Q. Concretely, aside from the ER edges corresponding to last(q)i ; f ir st(q)i+1 , vk is also incident to ES edges, and to up to two EC edges. One of the EC edges simulates last(q)i and the other simulates f ir st(q)i+1 . Note, either EC edge may or may not be incident to vk (by Section 3.1). In particular, an EC edge is incident to a copy of an arbitrary endpoint of its corresponding primal edge. E.g. if last(q)i maps to the primal edge (u; v ), then the EC copy of last(q)i may be incident to some copy uj of u. Formally, the simple change we perform to make p̂(q)i ; p̂(q)i+1 vertex disjoint is on vk : Expand the vertex vk into two vertices vk0 ; vk1 , where vk0 is incident to the ER ; EC edges of vk that map to last(q)i , and similarly, vk1 is incident to EC ; ER edges of vk that map to f ir st(q)i+1 . ES edges that were incident to vk get incident to an arbitrary vertex of the two. Finally, we connect the newly created vertices with an ES edge (vk0 ; vk1 ) to keep the graph connected with small diameter (contracting this edge reverses the change that we just did on vk ). 47

Note, changes related to EC ; ES edges incident to all copies vk ∈ D(v ) of v ∈ G can be simulated locally by v , because those types of edges connect only copies of v itself in Ĝ‘ . The change on ER edges can be coordinated in one round of communication on G with their other (primal) endpoints. That is because v is a neighbor of the other endpoints in G of (edges corresponding to) ER edges incident to v ’s copies (by definition of Ĝ‘ , Section 3.1). We do this change on Ĝ‘ for all p̂(q)i ; p̂(q)i+1 , and for all nodes q of level ‘ in one round of communication on G. Note, the only knowledge required is, for vk to know that it is a shared endpoint of p̂(q)i ; p̂(q)i+1 , which can be easily deduced by the numbers assigned to its incident ER edges that are given as input. That is, vk checks if one of those ER edges is assigned an odd number and the other is assigned its successor (then those edges belong to different paths p̂(q)i ; p̂(q)i+1 ). Properties of Ĝ‘′ . Claim 4.12. Ĝ‘′ is a planar graph of diameter O(D), and a CONGEST round can be simulated in it within O(1) rounds on G. Proof. Note first that adding the new ES edges (vk0 ; vk1 ) keeps Ĝ‘′ connected of twice the diameter of Ĝ‘ at most, which remains O(D) (see Lemma 3.4). In addition, since the communication on ES ; EC edges can be simulated locally, then the only edges that need to simulated are ER edges whose number did not change, hence, like Ĝ‘ , an edge of G simulates at most four ER edges (see Lemma 3.16), and CONGEST round on Ĝ‘′ is simulated within O(1) rounds on G. Obviously, expanding a vertex as we do does not violate planarity. Remark 4.13. Note that there is a bijection between edges of Ĝ‘ [ER ∪ EC ] and edges of Ĝ‘′ [ER ∪ EC ]. Thus, we abuse notation and refer to a subgraph of Ĝ‘′ [ER ∪ EC ] by its corresponding subgraph of Ĝ‘ [ER ∪ EC ]. E.g. we may refer to Q̂, or p̂(q)i in Ĝ‘′ [ER ∪ EC ]. Claim 4.14. Let Q be any path defined by the given edge pairing in any subgraph H of any level ‘ annulus, then: 1. The paths p̂(q)i ; p̂(q ′ )k (as defined by Lemma 4.9) are vertex disjoint in Ĝ‘′ [ER ∪ EC ] for any two nodes q; q ′ ∈ H, (except when q = q ′ and i = k). In particular, any two paths Q′ ̸= Q defined by the given edge pairing, the graphs Q̂; Q̂′ in Ĝ‘′ [ER ∪ EC ] are vertex-disjoint. 2. The subgraph Q̂ of Ĝ‘′ is connected, and has the same structure as in Claim 4.11. Proof. The first property, follows by the fact that p̂(q)i ; p̂(q ′ )k are vertex-disjoint in Ĝ‘ [ER ∪ EC ] by Lemma 3.6 if q ̸= q ′ . Otherwise, q = q ′ and i ̸= k, thus, by Claim 4.9, p̂(q)i ; p̂(q)k are edge disjoint. Then, the property follows by the change we do on Ĝ‘ . I.e., the fact that each vertex v ∈ p̂(q)i ∩ p̂(q)k in Ĝ‘ was split into two vertices, one in p̂(q)i and the other in p̂(q)k . The proof of Q̂; Q̂′ for Q ̸= Q′ being vertex-disjoint follows. As by Claim 4.11, Q̂; Q̂′ in Ĝ‘ consist of distinct EC edges and distinct paths p̂(q)i . Then, since Q̂; Q̂′ are edge disjoint in Ĝ‘ , they cannot overlap in EC edges. I.e., for them to overlap in vertices they must overlap in p̂(q)i ⊆ Q and p̂(q ′ )k ⊆ Q′ , but we just proved that this is not possible for p̂(q)i ̸= p̂(q ′ )k in Ĝ‘′ . Note, p̂(q)i ̸= p̂(q ′ )k because each corresponds to a pair of edges in Q; Q′ and Q; Q′ are edge-disjoint (edge pairings produce edge-disjoint paths). The second property is correct in Ĝ‘ [ER ∪ EC ] by Claim 4.10 (where Q̂ was defined). The change we perform on Ĝ‘ to get Ĝ‘′ only expands some vertices of Q̂, but does not apply change the structure of Q̂; in the sense that any edge in Ĝ‘ has exactly one corresponding edge in Ĝ‘′ (Remark 4.13), s.t., an edge in Ĝ‘ belongs to Q̂ iff its corresponding edge in Ĝ‘′ also belongs to Q̂. In particular, this is correct for EC ; ER edges by definition of Ĝ‘′ . I.e., when we expand a vertex in Ĝ‘ that belongs to Q̂, its copy in Ĝ‘′ that belongs toQ̂ gets incident to all edges that belonged to Q̂ in Ĝ‘ . 48

Orienting the paths. The above claim implies that orienting the path Q in H can be easily simulated by computations on Q̂ in Ĝ‘′ . That is, the first property (by definition of Q̂ as in Claim 4.11) states that there is a 1-1 mapping between EC edges in Q̂ and edges of H in Q. Thus, orienting those edges consistently in Q̂ is sufficient. In addition, the second property allows to compute such an orientation on all subgraphs Q̂ simultaneously. Concretely, we prove a structural property related to Q̂, which then would be used to compute the desired orientation. Claim 4.15. Contracting ER edges of Q̂ in Ĝ‘′ results in a minor of it, denoted Q. Such that, Q contains all EC edges of Q̂, and only them. Moreover, Q is a path (cycle) and has the exact same topology as Q (see Figure 25). Proof. the proof follows from Claim 4.14 above. I.e., by the second item of the claim, the path Q = q1 ; q2 ; : : : corresponds to a connected subgraph Q̂ of Ĝ‘′ [ER ∪EC ], where Q̂ has a structure as in Claim 4.11. In particular Q̂ is the union of: the (ER ) subpath p̂(q1 )i1 of p̂(q1 ), the EC edge mapping to edge (q1 ; q2 ), the (ER ) subpath p̂(q2 )i2 of p̂(q2 ), the EC edge mapping to (q2 ; q3 ), and so on. Then, by the first item of Claim 4.14, we have that p̂(qj )ij s are vertex disjoint. Note, these are exactly the components whose edges are contracted in Q̂ to obtain Q. Henceforth, Q is exactly the path consisting of: the EC edge mapping to edge (q1 ; q2 ), the EC edge mapping to (q2 ; q3 ), and so on. Henceforth, to orient edges of paths Q in H, all we have to show is that this contraction can be performed (distributively) to obtain the paths Q. Then, to orient all paths Q consistently and show that this indeed can be translated to an orientation of Q in H (i.e., edges of H learn their orientation). Orienting the edges. We focus on orienting the EC edges of Q̂ in Ĝ‘′ . Afterwards we explain why we can parallelize this to all paths and all annuli of level ‘. We will work in the minor-aggregation model in Ĝ‘′ this time. First, all ER edges inside subgraphs Q̂ contract themselves (which is allowed by the model), producing the paths Q. Note those ER edges know themselves, as their endpoints in G that simulate them know this information about them because they simulate their vertex copies on paths p̂(q)j . We then orient all edges of Q, using a minor-aggregation procedure that runs in Õ(1) rounds and orients edges towards an elected root of Q (e.g. procedure of orienting a tree Lemma 5.2 from the next section). We elaborate. If Q is a path then it is also a tree and this can be achieved if we elect one of its endpoints as a root. Otherwise, Q is a cycle and the elected node to be a root can omit one of its incident edges, defining a spanning path of Q̂ rooted with an endpoint, on which the lemma can be used. Finally, leader election for Q can be done easily: If Q is a path then one of its endpoints informs all nodes of Q with this information and the maximal ID endpoint is elected. If Q is a cycle, then a root is elected by computing the maximal ID of a node in Q. Each of both tasks can be performed in one minor-aggregation round by contracting Q to a single node, which then performs a consensus step to detect whether Q is a path (has endpoints), and to compute the maximum ID of nodes (or endpoints) of Q. Correspondence to H. Note, by Claim 4.15, there is a bijection between edges of Q to edges of Q and both paths has the exact topology. Obviously, the consistent orientation computed for Q of implies an consistent orientation for Q. Thus, it remains to explain how the computed orientation to Q is leaned by the edges of Q in H. Concretely, by Claim 4.15 there is a bijection between edges of Q to EC edges of Q̂, which is known to endpoints of EC edges in Ĝ‘′ . In addition, recall (Remark 4.13), there is a bijection between the EC edges of Q̂ in Ĝ‘′ and EC edges of Q̂ in Ĝ‘ . Henceforth, since an H edge is simulated by its corresponding EC edge in Ĝ‘ , then the orientation of an EC edge (vi ; vi+1 ) from vi to vi+1 in Ĝ‘ is considered (by vi ; vi+1 ) as orienting the edge’s counterpart in H from g to f where vi ∈ p̂(g ) and vi+1 ∈ p̂(f ). This is enough as these are the vertices that simulate the edge (g ; f ) in H. I.e., edges in H know their direction. 49

Simulation. The reason we can simulate a round of the minor aggregation model on Q̂ in Ĝ‘′ within nearoptimal Õ(D) rounds, is that connected subgraphs (in this case, Q̂) of planar graphs whose diameter is O(D) allow such simulation (Theorem 17 and Corollary 11 of [18]; [34, 35]). By Claim 4.12, Ĝ‘′ is such a planar graph of diameter O(D), and a CONGEST round on it is simulated by O(1) rounds on G. I.e., this simulation is possible. Finally, the parallelization to all Q̂ for all paths Q of all graphs H of level ‘, is possible by Claim 4.14. I.e., Q̂ and Q̂′ are connected (second item of the claim) and vertex disjoint for all Q ̸= Q′ (first item of the claim) in level ‘, and running a minor-aggregation algorithm in multiple connected vertex-disjoint subgraphs in parallel can be simulated within the same round complexity of running the algorithm on the input graph (Corollary 11 of [18]; [34, 35]). This concludes the proof of Lemma 4.7.

4.2

SSSP on Annuli

We explain how to put everything together in order to prove Theorem 4.1. That is, we need to explain how to combine: (1) Deactivating parallel edges, (2) Simulateing the approximate SSSP algorithm of [34] on annuli (this includes the Eulerian orientation problem), and (3) Turning the approximate SSSP algorithm of [34] into one that obeys the triangle inequality (as in Definition A.1). 1. Dealing with multi-graphs. The graph G ∗ , as well as level-‘ annuli, may be multi-graphs (i.e., have self-loops and parallel edges) and the algorithm of [34] assumes the graph is simple. To make the graph simple, we delete self-loops and parallel edges while preserving distances. I.e., we delete all edges connecting nodes f ; g except for the one with minimal weight. A simple minor-aggregation procedure that solves the problem was shown in [1]: Lemma 4.16 (Deleting parallel edges, Lemma 4.15 of [1]). There is a minor-aggregation algorithm that runs in Õ(1)-rounds on planar multi-graphs and deletes parallel edges. Upon termination, each edge is assigned a label of either "active" or "not-active". Each active edge (f ; g ) is the minimal weight edge with endpoints f ; g . We can therefore delete parallel edges and self-loops in all annuli of any given level ‘ simultaneously within Õ(D) rounds, by simulating the algorithm from Lemma 4.16 using Theorem 3.26. From now on, we assume that annuli are simple graphs. 2. Simulating the (approximate) SSSP algorithm of [34]. Next, we prove that our solution to the Eulerian orientation problem (Definition 4.2) can be used in [34]’s algorithm in order to compute (approximate) SSSP on annuli - without the approximate triangle inequality guarantee for now. In particular, one way to phrase the result of [34] is: Lemma 4.17 ([34]). There is a algorithm that works in Õ(1=›2 ) rounds and computes an (1+›) approximate SSSP tree from a given source s in any undirected graph Gv ir t with weight from the range [1; nO(1) ]. Where Gv ir t is obtained from an undirected graph G by adding Õ(1) arbitrarily-connected virtual nodes. Upon termination, each node knows its (approximate) distance from s, and each edge knows whether it is in the (approximate) SSSP tree. Each round of the algorithm is either a minor-aggregation round on G, or a call to the Eulerian orientation oracle OEuler on Gv i r t (as in Definition 4.2). Moreover, the algorithm is deterministic, if the minor-aggregation model and the oracle OEuler can be simulated deterministically. Assume all level-‘ incisions are distributively stored, and for each level-‘ annulus Ai the ID of a source node fi is known to all v ∈ G where v ∈ p(fi ) (i.e., is known to all node of the annulus Ai ). Then it is almost straightforward to compute approximate SSSP trees in all annuli of the level simultaneously. Concretely, we can split time into phases of D logc n for some constant c. Such that an even phase 2i simulates one round of the algorithm if that round is a minor-aggregation round. This simulation terminates within D logc2i n rounds on all annuli of level ‘ simultaneously by Theorem 3.26. Where c2i is 50

some constant, and c > maxi {c2i }. Similarly, an odd phase 2i + 1 simulates one round of the algorithm if that round is a call to the Eulerian orientation oracle (Definition 4.2). Note that the input of the oracle in this case is given by the algorithm and is computed by the previously simulated rounds, and its output is given in the format required by [34]. This is simply because we follow [34]’s definition of the oracle. This simulation terminates within D logc2i+1 n on all annuli of level ‘ simultaneously by Lemma 4.5. Where c2i+1 is some constant, and c is chosen to be larger than maxi {c2i+1 }. Hence, the total runtime of simulating [34]’s algorithm on all annuli of a given level is Õ(D). Note that this gives Theorem 4.1 except for the triangle inequality condition that we discuss next. 3. Approximate triangle inequality. As explained in Section 2.1 and Appendix A, we need the approximate SSSP algorithm to obey the approximate triangle inequality. This property requires that any subpath f ; : : : ; g of a (1 + ›)-approximate shortest path returned by the SSSP algorithm to be also a (1 + ›)-approximate shortest f -to-g path (see Definition A.1). Let A be any (1 + ›)-approximate SSSP algorithm that supports adding a total of Õ(1) arbitrarily connected virtual nodes to the input graph. Recently, [33] have shown a reduction that after Õ(1) executions of A (each time on a different graph that is obtained from the input-graph by adding virtual nodes and changing the edge weights) gives a (1 + › log n) approximate algorithm that obeys the triangle inequality. The reduction is implementable in the minor-aggregation model as shown in [1]. Lemma 4.18 (Theorem 5.1 of [33] and Theorem 1.3 of [1]). Let A be an r · f (›) round (1 + ›)-approximate SSSP algorithm that supports adding Õ(1) arbitrarily connected virtual nodes to the input-graph. There is a (1+›′ ) approximate SSSP algorithm A′ that obeys the approximate triangle inequality, and runs in Õ(r ·f (›′ )) rounds, where ›′ = ›= log n. Note that adding virtual nodes to the input of the SSSP algorithm of [34] is supported (see Lemma 4.17), in addition, our simulation of the minor-aggregation model supports adding Õ(1) virtual nodes to each annulus (see the end of Section 3.4). Hence, we use the above Lemma 4.18 to convert the approximate SSSP algorithm of [34] into one that, obeys the approximate triangle inequality and can be run on all annuli of a given level simultaneously. I.e., in Õ(D=›2 ) rounds, we compute (1 + ›)-approximate shortest paths tree for all annuli of any given level ‘ simultaneously, concluding Theorem 4.1.

5

Distributed Reif Implementation

In this section we wrap up the entire (distributed) implementation of Reif’s algorithm as summarized by the following Algorithm 3. In the first three lines of Algorithm 3, we need to construct G ∗ , detect nodes f ; g , find an approximate shortest f -to-g path P , and incise along P . In Line 1 we construct G ∗ (represented by Ĝ0 ) in Õ(D) rounds as in Lemma 3.17. In particular, nodes h of G ∗ are identified and assigned IDs that are known to all primal vertices on the face p(h) in G, and for each edge e ∈ G its endpoints know the IDs of the endpoints of e ∗ ∈ G ∗ . Since s (resp. t) knows the faces it participates in, then s (resp. t) chooses locally an arbitrary such face to be f (resp. g ), and broadcasts the ID of f (resp. g ) to the entire graph G in O(D) rounds using the following textbook lemma: Lemma 5.1 (Basic aggregation [29]). L For every v ∈ G let xv be an arbitrary O(log n)-bit input. Within O(D) rounds, all v ∈ G learn the result v ∈G xv of any predefined aggregate operator ⊕. Once all vertices of G know the IDs of f ; g , we have the required input format for Theorem 4.1, and we can compute a (1 + ›)-approximate SSSP tree rooted at f (Line 2) in Õ(D) rounds. After computing the tree, using Theorem 3.26 we can in Õ(D) rounds simulate the following classic Õ(1) minor-aggregation rounds procedure in order to mark the f -to-g path in the tree as P . 51

Algorithm 3: Distributed Reif Input: A D-diameter positively weighted undirected planar network G, two vertices s; t ∈ G, and a precision parameter › Result: Within Õ(D)-rounds, each vertex v ∈ G learns its incident edges in a (1 + ›)-approximate minimum st-cut Pi 1 Construct G ∗ , and detect nodes f ∈ s ∗ ; g ∈ t ∗ 2 Compute an f -to-g (1 + ›)-approximate shortest path P 3 Incise along P (results in annulus A) 4 ShortestCycle(A, 0, |P | − 1) 5 return the st-cut edges, bisection, and length of the shortest Pi found by ShortestCycle 6 Procedure ShortestCycle(A, j, k): 7 8 9 10 11 12 13 14 15 16 17 18 19

if k ≤ j + 1 then compute Pj ; Pk /* leaf annuli */ Compute a (1 + ›)-approximate shortest path Pi for i = ⌊(j + k)=2⌋ /* overlapping annuli */ for (Pa ; Pb ) ∈ {(Pj ; Pi ); (Pi ; Pk )} do if Pa ∩ Pb ̸= ∅ then Compute a (1 + ›)-approximate SSSP tree T from x ∈ Pa ∩ Pb Compute the pt0 -to-pt1 paths Pt in T for all a ≤ t ≤ b) end end /* define next level’s annuli */ Find first and last intersections pi1 ; pi2 ∈ Pi ∩ P Find the maximal subpath Pi′ of Pi , which is internally-disjoint from (copies) of P Incise Pi′ giving the annuli Al ; Ar of the next level and discard non-annuli graphs /* recursive calls (if any) */ if Al exists then ShortestCycle(Al , j, i1 ) if Ar exists then ShortestCycle(Ar , i2 , k)

Lemma 5.2 (Tree primitives). There are Õ(1) minor-aggregation rounds procedures P1 ; P2 s.t given any tree T and nodes f ; g ∈ T : P1 computes subtree sums on T w.r.t. f as the root over arbitrary Õ(1)-bit strings as an input. P2 marks the edges and nodes of the f -to-g path in T . Proof. The procedure P1 is Lemma 16 of [18], also appears in [2, 14, 17, 24, 34]. The procedure P2 exists in many works (e.g. [2, 17, 24]), however, not exactly as we state it. For completeness, we restate the proof: Simply, g ; f are assigned an input value of one. All other nodes are assigned an input value of zero. Then, compute subtree sums with P1 . Then, an edges has one endpoint of sum exactly one, and the other endpoint of sum at least one, iff the edge is on the f -to-g path. I.e., all internal nodes of the path has sum exactly one, except for the lowest common ancestor of f ; g , has a sum of two. After using the above lemma, edges of G whose duals are in P are known to their endpoints in G, and all vertices v ∈ G know for each h ∈ G ∗ s.t v ∈ p(h) whether h ∈ P . Then, with additional O(D) rounds, all vertices of G learn the (weighted) length of P : By Theorem 4.1, vertices v ∈ p(g ) know the (approximate) f -to-g distance. Thus, they broadcast it in O(D) rounds to all vertices of G. Next, we aim to enumerate P ’s endpoints from zero to |P | − 1. We use Lemma 5.2 to compute subtree sums on P as the tree of input, where the root is g and the input to all P ’s nodes is one except for f whose input is zero. The procedure terminates in Õ(D)-rounds (by the minor-aggregation simulation, 52

Theorem 3.26). After which, each vertex v ∈ G that lies on a face p(pi ) learns that this face corresponds to pi ∈ P . In order to incise along P (Line 3), we need to handle the endpoint-case edge (see Definition 2.2, Remark 3.3). For p0 (resp. p|P |−1 ), we identify a non-P edge incident to it and set it to be the endpointcase edge denoted (resp. e|P |−1 ). To find e0 , the vertex s knows the ID of p0 (since s ∈ p(p0 )) and its incident edges in p(p0 ). Moreover, s knows its incident P -edges (if any). Thus, s chooses an incident edge e0 of p(p0 ) whose dual is not on P . Note, such an edge always exists because P cannot contain all edge of the face s ∗ in G ∗ (this would contradict P being a simple path). In primal terms, the vertex s is incident to at least one edge on p(p0 ) whose dual is not on P . Then, e0 is set to be such an edge. A similar argument holds for t and e|P |−1 . Note that this is done locally in s; t. Overall, in Õ(D) rounds we have computed P and so the incision of level ‘ = 1 of T is distributively stored . Thus, using Lemma 3.17 P is incised (represented with Ĝ1 ) and this level is learnt. In addition, by Theorem 3.26 we can run minor-aggregation algorithms on it.

5.1

The Procedure ShortestCycle

We assume that level ‘−1 is constructed. That is: (1) paths that define annuli of level ‘−1 are distributively stored (Definition 3.2) and incised (meaning Ĝ‘−1 was already constructed), (2) annuli of level ‘ − 1 are known to the vertices that simulate them in Ĝ‘−1 (Lemma 3.17), (3) for every level ‘−1 annulus A bounded by paths Pj ; Pk , the edges of Pj ; Pk knows themselves. Moreover, let j ≤ j ′ ≤ k ′ ≤ k where we aim to compute the paths Pt for j ′ ≤ t ≤ k ′ in A (and its subtree in T ), then both j ′ ; k ′ are known to all G vertices that simulate A. I.e., vertices that lie on p(h) for some node-part h ∈ A. Then (Line 8) we compute the pi0 -to-pi1 path Pi for i = ⌊(j ′ + k ′ )=2⌋ inside the annulus A. Afterwards, we prepare for the next recursion by incising Pi as in Remark 2.5 (computing the child annuli of A as in Definition 2.8). We describe this on a single annulus A. However, these steps can be applied on all annuli level ‘ − 1 simultaneously in the same round complexity (by Theorem 3.26 and Theorem 4.1). Remark 5.3. In the following we may treat nodes and edges of annuli as computational entities, when that is done then it is either to compute a part-wise aggregation over the annuli (Lemma 3.27) or to run a minor-aggregation algorithm (Section 3.4, Theorem 3.26). Annuli however are not computational entities in CONGEST, and we may only discuss CONGEST on vertices of G and Ĝ‘−1 (since CONGEST on Ĝ‘−1 can be simulated without any asymptotic overhead by Lemma 3.16). Leaf annuli (Line 7). If k ′ ≤ j ′ + 1, then we compute Pk ′ ; Pj ′ and terminate the procedure for this annulus, as it is a leaf annulus (see Definition 2.8). Both computations are done in the same manner of computing any Pi (explained next). Finally, a special treatment is required for an annulus where Pi and Pk or Pj (or both) intersect (such an annulus might have only one child or also be a leaf annulus). This is discussed later in this section. Computing Pi (Line 8). Since all nodes of the annulus A know j ′ and k ′ , they locally compute i := ⌊(j ′ + k ′ )=2⌋. After which, the two nodes pi0 and pi1 know that the SSSP computation must originate in one of them. Note, the nodes do not know which of them is pi0 and which is pi1 . However, they know that they are node-parts of pi ∈ P , because the correspondence between node-parts of ancestor annuli is known to them by Lemma 3.17. This information is sufficient: the nodes pi0 ; pi1 aggregate their IDs on A in one round of minor-aggregations to elect the one with the maximum ID to be the source of the SSSP computation. Then, using Theorem 4.1 we compute an approximate SSSP tree from pi0 (w.l.o.g). Then, using Lemma 5.2: (1) we mark the tree pi0 -to-pi1 path Pi (its nodes and edges in A know themselves), (2) the length of Pi (sum of its edge weights) is known to all vertices v ∈ G that simulate A. Note, the SSSP algorithm terminates in Õ(D) rounds on G. The subtree sums and aggregation procedures run in Õ(1) 53

minor aggregation rounds, so by Theorem 3.26 they are simulated in Õ(D) CONGEST rounds on G. To conclude, Lemma 5.4. Within Õ(D) rounds, for each non-leaf annulus A of level ‘ − 1 that aims to compute Pt for j ′ ≤ t ≤ k ′ , the edges of Pi know themselves, and its length is known to its nodes. If A is a leaf annulus edges of both Pj ′ ; Pk ′ know themselves, and their lengths are known to nodes that participate in them. Intersection of Pi and Pj ; Pk (Lines 9-14). As explained in Section 2.1 (Claim 2.3), if Pi intersects Pj at some vertex x (analogously, we handle the case that Pi ; Pk intersect) then we compute all the paths Pm 0 -to-x and for j ≤ m ≤ i in the current recursive call. All such paths Pm are the concatenation of the pm 1 x-to-pm paths. Note that each node of the annulus knows whether it is on any of the paths Pj ; Pi and Pk . Thus, a node that is in Pi ∩ Pk or Pi ∩ Pj knows itself. Then, by aggregating IDs of those nodes in one minor-aggregation round (Õ(D) round on G by Theorem 3.26), we choose the node x and an SSSP 0 ; p1 computation (within Õ(D) rounds, by Theorem 4.1) is performed from x. After that, all nodes pm m 0 ) and p(p 1 ) know the x-tofor j ≤ m ≤ i know their distance from x. I.e., in G, then vertices on p(pm m 0 and x-to-p 1 distances (respectively). Thus, copies of those vertices broadcast these two distances on pm m p̂(pm ) in Ĝ0 , to compute and learn length of Pm . This is done in Õ(D) rounds by Corollary 3.23. Finally, the length of the minimal Pm is computed by one minor-aggregation round on A (Õ(D) round on G, by Theorem 3.26). That path is then marked in x’s SSSP tree in Õ(D) rounds (by Lemma 5.2, Theorem 3.26). Lemma 5.5. within Õ(D) rounds, for each annulus A defined by Pj ; Pk : If Pi intersects Pj (resp. Pk ), then all nodes on the minimal-weight Pm for j ≤ m ≤ i (resp. i ≤ m ≤ k), learn that and learn Pm ’s weight. Intersection of Pi and P (Lines 15-16). We have two tasks. First, we find the first node pi1 and the last node pi2 of P whose node-parts participate in Pi . Then, in the recursion (by Claim 2.4) we can discard Pt for all i1 < t < i2 . Second, we need to find the maximal subpath Pi′ of Pi that is internally disjoint from P because that is the path that needs to be incised in the next step of the algorithm (by Remark 2.5 of incising Pi ). Finding i1 ; i2 . We prove the following lemma. Lemma 5.6. Within Õ(D) rounds, for all annuli A of level ‘ − 1: All nodes of A that correspond to pt (and the vertices of G simulating them) learn that the length of Pt is not the minimal (i.e., is to an identity element) for i1 < t < i2 where i1 (resp. i2 ) is the first (last) node of P ∩ Pi in P . Moreover, all nodes of A know i1 ; i2 . The indices i1 , i2 are found as follows. Note, the pj -to-pk subpath P ′ of P has two copies in A (as a result of incising P ), s.t. an endpoint (say pi0 ) of Pi lies on the first copy of P ′ (denoted P ′0 ) and the second endpoint pi1 of Pi lies on the second copy of P ′ (denoted P ′1 ). Moreover, those copies of P ′ are node and edge disjoint (as a result of incising P at first). Thus, we identify nodes on P ′0 and P ′1 . Then, we set i1 as the smallest index s.t. pi01 ∈ Pi or pi11 ∈ Pi , and i2 is the largest index s.t. pi02 ∈ Pi or pi12 ∈ Pi . To do so, we compute a minimum and a maximum aggregate operator on each of the paths P ′0 ; P ′1 , where the input of a node pt0 ∈ P ′ 0 (resp. pt1 ∈ P ′ 1) is t if it participates in Pi and an identity element otherwise. This gives the first and last intersection between P ′0 ; P ′ 01 and Pi . Then, via aggregating the results on A, we find i1 and i2 (all nodes in A learn those indices). Those nodes know themselves because they know to what nodes of P do they correspond. The aggregations are made using Lemma 3.27 in Õ(D) rounds. It remains to show how to identify the paths P ′0 and P ′1 (the copies of P in A). We perform the following O(1) minor-aggregation round procedure (by Theorem 3.26, this is Õ(D) rounds on G). Simply, each edge of A that maps to an edge of P contracts itself (which is allowed by the model). This results in two distinct (super-)nodes, one corresponding to P ′0 , and the other to P ′1 . Since P ′0 ; P ′1 are nodedisjoint, the resulting super-nodes are indeed distinct. Each of those super nodes chooses an ID, say Id of 0 for P ′0 (analogously for P ′1 ). Simply p 0 informs all nodes on P ′0 that they are on P ′ the maximal node pm 0 i 54

and similarly for pi1 and P ′1 . Then, we rewind the contraction (return to annulus A), and we get that all vertices on P ′0 know a shared ID for P ′0 (similarly for P ′1 ), and that P ′0 ; P ′1 have different IDs (as nodes have distinct IDs, Lemma 3.17). Finding Pi′ . We prove the following lemma Lemma 5.7. For all annuli of level ‘ − 1 simultaneously, the maximal subpath Pi′ of Pi that is internally disjoint from (copies of) P can be found within Õ(D) rounds. For detecting Pi′ , we simply detect the last node px0 of P 0 in Pi , and the first py1 node of P ′1 in Pi . Then, node on the px0 -to-py1 subpath of Pi learn that this is in fact the path Pi′ . First we root Pi with its endpoint that belongs to P ′0 , then px0 is in fact the deepest node of P ′0 in (the rooted) Pi . To find this node we perform a subtree sum computation on Pi , where all nodes of P ′0 in Pi have an input of one. Hence, px0 is simply the node of P ′0 whose subtree sum is one. Next, we omit the prefix of Pi that contains higher nodes than px0 . This can be done locally. I.e., each edge whose both endpoints got a subtree sum of at least one, omit themselves. Now, we are kept with a subpath Q of Pi whose one endpoint is px0 (and is the only node in Q ∩ P ′0 ). However, Q may contain many nodes of P ′1 , and it remains to find py1 . We do that the same way we found px0 . That is, root Q with its P ′1 endpoint, compute subtree sums, the deepest node of P ′1 in Q is py1 . After that, we omit the prefix of nodes higher than py1 , which results in Pi′ . Defining next level’s annuli (Line 17). Before the recursive calls. we need to incise on Pi′ and define the next level’s annuli. We abuse notation and denote Pi′ by Pi . We incise edges of Pi that were not incised previously (in case it intersects Pk or Pj ). After the incision, some resulting subgraphs may not be annuli (by Corollary 2.11, see also a discussion at the end of Section 3.3). In particular, each node may have many node-parts in a level, the complementing parts are not in any annulus). Thus, we need to detect those subgraphs (if any). Once a node-part leanrs it is in such a graph, it stops its algorithm. I.e., vertices of Ĝ‘ that simulate such nodes stop simulating them, and are used exclusively for communication. Claim 5.8. A subgraph resulting from incising Pi is not an annulus of level ‘ iff it contains (at least) a non-Pi edge in Pk (resp. Pj ) that is incident to some node f ∈ Pi ∩ Pk (resp. Pi ∩ Pj ). We refer to such edges as bad. Proof. We prove for Pk (an analogous proof holds for Pj ). This case is actually implicit in Section 2.1, where we define the graphs that are discarded from being annuli of the next level. We explain. Let A′ be the subgraph of A bounded by Pi ; Pk . A′ is an annulus of the next level, iff Pi ∩ Pk is empty. Otherwise, after incising Pi , A′ can be (and might) broken into subgraphs, each associated with one maximal subpath of Pk that is internally-disjoint from Pi (such a subpath has at least one and possibly both it endpoints in Pi ). I.e., each subgraph that is not an annulus of the next level must have a node (an endpoint of its associated Pk subpath) that has an incident edge of Pk and another incident edge of Pi . In the other direction, if such a (bad) edge exists, then Pi and Pk intersect and A′ results from the incision shall be discarded. Note that because we chose to not incise an edge twice, then edges in Pi ∩ Pk are not duplicated in ′ A after the incision of Pi (that is why A′ might consist of many disconnected graphs, we deal with all of

them). The annulus defined by Pi ; Pj remains connected by Pi (if Pi ; Pj do not intersect, otherwise, it gets discarded). By the above Claim 5.8, to identify subgraphs that are not annuli in the next level, we can identify bad edges instead (and discard a subgraph if it contains a bad edge). We now show how to identify bad edges in Pk (the case of Pj is analogous). First, nodes of A mark themselves if they are in Pi ∩ Pk . Then, edges of Pk mark themselves if one of their endpoints is marked. We implement this in two minoraggregation rounds. In the first, contraction and consensus steps are skipped. In the aggregation step, 55

edges choose one of two values {Pi }; {Pk } indicating if they are in Pi ; Pk or an identity element (if the edge is in neither or in both). Then, the aggregate operator that a node computes over its incident edges checks if there are at least two incident edges s.t. one is in Pk and one is in Pi . If so, the node marks itself. After the aggregation terminates, edges learn whether one of their endpoints is marked in an additional minor-aggregation round and possibly marks itself as a bad edge accordingly (if it is in Pk or Pj and has a marked endpoint). Finally, we incise Pi and construct the resulting subgraphs (represented by Ĝ‘ ) as in Section 3. Then, each edge in each resulting subgraph chooses a value of one if its corresponding edge in A bad (and zero otherwise). This is known to the edges of the resulting subgraphs because the correspondence between ancestor annuli and A is known to A’s edges and nodes by the vertices that simulate them. I.e., endpoints u; v of edge e ∈ G simulate all of e’s duplicates in all levels, thus, any information about any duplicate of e in any previous level is known to u; v , and thus, is known to the edge’s duplicates in A. Then, an aggregation (OR operator) is computed on each subgraph, detecting whether there exists an edge that chose one as an input. Finally, each (node in a) graph in which a bad edge was detected, terminates its algorithm.

5.2

Finding the Minimum st-cut and Flow Value

Recall (Section 2) that the minimum st-cut consists of the edges of G whose duals participate in the cycle of G ∗ that corresponds to the Pm (0 ≤ m ≤ |P |−1) of minimal length. We first discuss the approximation guarantees regarding the value of the maximum st-flow and minimum st-cut. Then discuss finding the desired path Pm that admits this. Finally, we discuss a minor problem and its solution, concerning Pm is an approximate path. Approximation guarantee and flow value. Since, the dependency on › is quadratic in the SSSP algorithm that we use Theorem 4.1 to find Pm , then if › is set to Õ(1)−1 , we get a 1 + o(1) approximation to the minimum st-cut in Õ(D) rounds (shortly we explain how to find Pm ). In addition, a 1 − o(1) approximation to the maximum st-flow value is obtained simply by dividing the value of the minimum st-cut by (1 + ›). This gives the flow value within a multiplicative error in the range [1=(1 + ›); 1]. Note however, another form of 1=(1 + ›) is 1=(1 − (−›)), which (when |›| < 1) is 1 − › + ›2 − ›3 : : : by the geometric series expansion. Obviously, this is at least 1 − ›. Hence the multiplicative error is in the range [1 − ›; 1] as promised. Finding Pm (cut edges, and bisection). While in Algorithm 1 and Algorithm 2 the procedure ShortestCycle only returns this length, in Algorithm 3 we wish (Line 5) to also compute the st-cut edges and the corresponding bisection. To find the minimal length Pm , note first that leaf annuli divide the interval P into intervals. Each interval either maps to a specific leaf annulus (defined by paths Pi ; Pi+1 and handled in Lemma 5.4) or to an interval [j; k] for which the minimal Pm for all m ∈ [j; k] was computed in a non-recursive manner (and was handled in Lemmas 5.5 and 5.6). Henceforth, the nodes of every Pi and its length are known to vertices of G that simulate them. To find the minimal length Pm , each vertex in G aggregates the minimal length of a path Pi that it knows along with the index i. The aggregation terminates in O(D) rounds by Lemma 5.1. To mark the st-cut edges in G and learn the corresponding bisection we do the following. First, each vertex of G knows for each incident edge whether it (its dual) participates in Pm or not. Thus, each vertex marks such incident edges, and the approximate minimum st-cut is distributively stored. To compute the bisection, we simply omit the st-cut edges from G and run a connectivity algorithm in Õ(D) rounds [14, 17] (the omitted edges still exist in the communication graph, but not in the input graph). Then, two connected components are detected. The one that contains s is set to S and the other to V \ S. Vertices can learn their side after s and t broadcast their component’s ID in O(D) rounds to all vertices of G (using Lemma 5.1). 56

Dealing with non-simple Pm . Finally, there is a slight issue with this description. In particular Pm might not correspond to a simple cycle in G ∗ , because it is an approximate path. I.e., it is simple in the annulus it was found in, but it may use copies of the same edge of P in that annulus. To deal with this, we force Pm to correspond to a simple cycle by removing such overlaps. That is, we compose a new cycle in G ∗ , whose weight is larger than that of Pm only by a (1 + ›) (by Lemma 2.7, Appendix A) as follows: Let Pm′ be the maximal subpath of Pm that is internally disjoint from (copies of) P (as in Lemma 5.7). Pm′ then corresponds to a simple path of G ∗ whose endpoints px ; py ∈ P . We take the union of Pm′ and the px -to-py subpath of P to be our cycle. The path Pm′ can be found by Lemma 5.7 within Õ(D) rounds, while the px -to-py subpath of P can be marked by Lemma 5.2 (in Õ(D) rounds, by Theorem 3.26).

References [1] Yaseen Abd-Elhaleem, Michal Dory, Merav Parter, and Oren Weimann. Distributed maximum flow in planar graphs. In 44th PODC, pages 278–286, 2025. [2] Yaseen Abd-Elhaleem, Michal Dory, and Oren Weimann. A simple distributed deterministic planar separator. In 33rd SIROCCO, pages 1–20, 2026. [3] Mikhail J. Atallah and Uzi Vishkin. Finding euler tours in parallel. J. Comput. Syst. Sci., 29(3):330–337, 1984. [4] Glencora Borradaile and Philip N. Klein. An O(n log n) algorithm for maximum st-flow in a directed planar graph. J. ACM, 56(2):9:1–9:30, 2009. [5] Edson Cáceres, Narsingh Deo, Shivakumar Sastry, and Jayme Luiz Szwarcfiter. On finding euler tours in parallel. Parallel Process. Lett., 3:223–231, 1993. [6] Yi-Jun Chang, Oren Hecht, Dean Leitersdorf, and Philipp Schneider. Universally optimal information dissemination and shortest paths in the HYBRID distributed model. In 43rd PODC, pages 380–390, 2024. [7] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 63rd FOCS, pages 612– 623, 2022. [8] Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32–53, 1986. [9] Tijn de Vos. Minimum cost flow in the CONGEST model. In 30th SIROCCO, pages 406–426, 2023. [10] Michael Elkin. Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In 36th STOC, pages 331–340, 2004. [11] L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399–404, 1956. [12] Juan A. Garay, Shay Kutten, and David Peleg. A sublinear time distributed algorithm for minimumweight spanning trees. SIAM J. Comput., 27(1):302–316, 1998. [13] Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks I: planar embedding. In 34th PODC, pages 29–38, 2016. 57

[14] Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks II: lowcongestion shortcuts, mst, and min-cut. In 27th SODA, pages 202–219, 2016. [15] Mohsen Ghaffari and Bernhard Haeupler. Low-congestion shortcuts for graphs excluding dense minors. In 40th PODC, pages 213–221, 2021. [16] Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz Patt-Shamir. Near-optimal distributed maximum flow. In 33rd PODC, pages 81–90, 2015. [17] Mohsen Ghaffari and Merav Parter. Near-Optimal Distributed DFS in Planar Graphs. In 31st DISC, pages 21:1–21:16, 2017. [18] Mohsen Ghaffari and Goran Zuzic. Universally-optimal distributed exact min-cut. In 40th PODC, pages 281–291, 2022. [19] Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Low-congestion shortcuts without embedding. Distributed Comput., 34(1):79–90, 2021. [20] Theodore E. Harris and Frank S. Ross. Fundamentals of a method for evaluating rail net capacities. Memorandum RM-1573, 1955. [21] Refael Hassin. Maximum flow in (s, t) planar networks. Inf. Process. Lett., 13(3):107, 1981. [22] M. R. Henzinger, P. N. Klein, S. Rao, and S. Subramanian. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences, 55(1):3–23, 1997. [23] Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In 43rd STOC, pages 313–322, 2011. [24] Benjamin Jauregui, Pedro Montealegre, and Ivan Rapaport. Deterministic distributed DFS via cycle separators in planar graphs. In 44th PODC, pages 268–277, 2025. [25] Philip Klein and Shay Mozes. Optimization Algorithms for Planar Graphs. https://planarity.org. Book draft. [26] Shay Kutten and David Peleg. Fast distributed construction of small k-dominating sets and applications. J. Algorithms, 28(1):40–66, 1998. [27] Jason Li and Merav Parter. Planar diameter via metric compression. In 51st STOC, pages 152–163, 2019. [28] Merav Parter. Distributed planar reachability in nearly optimal time. In 34th DISC, pages 38:1–38:17, 2020. [29] David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000. [30] David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of distributed MST construction. In 40th FOCS, pages 253–261, 1999. [31] John H. Reif. Minimum s-t cut of a planar undirected network in O(n log2 n) time. SIAM J. Comput., 12(1):71–81, 1983.

58

[32] Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. In 43rd STOC, pages 363–372, 2011. r Bernhard Haeupler ⃝ r Anders Martinsson ⃝ r Christoph Grunau ⃝ r Goran Zuzic. [33] Václav Rozhon ⃝ Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances. In 55th STOC, pages 321–334, 2023. r Christoph Grunau ⃝ r Bernhard Haeupler ⃝ r Goran Zuzic ⃝ r Jason Li. Undirected [34] Václav Rozhon ⃝ (1+›)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms. In 54th STOC, pages 478–487, 2022. r Gramoz Goranci ⃝ r Mingquan Ye ⃝ r Bernhard Haeupler ⃝ r Xiaorui Sun. Universally[35] Goran Zuzic ⃝ optimal distributed shortest paths and transshipment via graph-based l1 -oblivious routing. In 33rd SODA, pages 2549–2579, 2022. [36] Shankar M. Venkatesan. Algorithms for network flows. Ph.D. thesis, Pennsylvania State University, 1983.

A

Deferred Proof from Section 2.1

A.1

Proof of Lemma 2.6

Lemma 2.6. Every edge of G ∗ is incised at most once in our implementation of Reif. Proof. We prove by induction. Obviously, the claim holds for level zero (the graph G ∗ ) where no edge is incised. In addition, from the definition of an incision on P (Definition 2.2), the claim is immediate for level one (G ∗ after incising P ). I.e., only edges of G ∗ in P are incised (once). Let e ∈ G ∗ s.t. it was incised at most once until level ‘ − 1, we show that the claim holds for e in level ‘. Let A be defined by paths Pk ; Pj , and assume k + 1 < j; otherwise k + 1 = j and A is a leaf annulus (and the claim holds by the hypothesis). I.e, we incise on Pi (i = ⌊(j + k)=2⌋) to define A’s child annuli in level ‘. We examine two cases related to e and A. Namely, if e is in A and was not incised before, then: It is either in Pi and gets incised, or it is not and does not get incised. In either case e is incised at most once until level ‘ (inclusive). Otherwise, e was incised (only) once before, and a duplicate of it is in A. If e’s duplicate is not in Pi , then nothing changes and the claim still holds. Otherwise, e’s duplicate is in Pi . Since e was incised before, then its duplicate in A must be in P , Pi or Pj . In this case, (the duplicate of) e is not incised, because common subpaths of Pi and P , Pk or Pj do not get incised (Remark 2.5).

A.2

Proof of Lemma 2.7

Lemma 2.7 (Approximate Reif). Using a (1 + ›)-approximate SSSP algorithm that obeys the approximate triangle inequality, setting › = O(›′ = log n) ensures that all Pi s do not cross and are (1 + ›′ )-approximate shortest pi0 -to-pi1 paths. The proof of Lemma 2.7 relies on the fact that any subpath Pi [u; v ] of an approximate path Pi returned by the SSSP algorithm is also an approximation (with the same approximation ratio) to the u-to-v shortest path, if the SSSP algorithm obeys the approximate triangle inequality:

59

Definition A.1 (Approximate triangle inequality). Let s be any source vertex. Any ¸-multiplicative approximate distances ds¸ (·) from s obey the approximate triangle inequality if for any two vertices u; v we are guaranteed that: |ds¸ (v ) − ds¸ (u)| ≤ ¸ · d(u; v ) We begin the proof of Lemma 2.7 with the following claim. Claim A.2. Let Pi be a (1 + ›)-approximate shortest pi0 -to-pi1 path that obeys the approximate triangle inequality. For j ̸= i, there is a (1 + ‹)(1 + ›) approximate shortest pj0 -to-pj1 path Pj that does not cross Pi , where ‹; › > 0 are arbitrary constants. Proof. Let Pj′ be a (1 + ‹)-approximate shortest pj0 -to-pj1 path. Assume w.l.o.g that pj0 and pj1 are in the interior of Pi . If Pj′ crosses Pi , then it must cross it an even number of times, say 2‘. If ‘ = 0 then Pj′ does not cross Pi and we are done. Otherwise, there is an ordered (by distance to pi0 ) set of vertices (v0 ; v1 ; : : : ; v2‘−1 ) in which Pj′ crosses Pi , such that, the Pj′ [v2k−1 ; v2k ] subpaths are enclosed by Pi , and the Pj′ [v2k ; v2k+1 ] subpaths are not enclosed by Pi . Meanwhile, since Pi obeys the approximate triangle inequality, the Pi [v2k ; v2k+1 ] subpaths are (1 + ›) approximation to the shortest v2k -to-v2k+1 paths. I.e., denote by w (Q) the length of a path Q, then, by the approximate triangle inequality: w (Pi [v2k ; v2k+1 ]) = dp1+› (v2k+1 ) − dp1+› (v2k+1 ) ≤ (1 + ›)d(v2k ; v2k+1 ) i i Thus, we obtain Pj by replacing the Pj′ [v2k ; v2k+1 ] subpaths with Pi [v2k ; v2k+1 ], as follows:

w (Pj ) =

≤

≤

‘−1 X k=0 ‘−1 X

w (Pi [v2k ; v2k+1 ]) +

‘−1 X

w (Pj′ [v2k−1 ; v2k ])

k=1

(1 + ›)w (Pj′ [v2k ; v2k+1 ]) +

k=0 2‘−2 X

‘−1 X

w (Pj′ [v2k−1 ; v2k ])

k=1

(1 + ›)w (Pj′ [vk ; vk+1 ]) = (1 + ›)w (Pj′ )

k=0

≤ (1 + ›)(1 + ‹)d(pj0 ; pj1 ): The proof of Lemma 2.7 follows easily from the above claim, by induction on the recursion level i and using ‹ = ›. In the base case, i = 1. For the same reasoning of Claim A.2, in the first recursion level, we can compute P to be a 1 + › approximate shortest path, and then ensure that P|P |=2 is a (1 + ›)2 approximation. In level 1 < i ≤ O(log n), applying Claim A.2 to compute all paths of level i guarantees an approximation equivalent to the approximation guarantee of level i − 1 with a multiplicative factor of (1 + ‹). By the inductive assumption, the level i shortest paths constitute an (1 + ›)(i+1) approximation. Since there are O(log n) recursion levels, all we need to show is that for each constant c2 , there exists a constant c1 , s.t., (1 + ›)O(log n) = (1 + c1 ›′ = log n)(c2 log n) is at most 1 + ›′ . Choosing c1 < 0:5=c2 , we get that for all 0 < ›′ < 1: ′

′

(1 + c1 ›′ = log n)(c2 log n) ≤ e c1 c2 › < e 0:5› ≤ 1 + ›′ : ′

The last inequality is true since: (1) 1 + ›′ is linear in ›′ , while e 0:5› is convex. (2) For ›′ = 0 both functions √ ′ are equal, and for ›′ = 1 we have that e 0:5› = e < 2 = 1 + ›′ . This concludes the proof of Lemma 2.7.

60

Related documents

• Degenerating orbits of the Longest Edge Bisection process#986474
• Long-step strategies in interior-point primal-dual methods#429967
• Distributed Near-Equitable Coloring in the LOCAL Model#1062091
• Fractal antenna inspired EMP power grid mitigation device placement through cycle removal using graph theory#454240
• High-order energy-stable BGN parametric finite element methods for geometric flows#799132