In the real world, planar networks commonly model utility distribution networks such as gas pipelines, water distribution, city's electric grid, and transportation networks like railways and highways. Evaluating the vulnerability of these networks is crucial on several point of view: in a military context in order to prevent terrorist attack, or for maintenance to prevent wear and tear or natural disasters from inflicting extremely severe damage. This work aims to evaluate the vulnerability of undirected planar network studying the decrease of maximum -flow when an edge or a vertex is removed, that is, we propose algorithms for computing the max flow vitality of edges and vertices. Our algorithms are applied to real world scenarios, and we prove that high vitality values are well approximated in time close to the time currently required to compute -max flow ( log log ). All our algorithms work in () space.
The design and construction of networks are important topics in today’s world. Establishing the
vulnerability of a network is crucial to prevent severe damage. There is no universal definition
of vulnerability, as the same network can be assessed using diferent metrics, resulting in it
being deemed vulnerable or robust depending on the metric used [
In this paper, we focus on undirected planar networks and study vulnerability with respect to the maximum flow. It’s worth noting that planar networks find commonly application in urban science for representing, either directly or with high accuracy, various infrastructure networks [4], as water distribution networks [5, 6] and lots of streets patterns [7, 8]. The cities structure are the subject of many studies [9, 10, 11, 12] based on their planar aspects; see [13, 14] for a complete bibliography.
We focus our study on the -maximum flow vitality , that is the -max flow decrease when an edge or a vertex is removed, where and are two fixed vertices. A practical metric for assessing the overall vulnerability of a network may involve considering the count of edges/vertices exhibiting high vitality, that is, elements whose deletion implies serious damage to the -maximum flow value. Thus, if all edges and vertices have low vitality, the network can be deemed robust. We refer to [15, 16, 17] for surveys on several kind of robustness and vulnerability problems discussed by an algorithmic point of view.
In networks algorithms, the efect of edges removal/damage on the max flow value has been studied since 1963, only a few years after the pioneering paper by Ford and Fulkerson [18] in 1956. Wollmer [19] presented an algorithm for determining the most vital edge in a railway network, and other studies about max flow interdiction were carried out on the planar Russian railway [20, 21] reported in Figure 1. According to Schrijver [22], in those year the study of vitality and interdiction on maximum flow problem arose from the US Air Force’s desire to disrupt the transportation capabilities of their adversaries.
Ratlif and Sicilia [ 23] describe an algorithm for the most vital edges, where the removal of these edge is simultaneous. Wood [24] showed that this problem is NP-hard in the strong sense, while its approximability has been studied in [25, 26]. Other interdiction problems studied in the literature include: shortest paths [27], minimum spanning tree [28, 29, 30], maximum matching [31, 32] and connectivity [33].
Previous work A recent survey on exact -max flow algorithms can be found in [ 34]. The best know algorithms for general graphs solve the problem in () time [35, 36]. For undirected planar graphs a better result in ( log log ) is presented by Italiano et al. [37], while for planar directed graphs Borradaile and Klein [38] propose an ( log ) time algorithm. The easier -planar case (that is when and are in the same face of a planar embedding) is reduced by Hassin [39] to the computation of a single source shortest paths; that can be solved in () time [40]. Finally, Eisenstat and Klein [41] illustrate how to compute the max flow in undirected unweighted planar graphs in optimal () time.
There are a few results focused on max flow vitality. In [ 42] the vitality of each edge and vertex is computed in optimal () time in the -planar case. The dynamic max flow algorithms presented in [37, 43] allow also to computed edge and vertex vitality for undirected planar graphs, we remind to Theorem 3 for a more in-depth discussion.
Our contribution We present fast algorithms for computing an additive guaranteed approximation of the -max flow vitality for both edges and vertices with capacities below a chosen threshold . In Section 4 we explain how to use our results in real world scenarios.
Let be an undirected planar graphs, let () and () be its set of edges and vertices, respectively, and let and be two fixed vertices. Let us denote by MF or MF if no confusion arises, its -max flow. Let : () → R+ be the edge capacity function, we define the capacity () of a vertex as the sum of the capacities of all edges incident on .
Formally, the -max flow vitality of a set ⊆ ( () ∖ {, }) ∪ (), denoted by (), corresponds to MF − MF− , where − is the graph derived from by deleting set . Our main results are summarized in the following two theorems. We show that we can compute an approximated value of both edge and vertex vitalities with an additive error lower than > 0, where is an arbitrarily fixed vitality. All our algorithms work in () space. Theorem 1. Let be a planar graph with positive edge capacities. Then for any , > 0, we can compute a value () ∈ (() − , ()] for each ∈ () satisfying () ≤ , in ( + log log ) time.
Theorem 2. Let be a planar graph with positive edge capacities. Then for any , > 0, we can compute a value () ∈ (() − , ()] for each ∈ () satisfying () ≤ , in ( + log ) time.
In the full version of the paper [
Outline Our procedure is split into two parts. We start from the approach introduced by Itai and Shiloach’s [46] for computing the -max flow in undirected planar graphs, see Section 2. They translate the max flow computation into finding non-crossing shortest paths in graph , which is derived from the dual graph of . We use this construction to prove that edge vitalities can be inferred by knowing some distances in , see Proposition 1. In the second part, which is exposed in Section 3, we compute required distances by introducing a divide-and-conquer strategy, which consists in slicing via non-crossing shortest paths, see Lemma 1.
In Section 4 we apply our results to real world scenario, and in Section 5 conclusions and open problems are presented.
The first part of our approach is based on the work by Itai and Shiloach [ 46], that computes the -maximum flow of via -separating cycle in its dual graph * . They build an auxiliary graph (if no confusion arises, denoted as ) where the -separating cycles correspond to non-crossing shortest paths between pairs vertices on the external face of . Starting from , we explain how computing edge vitalities of by finding some distances in , this is our main result of this section and it is exposed in Proposition 1. Now we describe into details the construction of by Itai and Shiloach [46].
We observe that every vertex in * corresponds to a face in . In Figure 2 on the left, there is graph in black continuous edges, and graph * in red dashed edges. In [46], the authors ifrst fix a shortest path
from * to * , where * to * are the vertices in * corresponding to faces in containing and , respectively. Without loss of generality, we assume that = {1*, 2*, . . . , *}, with 1* = * and * = * . Path is represented in green in Figure 2 on the left. Then they “cut” * along obtaining graph (for convenience we refer to it as graph ) represented in Figure 2 on the right. by * (this happens when > ).
They double path into the paths and , the first has vertices {1, . . . , } and the latter {1, . . . , }. In order to split the graph * into two, has to split the whole plane into two parts. To obtain this, they add two dummy vertices and , and they connect them to * and * , respectively. If is inside the face containing and inside the face containing , then the edges * and * can be extended to the infinity, splitting the whole plane where * is embedded into two arbitrarily parts and ; without loss of generality we say that is the part “above” and the part “below” . Now we can explain how to build graph .
For any ∈ [], where [] = {1, . . . , }, edges in * incident on each * from below are moved to and edges incident on * from above are moved to . For each * ∈ in * , in the copy of * in is denoted by *, and the copy of * in is denoted by *. Note that every vertex in generates a face * in * , that still remains a face in , still denoted by * . If * in * does not belong to , then we still denote the corresponding edge in by * . Similarly, if * in * does not belong to , then we still denote the corresponding vertex in 1* 8* * ∞ 2* 3* ℎ 4* 5*
6* 7* 1 8* 1 * * ℎ * *
2 7* * * ∞ 2 3 6* * * 3 * 5* 4 4 (1* ) to * (*) in green, and are dummy vertices. On the right graph .
For ∈ [], we define = dist(, ). Itai and Shiloach [46] proved that MF = min∈[] , that is, the -maximum flow is equal to the minimum -separating cycle. We observe that the removal of an edge in corresponds to contracting vertices of * in * into one, and so some ’s may be shorten. For this reason, for * ∈ () and ∈ [] we define (* ) = min{, dist(, * ) + dist(, * )}. Note that (* ) represents the distance in from to if all vertices of * are contracted into one. For ∈ () we define MF as the -maximum lfow in graph − . It follows that () = MF − MF and, trivially, () > 0 if and only if MF < MF. In the following proposition we translate the problem of computing edge vitality in into computing distances in .
Proposition 1. For every edge of , if * ̸∈ in * , then MF = min∈[]{(* )}. If * ∈ in * , then MF = min∈[] ︀{ min{(*), (*)}}︀ .
In this section we explain our divide-and-conquer strategy that leads to Lemma 1, which is the key to derive Theorem 1. We slice graph along shortest non-crossing ’s paths.
From now on, for ∈ [] we fix a shortest path , and we consider that {}∈[] is a set of pairwise single-touch non-crossing shortest paths, where two paths are single-touch if their intersection is still a path. All the ’s can be computed in ( log log ) time by the algorithm in [37], and their lengths in () time by the algorithm in [44].
Let = ⋃︀∈[] , see Figure 3(a). The single-touch property assures us that is a forest. Given an path and a path , we define ∘ as the (possibly not simple) path obtained by the union of and . Each ’s splits into two parts as shown in the following definition and in Figure 3(b).
Definition 1. For every ∈ [], we define Left as the subgraph of bounded by the cycle [1, ] ∘ ∘ [, 1] ∘ , where is the leftmost 11 path in . Similarly, we define Right as the subgraph of bounded by the cycle [, ] ∘ ∘ [, ] ∘ , where is the rightmost path in . 1 2 3 4 5 6
7 8 1 1 2 3 4 5 6 (a) 7 8 1
Left
Right (b) 1 1 Ω, (c)
Based on Definition 1, for every , ∈ [], with < , we define Ω, = Right ∩ Left , see Figure 3(c). Our divide-and-conquer strategy is based on these slices Ω, . Now we have to bucket the indices {1, 2, . . . , } so that these slices have some special distance properties.
For every ∈ N, we define = (ℓ1, . . . , ℓ ) as the ordered list of indices in [] such that ∈ [MF + , MF + ( + 1)), for all ∈ , and ℓ < ℓ+1 for all ∈ [ − 1]. If no confusion arises, we omit the superscript ; thus we write ℓ in place of ℓ.
Now we can formulate properly our slicing strategy in the following lemma. Indeed, we note that every edge in is always contained in a slice. The following lemma is the key of our slicing strategy. In particular, Lemma 1 can be applied for computing distances required in Proposition 1.
Lemma 1. Let > 0 and let = (ℓ1, ℓ2, . . . , ℓ). Let * be a vertex in and let ∈ [ − 1] satisfy * ⊆ Ωℓ,ℓ+1 . Then min ℓ(* ) > min{ℓ (* ), ℓ+1 (* )} − . ℓ∈ Moreover, if * ⊆ Leftℓ1 (resp., * ⊆ minℓ∈ ℓ(* ) > ℓ (* ) − ).
Rightℓ ) then minℓ∈ ℓ(* ) > ℓ1 (* ) − (resp.,
An application of Lemma 1 is in Figure 4. By Proposition 1, we need (* ) for all ∈ [] and consider the minimum value. This can be obtained by 2 SSSP instances in (one with source and one with source for every ∈ []). But we can compute minℓ∈ ℓ(* ) with only 4 SSSP instances focused on the slice of the graph containing * ; in a way, we obtain the minimum among more indices by paying the additive error . In Figure 4, it holds minℓ∈ ℓ(* ) ≥ min{ℓ3 (* ), ℓ4 (* )} − .
ℓ1 ℓ2 ℓ3 ℓ4 ℓ− 1 ℓ Ωℓ1,ℓ2 Ωℓ2,ℓ3 Ωℓ3,ℓ4 *
Ωℓ− 1,ℓ
In the full version of this work [
In this section we explain how to use the results stated in Theorem 1 and Theorem 2 to real world scenario. In particular we describe how to determine and according to the distribution of edge capacities. Note that in real world applications one is usually interested in determining edge and/or vertices with high vitality, that is, edge or vertices whose deletion implies serious damage to the -maximum flow value. This is strictly linked to evaluating the robustness/vulnerability of the network. Before arguing with our theorems, we report here the best algorithm for computing edge vitalities stated in [37, 43].
Theorem 3 ([37, 43]). Let be a planar graph with positive edge capacities. Then it is possible to compute the vitality of ℎ single edges or the vitality of a set of ℎ edges in (min{ loℎg + log log , ℎ2/3 log8/3 + log }) time.
We underline that the previous algorithm can compute the exact vitality of ℎ edges, but in order to obtain information about all edges, we need to apply it with ℎ = .
Returning to the discussion of our theorems, we observe that the capacities may be not bounded by any function of . Despite this, we now introduce some procedures to make / constant. In this way, the time complexity of Theorem 1 becomes ( log log ), that is the best current time bound for computing the -max flow [ 37]. Let’s start with the following crucial remark, where = max∈() ().
Remark 1. [Bounding capacities]. We can bound all edge capacities higher than MF to MF, obtaining a new bounded edge capacity function. This change has no impact on the -max flow value or the vitality of any edge/vertex. Thus w.l.o.g., we can assume that ≤ MF.
After Remark 1, from now on we assume that ≤ MF. We apply the result in Theorem 1 to two real world scenarios. In the first scenario we assume that the distribution of capacities is general, i.e., there is no function that relates a capacity value to the number of edges having that capacity value. In the second scenario we study what happens when the distribution of edge capacities can be described by a power-law; but actually, this can be applied in every case there are few edges (outlier) with high capacity. Take into account that the power-law distribution is very common in real world planar networks, especially in distribution networks.
In Figure 5 we outline the following discussion. The figure shows how to determine constants and in two diferent scenarios (the edge capacities are synthetic).
(a) (b) ∙ General distribution. In this case we can set = and = /, for some small constant , e.g., = 10, 50, 100. So we have a good approximation of edges with high vitality. Indeed, if an edge has vitality comparable with MF, then we obtain its vitality with an additive error smaller than MF/ (because of Remark 1). On the other hand, we have a bad approximation for edges with low capacity; in Figure 5(a) they correspond to edges on the left of the green line. This is not a problem because “small capacity” corresponds to “small vitality”, indeed the vitality of an edge is at most its capacity. With this settings the time complexity stated in Theorem 1 becomes ( log log ), that is the time currently required for the computation of the -max lfow. ∙ Power-law distribution. We cannot apply the same reasoning to the previous case, in fact if we choose = and = / for small constant , then we obtain a bad approximation of all edges on the left of the red line in Figure 5(b). They are absolutely the majority of edges. So we set = / and = /ℓ, for some constant ℓ, and we compute the (exact) vitality of edges whose capacity is greater than via Theorem 3. Note that this set of edges is small because of the power law distribution of capacities. The vitality of edges computed by our algorithm has an additive error smaller than MℓF , because of Remark 1; it may be an acceptable error even for small values of and ℓ. Also in this case, the overall time complexity is equal or close to ( log log ).
Since our algorithms provide approximate vitalities with an additive error, it is possible having as output () = 0 for each ∈ (). At first sight, it may appear as an useless result, but actually we verify the robustness of the network because all edges have vitality smaller than . The same reasoning can be applied also to vertex vitality, and consequently to Theorem 2 by observing that in a real-world planar network there are usually a few vertices with high degree (as also implied by Euler’s formula). We conclude by a fast comparison among our results and the algorithm stated in Theorem 3. It’s clear that we compute approximated vitalities while Theorem 3 allows to compute exact vitality, but if one is interested in understanding the robustness/vulnerability of the network, then it is necessary to evaluate the vitality (exact or approximated) of all edges and/or all vertices. Our algorithms obtain this in a time equal o close to ( log log ), while we need (5/3 log8/2 ) time by using the result in Theorem 3. Hence our results provide considerably faster algorithms.
We describe fast algorithms for computing an additive guaranteed approximation of the -max lfow vitality of both edges and vertices in undirected planar networks. The vulnerability of real world planar networks can be established via our algorithms under various edge capacity distributions.
We left open the problem of computing the exact vitality of all edges and vertices in the same time required for computing the max flow value, as is already known for the -planar case. [3] H. V. Nath, Vulnerability assessment methods – a review, in: D. C. Wyld, M. Wozniak, N. Chaki, N. Meghanathan, D. Nagamalai (Eds.), Advances in Network Security and Applications, Springer Berlin Heidelberg, Berlin, Heidelberg, 2011, pp. 1–10. doi:10.1007/ 978-3-642-22540-6_1. [4] M. Barthélemy, Spatial networks, Physics Reports 499 (2011) 1–101. doi:https://doi.
org/10.1016/j.physrep.2010.11.002. [5] V. Chauhan, Planar Graph Generation with Application to Water Distribution Networks,
Ph.D. thesis, Clemson University, 2018. [6] M. Herrera, E. Abraham, I. Stoianov, A Graph-Theoretic Framework for Assessing the Resilience of Sectorised Water Distribution Networks, Water Resources Management 30 (2016) 1685–1699. doi:10.1007/s11269-016-1245-6. [7] S. Marshall, Streets and Patterns, Routledge, 2004. doi:10.4324/9780203589397. [8] M. Southworth, E. Ben-Joseph, Streets and the Shaping of Towns and Cities, Island Press, 2013. [9] M. Barthélemy, A. Flammini, Modeling Urban Street Patterns, Phys. Rev. Lett. 100 (2008) 138702. doi:10.1103/PhysRevLett.100.138702. [10] J. Buhl, J. Gautrais, N. Reeves, R. V. Solé, S. Valverde, P. Kuntz, G. Theraulaz, Topological patterns in street networks of self-organized urban settlements, The European Physical Journal B-Condensed Matter and Complex Systems 49 (2006) 513–522. doi:10.1140/ epjb/e2006-00085-1. [11] A. Cardillo, S. Scellato, V. Latora, S. Porta, Structural properties of planar graphs of urban street patterns, Phys. Rev. E 73 (2006) 066107. doi:10.1103/PhysRevE.73.066107. [12] A. P. Masucci, D. Smith, A. Crooks, M. Batty, Random planar graphs and the London street network, The European Physical Journal B 71 (2009) 259–271. doi:10.1140/epjb/ e2009-00290-4. [13] G. Boeing, A multi-scale analysis of 27,000 urban street networks: Every us city, town, urbanized area, and zillow neighborhood, Environment and Planning B: Urban Analytics and City Science 47 (2020) 590–608. doi:10.1177/2399808318784595. [14] M. P. Viana, E. Strano, P. Bordin, M. Barthelemy, The simplicity of planar networks,
Scientific reports 3 (2013) 3495. doi: 10.1038/srep03495. [15] D. L. Alderson, G. G. Brown, W. M. Carlyle, L. A. Cox Jr, Sometimes There Is No “Most-Vital” Arc: Assessing and Improving the Operational Resilience of Systems, Military Operations Research 18 (2013) 21–37. [16] L.-G. Mattsson, E. Jenelius, Vulnerability and resilience of transport systems – a discussion of recent research, Transportation Research Part A: Policy and Practice 81 (2015) 16–34. doi:https://doi.org/10.1016/j.tra.2015.06.002, resilience of Networks. [17] A. T. Murray, An overview of network vulnerability modeling approaches, GeoJournal 78 (2013) 209–221. doi:http://dx.doi.org/10.1007/s10708-011-9412-z. [18] L. R. Ford, D. R. Fulkerson, Maximal Flow Through a Network, Canadian journal of Mathematics 8 (1956) 399–404. doi:http://dx.doi.org/10.1007/978-0-8176-4842-8_ 15. [19] R. D. Wollmer, Some Methods for Determining the Most Vital Link in a Railway Network,
Rand Corporation, 1963. [20] T. Harris, F. Ross, Fundamentals of a Method for Evaluating Rail Net Capacities, Technical
Report, Rand Corporation, 1955. [21] A. W. McMasters, T. M. Mustin, Optimal Interdiction of a Supply Network, Naval Research Logistics Quarterly 17 (1970) 261–268. doi:http://dx.doi.org/10.1002/ nav.3800170302. [22] A. Schrijver, On the history of the transportation and maximum flow problems, Mathematical programming 91 (2002) 437–445. doi:http://dx.doi.org/10.1007/ s101070100259. [23] H. D. Ratlif, G. T. Sicilia, S. Lubore, Finding the n Most Vital Links in Flow Networks, Management Science 21 (1975) 531–539. doi:http://dx.doi.org/10.1287/mnsc.21. 5.531. [24] R. K. Wood, Deterministic Network Interdiction, Mathematical and Computer Modelling 17 (1993) 1–18. doi:http://dx.doi.org/10.1016/0895-7177(93)90236-R. [25] D. S. Altner, Ö. Ergun, N. A. Uhan, The Maximum Flow Network Interdiction Problem: Valid Inequalities, Integrality Gaps, and Approximability, Operations Research Letters 38 (2010) 33–38. doi:10.1016/j.orl.2009.09.013. [26] C. A. Phillips, The Network Inhibition Problem, in: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, ACM, 1993, pp. 776–785. doi:10. 1145/167088.167286. [27] E. Israeli, R. K. Wood, Shortest-path network interdiction, Networks 40 (2002) 97–111.
doi:https://doi.org/10.1002/net.10039. [28] L.-H. Hsu, R.-H. Jan, Y.-C. Lee, C.-N. Hung, M.-S. Chern, Finding the most vital edge with respect to minimum spanning tree in weighted graphs, Information Processing Letters 39 (1991) 277–281. doi:https://doi.org/10.1016/0020-0190(91)90028-G. [29] L.-H. Hsu, P.-F. Wang, C.-T. Wu, Parallel algorithms for finding the most vital edge with respect to minimum spanning tree, Parallel Computing 18 (1992) 1143–1155. doi:https: //doi.org/10.1016/0167-8191(92)90061-B. [30] S. Banerjee, S. Saxena, Parallel algorithm for finding the most vital edge in weighted graphs, Journal of Parallel and Distributed Computing 46 (1997) 101–104. doi:https: //doi.org/10.1006/jpdc.1997.1383. [31] R. Zenklusen, Matching interdiction, Discrete Applied Mathematics 158 (2010) 1676–1690.
doi:https://doi.org/10.1016/j.dam.2010.06.006. [32] M. Dinitz, A. Gupta, Packing interdiction and partial covering problems, in: M. Goemans, J. Correa (Eds.), Integer Programming and Combinatorial Optimization, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013, pp. 157–168. doi:http://dx.doi.org/10.1007/ 978-3-642-36694-9_14. [33] R. Zenklusen, Connectivity interdiction, Operations Research Letters 42 (2014) 450–454.
doi:https://doi.org/10.1016/j.orl.2014.07.010. [34] O. Cruz-Mejía, A. N. Letchford, A survey on exact algorithms for the maximum flow and minimum-cost flow problems, Networks 82 (2023) 167–176. doi: https://doi.org/ 10.1002/net.22169. [35] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows (1988). [36] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, M. Reddy, Applications of Network Optimization,
Handbooks in Operations Research and Management Science 7 (1995) 1–83. [37] G. F. Italiano, Y. Nussbaum, P. Sankowski, C. Wulf-Nilsen, Improved Algorithms for Min Cut and Max Flow in Undirected Planar Graphs, in: Proceedings of the 43rd ACM Symposium on Theory of Computing, ACM, 2011, pp. 313–322. doi:10.1145/1993636. 1993679. [38] G. Borradaile, P. N. Klein, An ( log ) Algorithm for Maximum st-Flow in a Directed
Planar Graph, Journal of the ACM 56 (2009) 9:1–9:30. doi:10.1145/1502793.1502798. [39] R. Hassin, Maximum Flow in (s,t) Planar Networks, Information Processing Letters 13 (1981) 107. doi:10.1016/0020-0190(81)90120-4. [40] M. R. Henzinger, P. N. Klein, S. Rao, S. Subramanian, Faster Shortest-Path Algorithms for Planar Graphs, Journal of Computer and System Sciences 55 (1997) 3–23. doi:10.1006/ jcss.1997.1493. [41] D. Eisenstat, P. N. Klein, Linear-Time Algorithms for Max Flow and Multiple-Source Shortest Paths in Unit-Weight Planar Graphs, in: Symposium on Theory of Computing Conference, STOC’13, ACM, 2013, pp. 735–744. doi:10.1145/2488608.2488702. [42] G. Ausiello, P. G. Franciosa, I. Lari, A. Ribichini, Max flow vitality in general and st-planar graphs, Networks 74 (2019) 70–78. doi:10.1002/net.21878. [43] J. Łącki, P. Sankowski, Min-Cuts and Shortest Cycles in Planar Graphs in ( log log ) Time, in: Algorithms - ESA 2011 - 19th Annual European Symposium, Proceedings, volume 6942 of Lecture Notes in Computer Science, Springer, 2011, pp. 155–166. doi:10. 1007/978-3-642-23719-5\_14. [44] L. Balzotti, P. G. Franciosa, Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time, Journal of Graph Algorithms and Applications 26 (2022) 589–606. doi:10.7155/jgaa.00610. [45] L. Kowalik, M. Kurowski, Short Path Queries in Planar Graphs in Constant Time, in: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, ACM, 2003, pp. 143–148. doi:10.1145/780542.780565. [46] A. Itai, Y. Shiloach, Maximum Flow in Planar Networks, SIAM Journal on Computing 8 (1979) 135–150. doi:10.1137/0208012.