betaFeedback

WorksMathematics

Composition of Near-Planar Infrastructure Network Instances with Certified Skewness Bounds

Abstract

Computational studies of optimization problems on infrastructure networks may require more suitable instances than are available. We propose a method to obtain additional instances by extracting and joining connected parts of existing networks, reusing their topology and parameters. Many infrastructure networks are near-planar, so added connections should preserve this property. We measure near-planarity by skewness, the minimum number of edges whose removal makes a graph planar. We derive bounds on the additional skewness caused by joining and give sufficient conditions under which none is added, and propose the corresponding strategy. We evaluate our approach on 100 sets of network parts extracted from each of PGLib-OPF and SNDlib. Within time limits, we show that no skewness is added for about half of the resulting power transmission networks and all considered telecommunication networks. Our method gives smaller mean upper bounds on added skewness than baselines that select vertices randomly, in order of decreasing degree, or using a Kamada–Kawai layout. Extraction and composition may also make the resulting optimization instances infeasible. To reduce this risk, we solve a simpler, tractable variant of the intended optimization problem during generation and restart if it is infeasible. On the generated instances, we solve security-constrained optimal transmission switching and survivable network design problems in full, demonstrating that the instances vary in computational difficulty with runtimes ranging from seconds to hours. The method thus extends the available benchmark sets with instances that inherit source data, have known skewness bounds, and cover a range of computational difficulty.

Introduction

Meaningful computational studies require a sufficiently large and diverse test set to support their conclusions ([5, 27, 14]). The number of instances provided by public libraries may be insufficient to reliably establish statistically significant performance differences between algorithms, leaving researchers to draw unreliable conclusions, or to obtain additional instances. Additional instances can be obtained by generating them from scratch or reusing existing ones. The difficulty in the former is choosing realistic parameters, which requires considerable domain knowledge. The advantage in the latter is that the instances are already accepted by the community, and for certain types of problems, a combination of multiple instances may also be accepted if an appropriate combination strategy is applied.

We consider network-based optimization problems for real-world infrastructure networks, where a composition comprises merging the underlying networks, e.g., by adding an edge (see Figure 1). Infrastructure networks are usually near-planar ([3, 6, 24]) (Figure 1a), so it is desirable that generated instances retain that property (Figure 1b). We quantify near-planarity by skewness, the minimum number of edges that must be removed to make a graph planar (Liebers, [59], Def. 11). A poor merge of two networks can increase skewness well beyond that already present in the extracted subgraphs (Figure 1c). Avoiding this increase may require computing maximum planar subgraphs, which is computationally expensive.

Schematic networks and connections

Figure 1. Schematic networks and connections. Country boundaries: © EuroGeographics, via Eurostat/GISCO.

We study how to compose network instances while controlling added skewness and reducing infeasibility rates. Our contributions are the following. First, we propose a generic composition framework. It extracts connected subgraphs, retaining their node and edge parameters, and compensates flows removed at cut edges. We join the subgraphs by adding coupling edges between selected vertices, called merge vertices. We solve a tractable auxiliary problem of the problem the instance is intended for, and only retain the instance if it is feasible. Second, we derive bounds on the skewness added by composition and give conditions under which none is added. We also bound changes in degree distribution, maximum degree, and average clustering. Third, we design an exact vertex selection strategy and prove that it adds no skewness when maximum planar subgraphs are used. We compare this strategy with alternatives that select vertices randomly, in order of decreasing degree, or based on a Kamada–Kawai layout (Kamada and Kawai, [48]). Fourth, we evaluate the construction on source instances stemming from PGLib-OPF (Babaeinejadsarookolaee et al., [1]) and SNDlib (Orlowski et al., [66]). We then use the generated instances in experiments in security-constrained optimal transmission switching (SCOTS) and in survivable network design (SND).

Our proposed exact selection strategy gives smaller mean upper bounds on added skewness than the alternatives. We show that no skewness is added for about half of the power transmission composites and all telecommunication composites. The choice of merge vertices also affects properties beyond skewness, including degree distribution, graph diameter and connectivity, which we compare across the different strategies. To examine whether the generated instances are useful for optimization experiments, we also evaluate their computational outcomes and solution times. Runtimes range from seconds to hours in both applications, demonstrating differences in computational difficulty among the generated instances.

The proposed method therefore extends the available test sets with instances that retain characteristics of realistic infrastructure networks and span a range of computational difficulty.

Related Work

Computational Evaluation: Best Practices. Guidelines for computational experiments emphasize representative, sufficiently large and diverse test sets [62, 5, 71]. Hooker [42, 43] additionally suggests systematic variation of instance properties helps explain algorithm performance. Beiranvand et al. [5] recommend at least 20 instances for a dependable conclusion and 100 or more to detect performance differences between algorithm variants. Campelo and Takahashi [14] and Campelo and Wanner [15] provide methods to determine how many instances are needed to detect specified performance differences at a chosen statistical significance level. For example, they calculate a requirement of 34 instances for a paired tt-test at a 5% significance level [14 Section 5.1]. Lodi and Tramontani [60] also recommend repeated runs on the same instance (e.g., with different seeds) to account for runtime variability in mixed-integer programming.

These recommendations motivate sufficiently large and diverse test sets that remain representative of the application. For the infrastructure networks considered in this paper, this means retaining near-planarity while varying properties such as network size, connectivity and computational difficulty.

Computational studies of security-constrained optimal power flow problems. Optimal power flow (OPF) problems minimize the cost of generation under the physical constraints of the power grid. The security-constrained optimal power flow (SCOPF) problem extends the OPF by requiring feasible operation under contingency scenarios, e.g., single-edge failures. PGLib-OPF provides a library of 66 power system instances ranging from 3 to 78,484 buses [1]. Due to that large range, the number of relevant instances for a given problem formulation and algorithm (i.e., those that are neither trivial, nor too hard) can be much smaller. Additionally, some instances do not admit a feasible solution to SCOPF or its variants, motivating researchers to modify them to obtain feasible instances.

Table 1 summarizes our review of the Web of Science Core Collection (Clarivate Analytics, n.d.) query TS=("optimal power flow") AND PY=(2003–2023), executed on 2024-04-09. After sorting by citation count, we screened the 50 most-cited records and retained 18 computational studies that impose contingency constraints or analyze the computed solutions under contingencies.

Table 1: Test case use in power flow and transmission switching studies. Base networks: ■ unmodified, ◩ modified, □ unused. Numbers denote base-network bus counts. Enforced contingencies within each study’s outage model: ● all, ◐ a subset, ○ none. A question mark indicates undisclosed or incomplete modification information.

Base networkOutages
14305773118300Other
Fisher et al. [31]□□□□◩□○
Hedman et al. [39]□□□◩◩□◐
Khodaei and Shahidehpour [51]□□□□◩□Custom 6-bus?
O’Neill et al. [65]□□□◩□□●
Barrows et al. [2]□□□◩□□●
Khanabadi et al. [49]□□?□□■◐
Khodaei and Shahidehpour [52]□□□□◩□◐
Ruiz et al. [69]□□□□?□?
Heidarifar et al. [40]◩□□□□□◐
Chiang and Grothey [19]□??□◩◩3-bus; Iceland?; grids??
Ding and Zhao [28]□◩□□□□●
Khanabadi et al. [50]□□□□?□6-bus; 472-bus??
Behnia and Akhbari [4]□□□□□□Modified IEEE-24●
Saavedra et al. [70]□□□□◩◩Custom 4-bus◐
Han et al. [37]□■□□□□Germany?◐
Heidarifar et al. [41]◩□◩□◩□◐
Li et al. [57]□□□□□■Modified PJM-5; French 1888-bus?
Han et al. [38]■■■□□□Germany (50Hertz)◐

Table 1.

Most reviewed publications use only one to three base networks. Some studies leave the exact contingency sets or details of other instance modifications undisclosed, limiting reproducibility and comparability.

The use of so few base networks and extensive, sometimes undisclosed modifications highlights the community’s need for additional instances at relevant levels of computational difficulty to support meaningful computational evaluations.

Computational studies of survivable network design problems. Network design problems minimize the cost of installing edge capacities to accommodate commodity flows between their sources and sinks. A possible survivability requirement is that flows can be rerouted (arbitrarily) to fulfill all demands after any single-edge failure. Available libraries provide topologies of real telecommunication networks [53, 72] and graphs from a wide range of other applications [55, 68]. These libraries supply only the graph, requiring researchers to synthesize the parameters of the survivable network design problem themselves. One of the most widely used libraries that does include parameters is SNDlib ([66]), whose original release contains 22 network topologies.

Planarization and maximum planar subgraphs. Computing a maximum planar subgraph, a planar subgraph with the largest possible number of edges, is NP-hard ((Yannakakis, 1978)). Exact approaches include integer programming formulations solved by branch-and-cut ([46, 20, 22]). Liebers [59] surveys the broader planarization literature.

Instance Generation Strategies

We categorize approaches to generating network instances into five groups.

Generation builds an instance from scratch by sampling from a model. It requires significant domain knowledge to design a generator that produces realistic instances. Application-specific generators produce water distribution ([25]), heating ([13]), and transportation networks ([11, 54]). Other approaches construct power system models from geographic and infrastructure data ([7, 44, 63]). Graph generators sample from random graph models to produce large networks with specified structural properties, such as degree distributions and clustering coefficients ([36, 8, 34]).

Perturbation derives new instances by changing the parameters or topology of an existing instance. Examples include varying loads, power generation, and topology in power systems ([61] (Rivera Him et al. 2025)), and water demands, pipe diameters, and pump speeds in water networks ([74]). OPF-Learn ([45]) generates feasible load profiles for the alternating-current (AC) optimal power flow problem for a given network. Multiscale Planar Graph Generation ([18]) modifies nodes and edges of a given planar graph to generate structurally similar planar graphs. ReCoN ([73]) and Global Curveball ([16]) randomly replace edges while preserving each node’s degree.

Learning fits a generative model to existing graphs and samples new graphs from it ([56, 79, 10]). For power systems, Xiao et al. [77] learn from instances with feasible AC power flows to generate new feasible instances.

Slicing extracts smaller subinstances from one large instance. Li et al. (2026, Section IV.A) extract connected subgraphs of power networks and replace flows on removed connections with equivalent loads.

Composition joins several existing instances into a new, larger one. Grigg et al. [35] construct the IEEE 73-bus system by connecting three copies of the IEEE 24-bus system. They add one bus connected to an existing bus by a phase-shifting transformer. Donkiewicz (2026) extracts subgraphs from SNDlib instances and connects high-degree nodes to generate further SND instances. Classical work in graph theory studies how merging graphs by identifying selected vertices affects the structural properties of the resulting graph ([76, 26]).

Positioning of this work

Our method reuses the topology and parameters of existing infrastructure network instances, reducing the need to synthesize application data. We select source instances within an application domain from existing, accepted libraries. From those source instances, we extract subinstances and join them with coupling edges, retaining internal edges. This allows one composite to combine characteristics of different source networks. Multiscale Planar Graph Generation and ReCoN generate variants of a single source graph without assigning application parameters ([18, 73]). Relying on one source can bias a test set toward that network.

In graph composition, arbitrary choices of where to put coupling edges can produce unrealistic infrastructure networks by disrupting their characteristic near-planarity (Figure 1c). We extend and compare to earlier composition approaches ([35] (Donkiewicz 2026)) by using planar subgraphs to select merge vertices. We derive bounds on added skewness and prove that this strategy adds none when the planar subgraphs are maximum. We also bound changes in degree distribution, maximum degree, and average clustering.

Like Li et al. [58], we compensate removed flows, but also allow the compensation to vary to improve feasibility after composition. We establish sufficient conditions for preserving feasibility of an application-specific auxiliary problem during extraction and composition (Proposition 2 and Corollary 2). We solve this auxiliary problem for each composite. We evaluate the generated instances’ structural properties and computational difficulty for SCOTS and SND.

Problem Setting and Notation

To establish a generic framework for the composition of instances for network-based optimization problems, we first define an abstract network instance and the associated optimization problem (§ 4.1 and § 4.2). We define graph-theoretic properties used to describe the graphs underlying a network instance and how they change when composing multiple graphs (§ 4.3 to § 4.5). Finally, we introduce the two concrete problems used for the computational evaluation: security-constrained optimal transmission switching and its direct-current (DC) optimal power flow feasibility check (§ 4.7), and min-cost multicommodity flow as the feasibility check for SND (§ 4.8).

Note that throughout this paper, we will be referring to (sub)-instances whenever talking about the graph together with node and edge parameters and possibly some metainformation required for the optimization problem. We refer to (sub-)graphs whenever the described properties or algorithms do not access any of the instance data, but only require the graph.

Abstract network instance

A network instance is a tuple N=(V,E,K,S,P)\mathcal{N} = (V, E, K, S, \mathcal{P}). We write G(N)=(V,E)G(\mathcal{N}) = (V, E) for its underlying graph. The pair (V,E)(V, E) is a graph whose edges are written in a fixed reference direction. For a directed model, this is the direction of the edge. For an undirected model, it is only a notational orientation, and the application determines whether flow opposite to it is allowed. The set KK contains the commodities and may be empty or contain only one element. A commodity is a class of flow with its own supply and demand. The remaining components are families indexed by KK. S={Sk}k∈KS = \{S_k\}_{k \in K} collects all supply and demand values attached to a node. For each k∈Kk \in K, Sk:V→R2S_k : V \to\mathbb{R}^2 is a function whose value Sk1(v)S_{k1}(v) is the lower bound and Sk2(v)S_{k2}(v) is the upper bound for supply or demand (depending on whether it assumes a positive or negative value) at node vv. In particular, when Sk1(v)=Sk2(v)S_{k1}(v) = S_{k2}(v), the supply or demand at vv is fixed to that value. Otherwise, it is a variable within these bounds. If fkf_k and sks_k denote realized flows and supplies where sk(v)∈[Sk1(v),Sk2(v)]s_k(v) \in[S_{k1}(v), S_{k2}(v)], we impose flow conservation

∑(v,w)∈Efk(v,w)=∑(u,v)∈Efk(u,v)+sk(v),\sum_{(v,w)\in E} f_k(v,w) = \sum_{(u,v)\in E} f_k(u,v) + s_k(v),

i.e., total outgoing flow equals total incoming flow plus the supply attached to the node. P={Pk}k∈K\mathcal{P} = \{P_k\}_{k \in K} consists of node- and edge-attached parameter data per commodity. This includes, e.g., capacities, physical attributes (susceptances and angle limits in power systems; routing information in SND) and objective coefficients (generation cost functions in power systems; unit routing costs in SND). When ∣K∣=1|K| = 1, the commodity index is dropped from the notation. Several commodities may share a single attribute; e.g., in the considered SND all commodities share the edge capacity (§ 4.8).

We call a finite set of network instances that the community accepts as realistic a library, denoted N={N1,N2,…}\mathfrak{N} = \{\mathcal{N}_1, \mathcal{N}_2, \ldots\}. The composition pipeline of § 5 draws its source instances from such a library. When source instances are composed, an edge added between two different source graphs is a coupling edge, and a vertex incident with such an edge is a merge vertex.

Abstract optimization problem and feasibility check

The same network instance may be used for different variants of an optimization problem. Here, Opt⁡(N)\operatorname{Opt}(\mathcal{N}) denotes the fixed optimization problem for which we generate instances. Tract⁡(N)\operatorname{Tract}(\mathcal{N}) denotes an application-specific, tractable auxiliary optimization problem used during instance generation. It serves as a proxy for the suitability of N\mathcal{N} for Opt⁡(N)\operatorname{Opt}(\mathcal{N}) and need not certify feasibility or infeasibility for Opt⁡(N)\operatorname{Opt}(\mathcal{N}). We solve Tract⁡(N)\operatorname{Tract}(\mathcal{N}) for each selected source instance and composed instance (see § 5).

Skewness and other structural properties of graphs

To describe the structural effects of composition, we define the graph-theoretic properties for which we give identities, bounds or empirical measurements in the evaluation. For these structural properties, we consider the simple undirected graph GG obtained by ignoring edge orientations, removing self-loops and replacing parallel edges by a single edge. Further, let NG(v)={u:uv∈E(G)}N_G(v) = \{u : uv \in E(G)\} be the neighborhood of vv and dG(v)=∣NG(v)∣d_G(v) = |N_G(v)| its degree.

Our primary graph property is the skewness

sk⁡(G)=min⁡{∣F∣:F⊆E(G), G−F is planar}=∣E(G)∣−mps⁡(G),\operatorname{sk}(G) = \min\{|F| : F \subseteq E(G),\ G-F\text{ is planar}\} = |E(G)| - \operatorname{mps}(G),

where mps⁡(G)=max⁡{∣E′∣:E′⊆E(G),(V(G),E′) is planar}\operatorname{mps}(G) = \max\{|E'| : E' \subseteq E(G), (V(G), E')\text{ is planar}\}. A subgraph attaining this maximum is called a maximum planar subgraph; computing one is also called planarization. Throughout, we denote planar subgraphs by HH. Skewness counts exactly how many edges must be removed to recover planarity (see Figure 2b for an example), and is thus a measure of the graph’s near-planarity. Computing a maximum planar subgraph is NP-hard (Yannakakis, 1978). If a maximum planar subgraph computation is stopped before proving optimality, any planar subgraph found gives an upper bound on skewness.

Planar embeddings, noncrossing matching, and crossing matching

Figure 2. H1,H2H_1,H_2 are maximum planar subgraphs. Numbers in parentheses count distinct boundary vertices. Shading marks the chosen faces before joining. The dotted edge belongs to G1G_1. Dashed edges match the filled vertices.

Some graph characteristics remain unchanged except in the vicinity of the merge vertices. Those can be compared between the source graphs and the composite graphs. We record the degree distribution

pG(q)=∣{v∈V(G):dG(v)=q}∣∣V(G)∣p_G(q) = \frac{|\{v \in V(G) : d_G(v) = q\}|}{|V(G)|}

and the maximum degree Δ(G)=max⁡vdG(v)\Delta(G) = \max_v d_G(v).

The local clustering coefficient of vv is

cG(v)={2∣{uw∈E(G):u,w∈NG(v)}∣dG(v)(dG(v)−1),dG(v)≥2,0,dG(v)<2.c_G(v) = \begin{cases} \frac{2|\{uw \in E(G) : u,w \in N_G(v)\}|}{d_G(v)(d_G(v)-1)}, & d_G(v) \ge2,\\ 0, & d_G(v) < 2. \end{cases}

In other words, cG(v)c_G(v) is the fraction of possible triangles that include vv. We report the average clustering coefficient cˉ(G)=1∣V(G)∣∑vcG(v)\bar{c}(G) = \frac{1}{|V(G)|}\sum_v c_G(v).

We additionally consider characteristics whose changes cannot easily be bounded, because they depend on the choice of the merge vertices when composing two graphs. Such characteristics can be compared against the full source library rather than the source graphs for the composite. The diameter of a connected graph gives the maximum distance between any two vertices:

diam⁡(G)=max⁡u,v∈V(G)dist⁡G(u,v),\operatorname{diam}(G) = \max_{u,v\in V(G)} \operatorname{dist}_G(u,v),

where dist⁡G(u,v)\operatorname{dist}_G(u,v) is the length of a shortest path between uu and vv in GG.

Let n=∣V(G)∣n = |V(G)| and let 0=λ1(G)≤λ2(G)≤⋯≤λn(G)0 = \lambda_1(G) \le\lambda_2(G) \le\cdots\le\lambda_n(G) be the eigenvalues of the Laplacian L=D−AL = D - A, where AA is the adjacency matrix and DD is the diagonal matrix of vertex degrees, in the same vertex order as AA. The second eigenvalue λ2(G)\lambda_2(G) is the algebraic connectivity; it is positive exactly when GG is connected, and a small positive value indicates a bottleneck.

Finally, the degree assortativity r(G)r(G) [64] is the correlation between endpoint degrees in the underlying simple undirected graph. It is undefined when the variance of the endpoint degrees is zero. When defined, it lies in [−1,1][-1,1]: positive values indicate edges between vertices of similar degree, negative values indicate edges between vertices of dissimilar degree, and zero indicates no linear degree correlation.

Skewness of composite graphs

Consider connected source graphs G1,…,GpG_1,\ldots,G_p and their disjoint union ⋃i=1pGi\bigcup_{i=1}^{p}G_i, the graph whose vertex set and edge set are the disjoint unions of the V(Gi)V(G_i) and the E(Gi)E(G_i), so that the sources share no vertex or edge. Adding a set MM of coupling edges, each between a vertex of one source and a vertex of another, yields the composite C=(⋃i=1pGi)+M\mathcal{C} = (\bigcup_{i=1}^{p}G_i) + M, where +M+M denotes the addition of the edge set MM.

A planar embedding of a graph is a drawing in the plane in which no two edges cross. The embedded vertices and edges divide the plane into connected regions called faces (see Figure 2a). Exactly one face is unbounded and is called the outer face. An equivalent planar embedding can make any chosen face the outer face (see Figure 2a vs. Figure 2b, where f1f_1 and f2f_2 have been moved to the outside). Following the boundary of a face ff gives a sequence of incident vertices and edges that returns to its starting vertex. We denote this boundary walk by WfW_f, in which a vertex or edge may occur more than once (e.g., when a vertex of degree one lies on the boundary). Let V(f)V(f) be the set of distinct vertices occurring in WfW_f. We order the vertices in V(f)V(f) by their first occurrences in WfW_f.

A matching between distinct vertices incident with chosen faces of two planar embeddings is called noncrossing if, with the chosen faces placed as outer faces, the matching edges can be drawn without crossings (Figure 2b). Not every vertex incident with either face must be used to give a valid matching. A matching is crossing if and only if it introduces skewness to the composite (Figure 2c).

Lemma 1 (Skewness bounds for composite graphs). Suppose that the composite CC is connected. Then the skewness of the composite C=(⋃i=1pGi)+MC = \left(\bigcup_{i=1}^{p}G_i\right) + M satisfies

∑i=1psk⁡(Gi)≤sk⁡(C)≤∑i=1psk⁡(Gi)+∣M∣−(p−1).\sum_{i=1}^{p}\operatorname{sk}(G_i) \le\operatorname{sk}(C) \le\sum_{i=1}^{p}\operatorname{sk}(G_i) + \lvert M\rvert- (p-1).

Proof. The edges of CC split into the source edges and the coupling edges, so ∣E(C)∣=∑i∣E(Gi)∣+∣M∣\lvert E(C)\rvert= \sum_i \lvert E(G_i)\rvert+ \lvert M\rvert. For the lower bound, let HH be a maximum planar subgraph of CC. Each restriction H∩GiH \cap G_i is planar and contains at most mps⁡(Gi)\operatorname{mps}(G_i) edges. Together with at most ∣M∣\lvert M\rvert coupling edges, this gives mps⁡(C)≤∑imps⁡(Gi)+∣M∣\operatorname{mps}(C) \le\sum_i \operatorname{mps}(G_i) + \lvert M\rvert and hence sk⁡(C)≥∑isk⁡(Gi)\operatorname{sk}(C) \ge\sum_i \operatorname{sk}(G_i). For the upper bound, choose a maximum planar subgraph HiH_i of each GiG_i. Replace each source graph GiG_i by a single vertex and retain the coupling edges between these vertices. The resulting multigraph is connected and has pp vertices, so it has a spanning tree with p−1p-1 edges. Let T⊆MT \subseteq M be the corresponding set of coupling edges in CC. The graph (⋃iHi)+T\left(\bigcup_i H_i\right) + T is planar: it joins vertex-disjoint planar graphs according to a tree, with every edge of TT acting as a bridge. It omits ∑isk⁡(Gi)\sum_i \operatorname{sk}(G_i) source edges and ∣M∣−(p−1)\lvert M\rvert- (p-1) coupling edges of $C (the ones not contained in the spanning tree) which proves the upper bound.

For arbitrary (e.g., non-maximum) planar subgraphs that omit did_i edges from GiG_i, the same argument gives sk⁡(C)≤∑idi+∣M∣−(p−1)\operatorname{sk}(C) \le\sum_i d_i + |M| - (p-1). The following lemma characterizes when the lower bound is attained.

Lemma 2 (Attainment of the lower skewness bound). The equality

sk⁡(C)=∑i=1psk⁡(Gi)\operatorname{sk}(C)=\sum_{i=1}^{p}\operatorname{sk}(G_i)

holds if and only if there are maximum planar subgraphs Hi⊆GiH_i \subseteq G_i for which (⋃i=1pHi)+M(\bigcup_{i=1}^{p} H_i)+M is planar. In particular, for two sources, this condition holds whenever M={ajbj:j=1,…,k}M=\{a_jb_j:j=1,\ldots,k\} is a noncrossing matching between distinct vertices incident with chosen faces of planar embeddings of maximum planar subgraphs H1H_1 and H2H_2. Consequently, k≤min⁡{∣V(f1)∣,∣V(f2)∣}k\le\min\{|V(f_1)|,|V(f_2)|\} for the two chosen faces, i.e., kk can only be as large as the smaller of the two outer face sizes.

Proof. If (⋃iHi)+M(\bigcup_i H_i)+M is planar, it is a planar subgraph of CC with ∑imps⁡(Gi)+∣M∣\sum_i \operatorname{mps}(G_i)+|M| edges. Thus, mps⁡(C)≥∑imps⁡(Gi)+∣M∣\operatorname{mps}(C)\ge\sum_i \operatorname{mps}(G_i)+|M|. The reverse inequality follows from the proof of Lemma 1, so equality holds.

Conversely, suppose the equality holds and let HH be a maximum planar subgraph of CC. By assumption, planarizing CC deletes exactly ∑isk⁡(Gi)\sum_i \operatorname{sk}(G_i) edges from its ∑i∣E(Gi)∣+∣M∣\sum_i |E(G_i)|+|M| edges. Therefore

∣E(H)∣=mps⁡(C)=∑i(∣E(Gi)∣−sk⁡(Gi))+∣M∣=∑imps⁡(Gi)+∣M∣.\begin{aligned} |E(H)| &= \operatorname{mps}(C)\\ &= \sum_i\bigl(|E(G_i)|-\operatorname{sk}(G_i)\bigr)+|M|\\ &= \sum_i \operatorname{mps}(G_i)+|M|. \end{aligned}

The right-hand side is the largest number of edges HH can have: at most mps⁡(Gi)\operatorname{mps}(G_i) from each source GiG_i, plus the ∣M∣|M| coupling edges. Since HH has exactly that many edges, it contains all coupling edges and mps⁡(Gi)\operatorname{mps}(G_i) edges from every source. Thus, every Hi=H∩GiH_i=H\cap G_i is a maximum planar subgraph of GiG_i, and H=(⋃iHi)+MH=(\bigcup_iH_i)+M is the required planar graph. □

Lemma 3 (Boundary order matching). Let W1W_1 and W2W_2 be outer face boundary walks of two vertex-disjoint planar graphs. After fixing a starting vertex and traversal direction in each walk, enumerate their vertex occurrences as

Wi=(w0i,…,wℓi−1i),i∈{1,2},W_i=(w^i_0,\ldots,w^i_{\ell_i-1}),\qquad i\in\{1,2\},

where ℓi\ell_i is the number of vertex occurrences in one traversal, excluding the final repetition of the starting vertex. Let 1≤q≤min⁡{ℓ1,ℓ2}1\le q\le\min\{\ell_1,\ell_2\}, and choose indices

0≤α1<⋯<αq<ℓ1and0≤β1<⋯<βq<ℓ2,0\le\alpha_1<\cdots<\alpha_q<\ell_1\qquad\text{and}\qquad0\le\beta_1<\cdots<\beta_q<\ell_2,

i.e., some vertices may be skipped, but their order along each boundary walk must be preserved. Suppose the vertices aj=wαj1a_j=w^1_{\alpha_j} are distinct and the vertices bj=wβj2b_j=w^2_{\beta_j} are distinct, i.e., at most one occurrence of each vertex is selected from each boundary walk. Then the matching

M={ajbj:j=1,…,q}M=\{a_jb_j:j=1,\ldots,q\}

is noncrossing.

Proof. We insert the matching edges ej=(aj,bj)e_j=(a_j,b_j) in order. An endpoint is called unused until its matching edge is inserted; its position on the boundary walk is the one specified by the selected index, which may skip some intermediate nodes (e.g., because they are visited multiple times in the boundary walk). Draw the two graphs disjointly with the chosen outer face nodes incident to the common outer face. Observe that an edge can always be added without introducing crossings if its endpoints are incident to the same face of a planar embedding. For q≥2q \ge2, we may need to mirror one drawing so that, after inserting e1e_1, the unused endpoints occur along the outer face boundary in the order a2,…,aq,bq,…,b2a_2,\ldots,a_q,b_q,\ldots,b_2. Thus, the first edge e1=a1b1e_1=a_1b_1 can be drawn through the common outer face without crossings. The induced face boundary walk becomes longer, traversing the new edge twice. For q=1q=1, the construction is complete after adding e1e_1.

Inductively, suppose that e1,…,eje_1,\ldots,e_j have been inserted without crossings, where 1≤j<q1 \le j < q, and that the current graph has a face with a boundary walk that contains the unused endpoints in the order

aj+1,…,aq,bq,…,bj+1a_{j+1},\ldots,a_q,b_q,\ldots,b_{j+1}

possibly with intermediate vertices skipped according to the chosen indices, and the first edge e1e_1 and previously added edge eje_j. We add the next edge ej+1=aj+1bj+1e_{j+1}=a_{j+1}b_{j+1}. By construction, both aj+1a_{j+1} and bj+1b_{j+1} are incident with the same face of the current graph, and ej+1e_{j+1} is noncrossing. The new edge connects the first and last unused endpoints in the displayed order. One resulting face is bounded by eje_j and ej+1e_{j+1} with their endpoints, and other edges and vertices. The other resulting face contains all remaining unused endpoints on its boundary in the same relative order. Thus the induction hypothesis holds for j+1j+1 whenever unused endpoints remain; after inserting eqe_q, the matching is complete without crossings. □

The same principle applies when more than two source graphs are composed sequentially. For r≥2r \ge2, let CrC_r denote the composite obtained after the r−1r-1 joins of G1,…,GrG_1,\ldots,G_r with coupling edge sets M2,…,MrM_2,\ldots,M_r.

Corollary 1 (Sequential composition). Let C1=G1C_1=G_1 and choose a maximum planar subgraph H1C⊆C1H_1^C \subseteq C_1. Then, compose with G2,…,GpG_2,\ldots,G_p one at a time, with Cr=(Cr−1∪Gr)+MrC_r=(C_{r-1}\cup G_r)+M_r. At step rr, let HrG⊆GrH_r^G \subseteq G_r be a maximum planar subgraph and let MrM_r be a noncrossing matching between distinct vertices incident with chosen faces of planar embeddings of Hr−1CH_{r-1}^C and HrGH_r^G. If HrC=Hr−1C∪HrG∪MrH_r^C=H_{r-1}^C\cup H_r^G\cup M_r is retained for the next step, then the final composite CpC_p satisfies

sk⁡(Cp)=∑i=1psk⁡(Gi).\operatorname{sk}(C_p)=\sum_{i=1}^{p}\operatorname{sk}(G_i).

Proof. For the base case r=1r=1, we have C1=G1C_1=G_1, the chosen subgraph H1CH_1^C is maximum planar, and sk⁡(C1)=sk⁡(G1)\operatorname{sk}(C_1)=\operatorname{sk}(G_1).

For the induction step, let 2≤r≤p2 \le r \le p and assume that Hr−1CH_{r-1}^C is a maximum planar subgraph of Cr−1C_{r-1} and that

sk⁡(Cr−1)=∑i=1r−1sk⁡(Gi).\operatorname{sk}(C_{r-1})=\sum_{i=1}^{r-1}\operatorname{sk}(G_i).

The noncrossing matching MrM_r makes HrC=Hr−1C∪HrG∪MrH_r^C=H_{r-1}^C\cup H_r^G\cup M_r planar. Applying Lemma 2 to Cr−1C_{r-1} and GrG_r therefore gives

sk⁡(Cr)=sk⁡(Cr−1)+sk⁡(Gr)=∑i=1rsk⁡(Gi).\operatorname{sk}(C_r)=\operatorname{sk}(C_{r-1})+\operatorname{sk}(G_r)=\sum_{i=1}^{r}\operatorname{sk}(G_i).

The forward direction in the proof of Lemma 2 also shows that HrCH_r^C is a maximum planar subgraph of CrC_r. Thus both induction claims hold for rr, and setting r=pr=p proves the result. □

Writing M=⋃r=2pMrM=\bigcup_{r=2}^{p}M_r for the set of all coupling edges, Lemma 1 shows that the additional skewness sk⁡(C)−∑isk⁡(Gi)\operatorname{sk}(C)-\sum_i\operatorname{sk}(G_i) of a sequential composition of pp subgraphs lies between 00 and ∣M∣−(p−1)|M|-(p-1). By Corollary 1, it is zero (no skewness is added) if each join uses a noncrossing matching between vertices on chosen faces of maximum planar subgraphs. Figure 2b illustrates such a join.

Suppose instead that only planar subgraphs Hi′⊆GiH'_i \subseteq G_i, not necessarily maximum, are available. Maintaining these planar subgraphs and using a noncrossing matching at every sequential composition step keeps their union with the coupling edges planar, by the same induction as in Corollary 1. The added skewness is bounded by the sum of the differences in edge counts between maximum planar subgraphs of GiG_i and the chosen subgraphs Hi′H'_i.

Lemma 4 (Skewness bound for non-maximum planar subgraphs). If Hi′⊆GiH'_i \subseteq G_i are planar subgraphs for which (⋃i=1pHi′)+M(\bigcup_{i=1}^{p} H'_i) + M is planar, then

∑i=1psk⁡(Gi)≤sk⁡(C)≤∑i=1psk⁡(Gi)+∑i=1p(mps⁡(Gi)−∣E(Hi′)∣).\sum_{i=1}^{p} \operatorname{sk}(G_i) \le\operatorname{sk}(C) \le\sum_{i=1}^{p} \operatorname{sk}(G_i) + \sum_{i=1}^{p} \left(\operatorname{mps}(G_i)-|E(H'_i)|\right).

Proof. The lower bound is Lemma 1, which holds for any set of coupling edges. For the upper bound, consider the combined graph consisting of the (non-maximum) planar subgraphs together with the coupling edges, (⋃iHi′)+M(\bigcup_i H'_i)+M. It is planar by hypothesis and has ∑i∣E(Hi′)∣+∣M∣\sum_i |E(H'_i)|+|M| edges. This gives mps⁡(C)≥∑i∣E(Hi′)∣+∣M∣\operatorname{mps}(C) \ge\sum_i |E(H'_i)|+|M|. Since ∣E(C)∣=∑i∣E(Gi)∣+∣M∣|E(C)|=\sum_i |E(G_i)|+|M|, the ∣M∣|M| terms cancel out, giving

sk⁡(C)=∣E(C)∣−mps⁡(C)≤∑i(∣E(Gi)∣−∣E(Hi′)∣)=∑i(∣E(Gi)∣−mps⁡(Gi))+∑i(mps⁡(Gi)−∣E(Hi′)∣)=∑isk⁡(Gi)+∑i(mps⁡(Gi)−∣E(Hi′)∣).\begin{aligned} \operatorname{sk}(C) &= |E(C)|-\operatorname{mps}(C) \\ &\le\sum_i \left(|E(G_i)|-|E(H'_i)|\right) \\ &= \sum_i \left(|E(G_i)|-\operatorname{mps}(G_i)\right) + \sum_i \left(\operatorname{mps}(G_i)-|E(H'_i)|\right) \\ &= \sum_i \operatorname{sk}(G_i) + \sum_i \left(\operatorname{mps}(G_i)-|E(H'_i)|\right). \end{aligned}

The additional skewness above the lower bound is thus at most the sum of the missing edge set cardinalities of the chosen subgraphs, ∑i(mps⁡(Gi)−∣E(Hi′)∣)\sum_i \left(\operatorname{mps}(G_i)-|E(H'_i)|\right), and this upper bound is zero when each Hi′H'_i is a maximum planar subgraph, yielding Lemma 2.

Structural properties of composite graphs

We identify which structural properties of the original graphs remain unchanged and bound how much others can change under composition.

Proposition 1 (Structural effects of composition). Let C=(⋃˙i=1pGi)+MC=(\mathbin{\dot{\bigcup}}_{i=1}^{p}G_i)+M be the composite graph. For v∈V(C)v\in V(C), let dM(v)d_M(v) be the number of coupling edges incident with vv, let B={v∈V(C):dM(v)>0}B=\{v\in V(C):d_M(v)>0\} be the set of merge vertices, and let Δ(M)=max⁡vdM(v)\Delta(M)=\max_v d_M(v). For (iv), additionally assume the sequential construction C1=G1C_1=G_1 and Cr=(Cr−1∪˙Gr)+MrC_r=(C_{r-1}\mathbin{\dot{\cup}}G_r)+M_r, where each MrM_r is a matching between V(Cr−1)V(C_{r-1}) and V(Gr)V(G_r). Then the following hold:

(i) ∣V(C)∣=∑i∣V(Gi)∣|V(C)|=\sum_i |V(G_i)| and ∣E(C)∣=∑i∣E(Gi)∣+∣M∣|E(C)|=\sum_i |E(G_i)|+|M|.

(ii) Let

psrc(q)=1∣V(C)∣∑i∣V(Gi)∣pGi(q)p_{\mathrm{src}}(q)=\frac{1}{|V(C)|}\sum_i |V(G_i)|p_{G_i}(q)

be the degree distribution of the disjoint source graphs before composition. Then, for every qq,

∣pC(q)−psrc(q)∣≤∣B∣∣V(C)∣,|p_C(q)-p_{\mathrm{src}}(q)|\le\frac{|B|}{|V(C)|},

i.e., for any degree qq, the fraction of degree-qq vertices changes by at most the fraction of merge vertices.

(iii) The maximum degree satisfies

max⁡{max⁡iΔ(Gi),Δ(M)}≤Δ(C)≤max⁡iΔ(Gi)+Δ(M),\max\left\{\max_i \Delta(G_i), \Delta(M)\right\} \le\Delta(C) \le\max_i \Delta(G_i) + \Delta(M),

i.e., composition cannot reduce the largest source maximum degree and can increase it by at most the maximum coupling degree.

(iv) Any vertex v∉Bv \notin B satisfies cC(v)=cGi(v)c_C(v) = c_{G_i}(v). Let

c‾src=1∣V(C)∣∑i∣V(Gi)∣c‾(Gi)\overline{c}_{\mathrm{src}} = \frac{1}{|V(C)|} \sum_i |V(G_i)| \overline{c}(G_i)

be the average clustering coefficient over all source graphs before composition. Then

0≤c‾src−c‾(C)≤∣B∣∣V(C)∣,0 \le\overline{c}_{\mathrm{src}} - \overline{c}(C) \le\frac{|B|}{|V(C)|},

i.e., the average clustering coefficient can decrease by at most the fraction of merge vertices.

Proof. The source graphs are vertex-disjoint and MM adds exactly ∣M∣|M| edges, proving (i). For v∈V(Gi)v \in V(G_i), counting its source and coupling edges gives dC(v)=dGi(v)+dM(v)d_C(v) = d_{G_i}(v) + d_M(v). Only the vertices in BB change degree; hence, for each qq, at most ∣B∣|B| vertices switch their degree-qq class, proving the bound on pC(q)p_C(q) in (ii). Taking maxima in the degree identity gives (iii). If v∉Bv \notin B, its neighborhood is unchanged, so cC(v)=cGi(v)c_C(v) = c_{G_i}(v).

Suppose a triangle meets multiple source graphs, and let rr be the largest index for which it meets GrG_r. Irrespective of whether it has one or two vertices in GrG_r, the two edges between GrG_r and earlier source graphs are contained in MrM_r and share an endpoint, contradicting that MrM_r is a matching. Thus no triangle in CC contains a coupling edge. Therefore, composition leaves the number of triangles through each vertex unchanged while its degree can only increase, so cC(v)≤cGi(v)c_C(v) \le c_{G_i}(v). Since equality holds outside BB and all clustering coefficients lie in [0,1][0,1], averaging proves (iv).

Maintaining feasibility through cut flow compensation

When extracting subinstances from a network flow instance, the nodes incident to cut edges lose flow contributions from the removed edges. This can make the subinstance infeasible, and make it more difficult for the composed instance to be feasible.

We apply cut flow compensation, adding the flow that previously crossed the cut to the supply at each node. For ordinary network flow instances satisfying the hypotheses of Proposition 2, cut flow compensation is sufficient to maintain feasibility for Tract on the subinstance. The final composed instance remains feasible for Tract as well if assigning zero flow to all coupling edges satisfies their bounds and all additional constraints.

Let N′N' be induced by V′⊆VV' \subseteq V, with E′=E∩(V′×V′)E' = E \cap(V' \times V'), and let f‾k\overline{f}_k be the flows from a feasible solution of Tract(N)(N). For v∈V′v \in V' and k∈Kk \in K, the cut flow compensation is vv’s net flow across the cut,

Δsk(v)=∑(u,v)∈Eu∉V′f‾k(u,v)−∑(v,w)∈Ew∉V′f‾k(v,w),(1)\Delta s_k(v) = \sum_{\substack{(u,v)\in E\\u\notin V'}} \overline{f}_k(u,v) - \sum_{\substack{(v,w)\in E\\w\notin V'}} \overline{f}_k(v,w), \tag*{(1)}

which can be positive or negative.

Proposition 2 (Cut flow compensation). Let xˉ\bar{x} be a feasible solution for Tract⁡(N)\operatorname{Tract}(\mathcal{N}), with realized flows fˉk\bar{f}_k and supplies sˉk\bar{s}_k, and let Δsk\Delta s_k be given by (1). For every v∈V′v \in V' and k∈Kk \in K, shift the supply limits in N′\mathcal{N}' either to Sk1(v)+Δsk(v)S_{k1}(v) + \Delta s_k(v) and Sk2(v)+Δsk(v)S_{k2}(v) + \Delta s_k(v) (fixed compensation), or to Sk1(v)+min⁡{0,Δsk(v)}S_{k1}(v) + \min\{0,\Delta s_k(v)\} and Sk2(v)+max⁡{0,Δsk(v)}S_{k2}(v) + \max\{0,\Delta s_k(v)\} (variable compensation). Suppose that every constraint of Tract⁡(N′)\operatorname{Tract}(\mathcal{N}') other than flow conservation and supply limits is satisfied by the restriction of xˉ\bar{x} together with the compensated supplies. Then this restriction, with realized supplies sˉk(v)+Δsk(v)\bar{s}_k(v) + \Delta s_k(v), is feasible for Tract⁡(N′)\operatorname{Tract}(\mathcal{N}').

Proof. For every v∈V′v \in V' and k∈Kk \in K, feasibility of xˉ\bar{x} in N\mathcal{N} gives

∑(v,w)∈Efˉk(v,w)=∑(u,v)∈Efˉk(u,v)+sˉk(v).\sum_{(v,w)\in E} \bar{f}_k(v,w) = \sum_{(u,v)\in E} \bar{f}_k(u,v) + \bar{s}_k(v).

Separating internal and cut edges and rearranging yields

∑(v,w)∈E′fˉk(v,w)=∑(u,v)∈E′fˉk(u,v)+sˉk(v)+Δsk(v).\sum_{(v,w)\in E'} \bar{f}_k(v,w) = \sum_{(u,v)\in E'} \bar{f}_k(u,v) + \bar{s}_k(v) + \Delta s_k(v).

Thus the restricted solution satisfies flow conservation with the compensated supplies. Since sˉk(v)∈[Sk1(v),Sk2(v)]\bar{s}_k(v) \in[S_{k1}(v), S_{k2}(v)], the compensated supplies lie within the shifted limits for both compensations, and the hypothesis covers all remaining constraints.

The above proposition guarantees feasibility of the subinstance under its hypotheses, but does not by itself guarantee feasibility of the composed instance, because additional constraints may be imposed on endpoints of coupling edges. For example, in potential-based flow problems, each node vv has a continuous potential πv\pi_v, and the flow on an edge is determined by the difference between the potentials at its endpoints and the edge parameters. Coupling edges may therefore transfer additional flow between subinstances, possibly exceeding limits even when each subinstance is feasible on its own. Here, an additional offset in the potential difference constraints can repair possible infeasibilities of the composite.

Corollary 2 (Angle compensation in affine potential-based flow problems). Consider network instances Ni\mathcal{N}_i and Nj\mathcal{N}_j on disjoint node sets ViV_i and VjV_j, with node potentials πˉi\bar{\pi}^{i} and πˉj\bar{\pi}^{j} from feasible Tract⁡\operatorname{Tract} solutions (see Proposition 2). Let MM be a set of coupling edges between the instances. Each e=(u,v)∈Me=(u,v)\in M connects u∈Viu\in V_i to v∈Vjv\in V_j with i≠ji\ne j. Suppose the flow of each edge e∈Me\in M is defined by

fe=ae(πu−πv−ϕe),ae>0.f_e = a_e(\pi_u-\pi_v-\phi_e), \qquad a_e>0.

For each such edge, let ϕebefore\phi_e^{\mathrm{before}} be its offset before compensation, taking ϕebefore=0\phi_e^{\mathrm{before}}=0 if none exists, and set

ψe:=πˉui−πˉvj−ϕebefore,ϕe:=ϕebefore+ψe.\psi_e := \bar{\pi}^{i}_u-\bar{\pi}^{j}_v-\phi_e^{\mathrm{before}}, \qquad\phi_e := \phi_e^{\mathrm{before}}+\psi_e.

Suppose that, for every e∈Me\in M, this offset is admissible and the edge bounds allow fe=0f_e=0. If no other constraint introduced with $e excludes these values, then the constituent solutions extend to a feasible solution for Tract⁡\operatorname{Tract} on the composed instance after adding any number of such edges.

Proof. Retain the constituent solutions and use the offsets above. For every e=(u,v)∈Me=(u,v)\in M with u∈Viu\in V_i and v∈Vjv\in V_j, we obtain

fe=ae(πˉui−πˉvj−(ϕebefore+ψe))=ae(πˉui−πˉvj−(πˉui−πˉvj))=0.\begin{aligned} f_e &= a_e\left(\bar{\pi}^{i}_u-\bar{\pi}^{j}_v-\left(\phi_e^{\mathrm{before}}+\psi_e\right)\right)\\ &= a_e\left(\bar{\pi}^{i}_u-\bar{\pi}^{j}_v-\left(\bar{\pi}^{i}_u-\bar{\pi}^{j}_v\right)\right)=0. \end{aligned}

The zero coupling flows preserve the node balances, and all other existing constraints remain satisfied. The hypotheses ensure that the offset restrictions, edge bounds, and remaining new constraints are satisfied as well.

As with variable supply compensation, ψe\psi_e may vary between 0 (no angle difference compensation) and πˉu−πˉv−ϕebefore\bar{\pi}_u-\bar{\pi}_v-\phi_e^{\mathrm{before}} (full compensation, no exchange between networks required), since this range contains the value used in the proof.

Extensions of this corollary to other network flow problems may be possible in similar ways. Note that the compensation of subinstances to make them self-contained may lead to decreased difficulty of the composite, an issue we examine in § 7.4.

Security-constrained optimal transmission switching

As one of two instantiations, we consider SCOTS under the linear DC approximation [39] (Donkiewicz et al. 2026). SCOTS extends SCOPF by adding topology switching. The topological action limit ZZ bounds the number of transmission branches whose status may be changed. SCOPF is the special case with Z=0Z=0, in which the network topology is fixed. The contingency set C\mathcal{C} contains sets CC of failed branches. The base case C=∅C=\emptyset has no branch failures. A branch overload variable is a nonnegative slack variable by which a transmission line may exceed its thermal limit, at a penalty in the objective. Here, redispatch cost is the cost of changing generator outputs from a prescribed reference dispatch.

SCOTS
Instance.A power system graph G(N)=(V,E)G(\mathcal{N})=(V,E), fixed loads DvD_v and generation bounds Gv,GˉvG_v,\bar{G}_v for v∈Vv\in V, generation costs, line parameters and operating limits, contingencies C\mathcal{C} including the base case, and a topological action limit ZZ.
Feasible solution.Generation gvg_v, voltage angles θvC\theta_v^C, line flows x(u,v)Cx_{(u,v)}^C, branch status decisions z(u,v)z_{(u,v)} and nonnegative branch overload variables o(u,v)Co_{(u,v)}^C satisfying the topological action limit, nodal balance, Kirchhoff voltage laws, generation limits and the relaxed thermal constraints for every C∈CC\in\mathcal{C}.
Objective.Minimize redispatch costs and branch overload penalties.

Table 3.7.

This specialization has a single commodity, so we omit the commodity index. The net supply at node vv is s(v)=gv−Dvs(v)=g_v-D_v. The generation bounds and fixed demands determine the supply limits in SS. PP contains the thermal limits and the remaining physical and cost parameters.

Here, Opt\mathrm{Opt} is the DC-SCOTS variant stated by Donkiewicz et al. (2026). We refer to that paper for the full mathematical formulation and solution method. Branch overload is penalized rather than prohibited, so a feasible solution need not be free of overload. Our feasibility check Tract\mathrm{Tract} is a DC-OPF (without contingencies) problem with fixed original topology and strict branch limits. The subinstances are feasible for Tract\mathrm{Tract} by Proposition 2. The composite’s feasibility for Tract\mathrm{Tract} may be guaranteed by Corollary 2, since DC power flow problems are potential-based flows with voltage angles θv\theta_v corresponding to the node potentials πv\pi_v.

Survivable network design

Our second instantiation is SND, represented as capacitated modular multicommodity network design [66, 33], using the formulation of Donkiewicz (2026). A capacity module is one discrete unit of capacity that can be installed on an edge at a specified cost; several modules may be installed on the same edge. The contingency set C\mathcal{C} contains subsets C⊆EC\subseteq E specifying the failed edges and includes the base case ∅\emptyset. Instance. A graph G(N)=(V,E)G(\mathcal{N})=(V,E), commodities d∈Kd \in K with source odo_d, sink tdt_d and demand bd>0b_d > 0, available module types with their capacities and installation costs on each edge e∈Ee \in E, and contingencies C\mathcal{C} including the base case.

Feasible solution. Module counts ye,m∈Z≥0y_{e,m} \in\mathbb{Z}_{\ge0} for each edge e∈Ee \in E and available module type mm, and commodity flows fC,df_{\mathcal{C},d} for C∈CC \in\mathcal{C} and d∈Kd \in K, satisfying the demands and shared edge capacities, with zero flow on failed edges.

Objective. Minimize capacity installation cost.

For each commodity dd, the supply limits in S\mathcal{S} are fixed to bdb_d at odo_d, −bd-b_d at tdt_d, and zero elsewhere. P\mathcal{P} contains the installed capacities and routing costs. All commodities and both directions share the capacity installed on each edge.

Here, OPT is SND, while TRACT is a minimum-cost multicommodity flow problem with continuous flows, capacities fixed during preprocessing, and no failures. After cut flow compensation (Proposition 2), assigning zero flow to the coupling edges gives a feasible solution for TRACT on the composite. Coupling edges may carry flow if routing through another source network is cheaper. To introduce demands between source networks, new demands between nodes of both source networks can be added. In this case, feasibility must be checked again.

Composition Algorithm

We produce a network instance N⋆\mathcal{N}^{\star} in six stages, followed by a feasibility check. The algorithm draws s≥2s \ge2 source instances feasible for TRACT from a preprocessed library, extracts a connected subinstance from each, compensates the flow on removed cut edges, selects merge vertices, and adds coupling edges between them to join the subinstances. We describe the algorithm using the terminology of the abstract network instance of Section 3.1. Because the merge vertices for each join are selected on the growing composite CrC_r, the joins are performed sequentially.

Source selection. The library N\mathcal{N} is preprocessed once. An application may first restrict it using a declared Boolean filter function h:N→{0,1}h:\mathcal{N}\to\{0,1\}, where h(N)=1h(\mathcal{N})=1 means that N\mathcal{N} is eligible. For example, hh may select supported data features by filtering on P\mathcal{P} or a size range by filtering on ∣V∣|V|. By default, we use the Euler bound on the underlying simple graph as a density filter, although violating it does not imply high skewness. We exclude sources violating the bound before solving TRACT for all remaining instances, and the feasible ones with their solutions form the sampling pool

L={N∈N:h(N)=1, ∣V∣≥3, ∣E∣≤3∣V∣−6,TRACT⁡(N) is feasible}.\mathcal{L}=\left\{\mathcal{N}\in\mathcal{N}: \begin{aligned} &h(\mathcal{N})=1,\ |V|\ge3,\ |E|\le3|V|-6,\\ &\operatorname{TRACT}(\mathcal{N})\text{ is feasible} \end{aligned}\right\}.

For each generation attempt, we sample a number of sources ss from the integers in [smin⁡,smax⁡][s_{\min},s_{\max}], where smin⁡≥2s_{\min}\ge2. We then draw the ss sources Ni\mathcal{N}_i, i∈{1,…,s}i\in\{1,\ldots,s\}, independently and uniformly from L\mathcal{L} with replacement, relabeling if necessary to make all node sets disjoint. The stored solution provides a flow fi(e,k)f_i(e,k) for every edge e∈Eie\in E_i and commodity k∈Kik\in K_i for the subsequent cut flow compensation.

Subgraph extraction. For each requested instance N⋆\mathcal{N}^{\star}, a target size TT is drawn uniformly at random from the integers in [Tmin⁡,Tmax⁡][T_{\min},T_{\max}]. The parameters 0≤fmin⁡≤fmax⁡≤10\le f_{\min}\le f_{\max}\le1 give lower and upper bounds on the fraction of vertices retained from each source. Each subinstance size tit_i must be an integer in [max⁡{3,⌈fmin⁡∣Vi∣⌉},⌈fmax⁡∣Vi∣⌉][\max\{3,\lceil f_{\min}|V_i|\rceil\},\lceil f_{\max}|V_i|\rceil]. If the selected sources cannot together provide exactly TT vertices within these bounds, we redraw the sources. We then process the sources in random order, drawing each size uniformly from the values that leave a feasible allocation of the remaining target to the remaining sources. The last source receives the remainder, ensuring ∑i=1sti=T\sum_{i=1}^{s} t_i = T. Each instance is then reduced to a connected subgraph with Vi′⊆ViV_i' \subseteq V_i and ∣Vi′∣=ti|V_i'| = t_i by a randomized breadth-first search from a uniformly sampled starting node. The induced instance Ni′N_i' inherits all node and edge attributes from NiN_i. For the later cut flow compensation, the cut edges δ(Vi′)={(u,v)∈Ei:∣{u,v}∩Vi′∣=1}\delta(V_i') = \{(u,v) \in E_i : |\{u,v\} \cap V_i'| = 1\} are recorded.

Cut flow compensation. Using the stored solution fif_i, we compute the net cut flow Δsk(v)\Delta s_k(v) from (1) for each retained node vv incident to a cut edge and each commodity kk. We adjust the supply bounds using fixed or variable compensation as defined in Proposition 2, with the choices for each application specified in § 7.1. When nodes incident to cut edges also become merge vertices, variable compensation can reduce flows on the coupling edges and nearby edges. We denote the compensated subinstance by Ni′N_i' and its underlying graph by Gi=G(Ni′)G_i = G(N_i').

Merge vertex selection. At join r∈{2,…,s}r \in\{2,\ldots,s\}, the current composite Cr−1C_{r-1} is joined with the next extracted graph GrG_r. Let

nr=min⁡{∣V(Cr−1)∣,∣V(Gr)∣}.n_r = \min\{|V(C_{r-1})|, |V(G_r)|\}.

We request

qr=max⁡{3,⌈log⁡2nr⌉}q_r = \max\{3, \lceil\log_2 n_r \rceil\}

merge vertex pairs.

We use at least three coupling edges to provide multiple connections between the subinstances. The logarithmic term gives larger subgraphs more connections with a reasonable growth rate. Each method produces candidate sets Rr−1⊆V(Cr−1)R_{r-1} \subseteq V(C_{r-1}) and Rr⊆V(Gr)R_r \subseteq V(G_r). We select qrq_r merge vertex pairs (a1,b1),…,(aqr,bqr)∈Rr−1×Rr(a_1,b_1),\ldots,(a_{q_r},b_{q_r}) \in R_{r-1} \times R_r so that no vertex occurs in more than one pair, redrawing sources if ∣Rr−1∣<qr|R_{r-1}| < q_r or ∣Rr∣<qr|R_r| < q_r. We compare four merge vertex selection methods:

a) random (R): sample qrq_r distinct vertices uniformly from each graph; pair in sampling order;

b) high-degree (HD): take the qrq_r highest-degree vertices of each graph; pair in descending order;

c) Kamada–Kawai (KK): compute a two-dimensional layout whose vertex positions reflect graph distances, take the vertices on the boundary of the convex hull of each layout as candidates, place the layouts side by side and greedily select the shortest cross-graph pairs without reusing a vertex;

d) outer face (OF): compute and embed a planar subgraph of each graph (heuristically or using branch-and-cut, see § 5). Choose a face with the most distinct incident vertices as the outer face. Starting at a random vertex on each outer face, select qrq_r consecutive vertices in the boundary order from § 4.4 and pair them in order. By Lemma 3, the resulting matching is noncrossing.

For a graph with n=∣V∣n = |V| vertices and m=∣E∣m = |E| edges, random candidates can be selected in O(n)O(n) time ([75]) and high-degree candidates in O(n+m)O(n+m) time ([9]). The classical Kamada–Kawai method takes O(n3+IKKn)O(n^3 + I_{\mathrm{KK}}n) time, where IKKI_{\mathrm{KK}} is the total number of desired updates (improvements) to the vertex positions ([48], § 4.3). Once a planar subgraph has been computed, a planar embedding and the boundary walks of its faces can be computed in O(n+m)O(n+m) time ([12]). Computing a maximum planar subgraph, by contrast, is NP-hard ((Yannakakis, 1978)).

Sequential composition. Let Ir\mathcal{I}_r denote the composite instance after joining the first rr subinstances, with I1=N1′\mathcal{I}_1 = N_1' and Cr=G(Ir)C_r = G(\mathcal{I}_r). At join rr, we obtain Ir\mathcal{I}_r by adding the coupling edges MrM_r between Ir−1\mathcal{I}_{r-1} and Nr′N_r', one for each selected merge vertex pair. For the outer face method with maximum planar subgraphs, Lemma 2 and Corollary 1 guarantee that no join adds skewness. Lemma 4 bounds the added skewness when the planar subgraphs are not maximum.

The resulting instance N⋆=IS\mathcal{N}^{\star} = \mathcal{I}_{S} inherits the supplies, demands, capacities and other parameters of the extracted instances. Only the new coupling edges require additional edge parameters, which are specified for each application.

Instance normalization. Two source instances may have parameters (e.g., capacity or supply/demand values) measured on different scales. After the final join, an optional, problem-specific transformation can normalize these attributes without changing the topology or the selected merge vertices. It should not alter relative parameter values within one network, but only the scale of those values between composed networks. There is no universal normalization for the abstract model.

Feasibility check. Although cut flow compensation preserves the feasibility of extracted subinstances under the hypotheses of Proposition 2, composing feasible subinstances need not preserve feasibility when the hypotheses of neither Proposition 2 nor Corollary 2 hold. The feasibility check solves Tract⁡(N⋆)\operatorname{Tract}(\mathcal{N}^{\star}) after composition, discarding the attempt unless a feasible solution is found. For each requested output, the algorithm makes at most Amax⁡A_{\max} attempts and reports failure if none succeeds.

Planarization algorithm

We compute planar subgraphs using either a heuristic (OF-H) or branch-and-cut (OF-B) from the Open Graph Drawing Framework (OGDF) (Chimani et al., [21]), augmented by two additions: valid inequalities derived from the Euler bound, and the reuse of planar subgraphs and skewness bounds in subsequent joins. In both OF-H and OF-B, planarization is performed separately on the graph’s blocks, that is, its maximal connected subgraphs that remain connected after deleting any one vertex. A bridge (an edge whose removal disconnects the graph) forms a block of two vertices. Planar blocks are retained without deleting edges. The implementations, solver settings, and resource limits are specified in § 7.1.

Euler inequalities. A simple planar graph on n≥3n \ge3 vertices has at most 3n−63n - 6 edges, or 2n−42n - 4 if it contains no triangle (i.e., c(n−2)c(n - 2) with c=3c = 3 or c=2c = 2, respectively). Thus, a subgraph exceeding the applicable bound requires edge deletions. For S⊆VS \subseteq V with ∣S∣≥3\lvert S\rvert\ge3, let FF be the set of edges with both endpoints in SS. We use the subgraph Euler inequalities (Chimani and Wiedera, [20], § 4)

∑e∈Fxe≥∣F∣−c(∣S∣−2),\sum_{e \in F} x_e \ge\lvert F\rvert- c(\lvert S\rvert- 2),

where xe∈{0,1}x_e \in\{0,1\} indicates whether edge ee is deleted. The choice c=3c = 3 is always valid, and c=2c = 2 is valid when no triangle has all three vertices in SS. To find useful subsets, we adapt the vertex removal procedure of (Charikar, [17]): starting with each nonplanar block, we repeatedly remove a vertex of minimum current degree until three remain. We evaluate the right-hand side on the initial vertex set and after each removal, using c=3c = 3 and, whenever no triangles remain, also c=2c = 2. For each choice of cc, we retain a subset maximizing the right-hand side ∣F∣−c(∣S∣−2)\lvert F\rvert- c(\lvert S\rvert- 2) along this removal sequence, provided the maximum is positive. In OF-B, the resulting at most two inequalities per block are added as constraints to the initial formulation, while in OF-H they are used only as lower bounds.

Reusing planar subgraphs and bounds across joins. Since we compose the graphs sequentially, we can reuse planar subgraphs and bounds from earlier joins. Let Hr−1rH^{r}_{r-1} and HrGH^{G}_{r} be the selected planar subgraphs of Cr−1C_{r-1} and GrG_r. Their OF join Hr=(Hr−1r∪HrG)+MrH_r = (H^{r}_{r-1} \cup H^{G}_{r}) + M_r is planar by Lemma 3 even if the selected subgraphs are not maximum. In both OF-B and OF-H, we compare HrH_r with a fresh heuristic solution and retain the one with more edges. For OF-H, this is the solution, and for OF-B, it is supplied as an initial feasible solution.

Let Lr−1CL^C_{r-1} and LrGL^G_r be the computed skewness lower bounds for Cr−1C_{r-1} and GrG_r. For the next planarization of CrC_r, it still holds that

∑e∈E(Cr−1)xe≥Lr−1C,∑e∈E(Gr)xe≥LrG.\sum_{e\in E(C_{r-1})} x_e \ge L^C_{r-1}, \qquad\sum_{e\in E(G_r)} x_e \ge L^G_r.

In OF-B, however, since we decompose the problem into blocks, each constraint is added only if its edge set lies entirely within a single block of CrC_r. Additionally, since Cr−1C_{r-1} and GrG_r have disjoint edge sets,

sk⁡(Cr)≥Lr−1C+LrG\operatorname{sk}(C_r) \ge L^C_{r-1} + L^G_r

always holds. If the available lower bound equals the number of edges omitted by the retained planar subgraph of CrC_r, optimality is proved and no exact solve is needed.

Computational Study

We generate instances from PGLib-OPF v23.07 ([1]) (commit dc6be4b) and SNDlib ([66]). We use size eligibility filters

hPGLib(N)={1,73≤∣V(G(N))∣≤2000,0,otherwise,h_{\mathrm{PGLib}}(\mathcal{N}) = \begin{cases} 1, & 73 \le|V(G(\mathcal{N}))| \le2000,\\ 0, & \text{otherwise,} \end{cases}
hSNDlib(N)={1,2∣K∣∣E(G(N))∣≤2,000,000,0,otherwise,h_{\mathrm{SNDlib}}(\mathcal{N}) = \begin{cases} 1, & 2|K||E(G(\mathcal{N}))| \le2{,}000{,}000,\\ 0, & \text{otherwise,} \end{cases}

where KK is the commodity set of N\mathcal{N} and 2∣K∣∣E(G(N))∣2|K||E(G(\mathcal{N}))| is the number of flow variables in TRACT\mathrm{TRACT} for SND. Table 2 summarizes the exclusions and resulting source pools.

LibraryInitial instancesExclusions∣L∣|\mathcal{L}|
EulerTRACT\mathrm{TRACT}hh
PGLib66014916
SNDlib2654116

Table 2. Source screening.

Source skewness. For 28 of the 32 sources, the bounds in Table 3a and Table 3b show that deleting at most 5 % of the edges suffices for planarity. SNDlib has consistently low skewness, whereas PGLib exhibits a wider range. Removing branches between different nominal voltage levels makes additional PGLib sources planar.

Source∣V∣|V|∣E∣|E|[s,sˉ][s,\bar{s}]sˉ/∣E∣\bar{s}/|E|[s′,sˉ′][s',\bar{s}']sˉ′/∣E′∣\bar{s}'/|E'|
case73_ieee_rts7310843.7%00.0%
case89_pegase89206[40, 55]≤26.7%\le26.7\%[31, 32]≤19.9%\le19.9\%
case118_ieee11817900.0%00.0%
case162_ieee_dtc162280[16, 30]≤10.7%\le10.7\%00.0%
case179_goc17922210.5%10.5%
case197_snem19722300.0%00.0%
case200_activ200245[1, 6]≤2.4%\le2.4\%10.6%
case240_pserc240348102.9%10.4%
case300_ieee30040992.2%20.7%
case500_goc500650[14, 18]≤2.8%\le2.8\%20.4%
case588_sdet588677[10, 13]≤1.9%\le1.9\%00.0%
case793_goc793904[11, 17]≤1.9%\le1.9\%20.3%
case1354_pegase13541710[24, 50]≤2.9%\le2.9\%[10, 11]≤0.7%\le0.7\%
case1888_rte18882308[25, 54]≤2.3%\le2.3\%[9, 10]≤0.6%\le0.6\%
case1951_rte19512375[26, 57]≤2.4%\le2.4\%100.5%
case2000_goc20002806[59, 225]≤8.0%\le8.0\%130.6%

Table 3. Source skewness intervals (single values are exact) and relative upper bounds in gray. Time limit: 24 h. PGLib: ss with all lines, s′s' without lines between voltage levels, and E′E' the remaining edge set. (a) PGLib

Experimental setup

Generation settings. For both applications, we compare five methods on the same 100 accepted inputs: random (R), high-degree (HD), Kamada–Kawai (KK), and outer face selection with either heuristic (OF-H) or branch-and-cut (OF-B) planarization. For each input, the extracted graphs, their order, and all random seeds are fixed across methods. We accept an input only if all five composites are feasible for TRACT\mathrm{TRACT}. Table 4 lists the generation settings.

SettingSymbolsPGLibSNDlib
Source networks[smin⁡,smax⁡][s_{\min},s_{\max}][2,5][2,5][2,5][2,5]
Retained vertex fraction[fmin⁡,fmax⁡][f_{\min},f_{\max}][0.15,0.85][0.15,0.85][0.15,0.85][0.15,0.85]
Target vertices[Tmin⁡,Tmax⁡][T_{\min},T_{\max}][100,1000][100,1000][12,100][12,100]
Maximum attemptsAmax⁡A_{\max}2525
Outer face vertex selectionConsecutiveConsecutive
Cut flow compensationVariableFixed

Table 4. Generation settings.

Source∣V∣|V|∣E∣|E|[s,sˉ][s,\bar{s}]sˉ/∣E∣\bar{s}/|E|
abilene121500.0%
atlanta152200.0%
cost266375700.0%
france254500.0%
geant223625.6%
germany50508822.3%
giul39398644.7%
india35358045.0%
janos-us-ca396100.0%
janos-us264200.0%
nobel-eu284100.0%
nobel-germany172600.0%
nobel-us142114.8%
norway275112.0%
sun275112.0%
zib54548000.0%

Table 3b. (b) SNDlib

For PGLib, the variable cut flow compensation is implemented using auxiliary generators with zero cost and additional loads. We refrain from using the additional voltage angle offsets proposed in Corollary 2. We define coupling edges as transformers with reactance 10−410^{-4} per unit, unlimited thermal capacity, tap ratio 1, and zero phase shift.

For SNDlib, we decompose flows from Tract into paths terminating at the original terminals or, if one of those was removed during subgraph extraction, at the boundary vertex they flowed through. Coupling edges have zero module, routing, and setup costs. Their module capacity equals the combined positive demand of the two subinstances.

Computational settings and measurements. We use OGDF version foxglove-202510, with the additions described in § 5. OF-H uses OGDF’s heuristic mode (PlanarSubgraphFast with its default ten runs). OF-B uses its exact mode (MaxCPlanarMaster with default settings), with the ABACUS (Jünger and Thelin, [47]) branch-and-cut solver and COIN-OR’s linear programming solver (Forrest et al., n.d.).

For PGLib, both Tract and Opt are solved using the exact SCOTS solver of Donkiewicz et al. (2026) with Gurobi 13.0.2. For SNDlib, we solve Tract using our own implementation with Gurobi 13.0.3 and Opt using the SND implementation of Donkiewicz (2026) with Gurobi 12.0.3.

We use compute nodes with eight physical cores (Intel Xeon L5630, 2.13 GHz) and at least 16 GB of memory. We use up to sixteen threads for heuristic planarization and one for branch-and-cut, Euler preprocessing, and application solves. Exact planarization is limited to 600 s per graph during generation and 3600 s for final evaluation, including initialization. Reported runtimes additionally include Euler preprocessing, solution and bound reuse, and the separate heuristic call before the exact solve in OF-B, all of which do not count towards the above limits.

For the final skewness evaluation, all five methods use the same known planar subgraphs of the original extracted subinstances and the same random seed, and also receive all applicable bounds from generation. To obtain an initial feasible solution, we join these subgraphs with all coupling edges if the result is planar, and otherwise with a minimal subset that connects the subinstances.

For nonnegative values z1,…,zNz_1,\ldots,z_N, we report the shifted geometric mean

exp⁡(1N∑i=1Nlog⁡(1+zi))−1.\exp\left(\frac{1}{N}\sum_{i=1}^{N}\log(1+z_i)\right)-1.

We use this mean for runtimes and skewness, and medians for structural summaries.

Effects of composition

Added skewness. We first consider the 14 PGLib and 88 SNDlib inputs for which added skewness is known exactly for all five methods. Both outer face variants add no skewness on these inputs (Figure 3). KK has more cases with zero added skewness than R or HD, but most of its composites still add skewness. Thus, selecting vertices on the boundary of a geometric layout does not by itself prevent added skewness.

Distribution of added skewness on PGLib and SNDlib inputs

Figure 3. Distribution of added skewness on inputs with exact added skewness values for all five methods. Within each method color, lighter shades indicate larger added skewness.

To include all 100 inputs per application, we compare upper bounds on added skewness relative to the number of coupling edges (Figure 4 and Table 5). Both outer face methods give substantially smaller upper bounds for PGLib. With OF-H and OF-B, the upper bound on added skewness is zero for 37 and 48 PGLib inputs and 98 and 100 SNDlib inputs, respectively, compared to at most three and 18 for any of the alternatives. The bounds show that OF-B adds strictly less skewness than R, HD, and KK on 45 PGLib inputs and 77 SNDlib inputs. Relative to OF-H, OF-B tightens the upper bound on 37 PGLib inputs and certifies strictly smaller added skewness on eight PGLib and two SNDlib inputs. Figure 5 shows five composites from the same four subinstances: OF-B preserves their total skewness of three, OF-H adds one, and R, HD, and KK each add at least three.

Distribution of upper bounds on normalized added skewness for PGLib and SNDlib

Figure 4. Distribution of upper bounds on normalized added skewness on all 100 final instances.

DomainMethodUCU_Ca‾\underline{a}a‾\overline{a}η‾\underline{\eta}η‾\overline{\eta}No added skewnessExact skewness
PGLibR21.5021.0149.6370.1080.677014
HD20.6171.1069.1280.1130.645016
KK17.6560.8616.9070.0820.513321
OF-H11.3770.0571.9280.0050.2133746
OF-B10.9160.0001.4540.0000.1764849
SNDlibR3.4792.8062.9170.2900.299890
HD3.1062.5422.5630.2590.2621096
KK2.2081.6451.6490.1750.1761899
OF-H0.5840.0140.0140.0010.00198100
OF-B0.5770.0000.0000.0000.000100100

Table 5. Skewness over 100 matched inputs per domain. First five numeric columns: shifted geometric mean bounds; last two: counts with a‾=0\overline{a}=0 and LC=UCL_C=U_C, respectively. Bold: our method.

Other structural characteristics. Figure 8 compares changes in the degree distribution, mean clustering, and maximum degree with the bounds from Proposition 1. For the degree distribution, we report the largest absolute change among the fractions of vertices in each degree class. HD attains the upper bound on the increase in maximum degree on about two thirds of the inputs, which is consistent with repeatedly selecting vertices of maximum degree. KK tends to select vertices of low degree (Figure 10), leaving the maximum degree almost unchanged. Its concentration on vertices of the same degree, particularly degree one in PGLib, explains the largest median change in degree frequencies relative to the bound. OF and R choose vertices across the degree distribution, yielding smaller median changes in degree frequencies than KK and smaller median increases in maximum degree than HD.

Structural changes that can be bounded for PGLib and SNDlib, showing degree distribution change, mean clustering, and maximum degree for R, HD, KK, OF-H, and OF-B

Figure 8. Structural changes that can be bounded (see Proposition 1). Points: composites; boxes: quartiles and median; whiskers: observations within 1.5 interquartile ranges (IQRs); dashed line: upper bound.

Degrees before each join for PGLib and SNDlib

Figure 10. Degrees before each join; 3,218 coupling edge endpoints per method for PGLib and 2,156 for SNDlib.

For all methods, median changes in mean clustering are small relative to the bound, indicating that the constituents’ local clustering changes little on average, even among the merge vertices.

Figure 9 compares diameter, algebraic connectivity, and degree assortativity. HD and R give smaller median diameters than KK and OF on the same inputs, suggesting that their choice of merge vertices provides shorter paths between subinstances.

Structural changes without general bounds for PGLib and SNDlib, showing diameter, algebraic connectivity, and degree assortativity

Figure 9. Structural changes without general bounds. Values centered at source medians and scaled by source IQRs. Shading: source quartiles; symmetric logarithmic axis, linear on [−1,1][-1, 1]. Boxplots as in Figure 8.

For PGLib, OF gives median algebraic connectivity closer to the source median than R and HD, whose medians lie above it. For SNDlib, all methods give medians below the source median, with the lowest values for OF suggesting slightly more pronounced bottlenecks between subinstances.

HD gives higher median degree assortativity than the other methods, particularly for PGLib, consistent with adding edges between high-degree vertices. OF keeps median degree assortativity within the source interquartile range, avoiding the pronounced shift in degree mixing observed for HD in PGLib and giving distributions similar to R and KK.

Generation and skewness evaluation time

Merge vertex selection dominates the generation time for OF on PGLib, where the higher skewness makes planarization more expensive (Figure 6). SNDlib instances have very low skewness and are cheaper to planarize, so feasibility checking for TrACT accounts for most of the generation time.

Shifted geometric means for PGLib and SNDlib

Figure 6. Shifted geometric means; 100 accepted inputs per method. Final skewness times include only exact cases. TO: runs reaching 3600 s in the skewness calculation on the composite.

OF-B takes roughly one hundred times the selection time of OF-H on PGLib, but little additional time on SNDlib. These results suggest that OF-H is often sufficient, while OF-B offers further improvements at little additional cost on instances as close to planar as those in SNDlib.

Final skewness evaluation reaches the time limit on most PGLib composites, even for OF, but certifies exact skewness for most SNDlib composites.

Optimization experiments

We solve OPT on the generated instances for both applications, using the problem definitions in § 4.7 and § 4.8.

For SCOTS, we set Z=1Z = 1, permit overload slack, and exclude single-line contingencies that disconnect the network. SCOPF warmstarting is enabled. For SND, the contingency set CC contains the base case and all single-edge failures under which all demand terminals remain in

(a) Random: sk⁡(C)∈[8,10]\operatorname{sk}(C) \in[8, 10].

(b) High degree: sk⁡(C)∈[8,10]\operatorname{sk}(C) \in[8, 10].

(c) Kamada–Kawai: sk⁡(C)=6\operatorname{sk}(C) = 6.

(d) Outer face (heuristic): sk⁡(C)=4\operatorname{sk}(C) = 4.

(e) Outer face (branch-and-cut): sk⁡(C)=3\operatorname{sk}(C) = 3.

Figure 5. Final composites for input i070, drawn with Kamada–Kawai layouts that may visually favor KK. Apparent crossings do not measure skewness. Legend: G1G_1 case179_goc; G2G_2 case300_ieee; G3G_3 case793_goc; G4G_4 case118_ieee.

one connected component. Nodes without demands may become disconnected. Both applications use a 10 800 s solver limit.

Feasibility. We find feasible solutions for 65.6 % of SCOTS and 42.8 % of SND composites. In both domains, we find feasible solutions most often with HD and least often with KK. The “source” comparisons in Figure 7 and Figure 12 use the sets in Table 3.

Reported solver times for SCOTS and SND

Figure 7. Globally optimal runs only. SCOTS times include SCOPF warmstarting. Points: runs; ticks: shifted geometric means.

Two horizontal stacked bar charts of application outcomes. SCOTS sources R, HD, KK, OF-H, and OF-B show feasible, infeasible, and no solution counts; SND sources R, HD, KK, OF-H, and OF-B show feasible and no solution counts. The horizontal axis is Number of instances from 0 to 100.

Figure 12. Application outcomes; 100 composites per method and 16 sources per application; 10 800 s solver limit. “Feasible” includes optimal solutions. “Infeasible” requires a solver proof; “No solution” denotes runs ending without either a feasible solution or an infeasibility proof.

OF selects merge vertices consecutively along the outer face boundary. For OF-B on PGLib, we test three alternatives: selecting vertices at equally spaced positions along the boundary, skipping one vertex between selections where possible, and preferring vertices of degree greater than one during consecutive selection. We test whether spreading out the connections and avoiding vertices of degree one help us find feasible SCOPF solutions. The tested changes offer little improvement in the number of runs returning a feasible solution (Section A.6).

We also test normalization across voltage levels for all five methods on PGLib. It does not increase the number of SCOPF runs returning a feasible solution (Section A.7).

Interaction between subinstances. We introduce no demands between SND subinstances and compensate flows over cut edges in PGLib, which raises the question of whether the subinstances interact after composition. We therefore examine whether coupling affects power flows and capacity installation costs.

For PGLib, we examine flows on coupling edges in SCOPF solutions (i.e., SCOTS without any switching), observing that every coupling edge carries nonzero base-case flow. We also compute the ratio of the mean absolute flow on coupling edges to that on inherited edges within each composite (Figure 13a). The median ratio is 99.4 % for OF-H and 104.9 % for OF-B, with 134.5 % for R, meaning that the coupling edges transfer roughly as much power on average as other edges in the constituents do. KK and HD have median ratios of 70.2 % and 280.1 %, respectively, indicating lower mean absolute flows on coupling edges than on inherited edges for KK and substantially higher flows for HD.

Base-case flow ratios for PGLib and SNDlib

Figure 13. Base-case flows. Boxplots as in Figure 8. SNDlib axis linear below 10−310^{-3} and logarithmic above.

For SNDlib, routing with fixed capacities and no failures yields nonzero flow between subinstances on all OF instances (Section A.5). After summing flows over all commodities and both directions, the median ratio of the mean flow on added coupling edges to that on inherited edges is 11.1 % for OF-H and 10.5 % for OF-B.

For the full SND problem, we also compare the composite objective with the sum of the optimal objectives of the compensated subinstances. Without flow between subinstances, we would expect these values to coincide under the same contingency requirements. Among the 130 comparisons where all subinstances and the composite are solved to optimality, the composite objective is lower in 83 cases, equal in one, and higher in 46. The lower costs indicate that coupling edges carry flow between subinstances, allowing demands to be routed through other subinstances even though no demands connect them. Higher costs can arise when coupling keeps demand terminals connected after previously excluded edge failures, adding these failures to the contingency set.

We conclude that the subinstances interact after composition in both applications. For PGLib, OF yields comparable mean absolute flows on coupling and inherited edges. For SNDlib, coupling can reduce capacity installation costs even without demands between subinstances. Onward routing could induce additional flow across the join by placing the demand terminals introduced by cut flow compensation farther inside another subinstance.

Computational difficulty. Among the generated instances solved to optimality, runtimes range from seconds to about three hours in both applications (Figure 7). Composition therefore provides benchmark instances at different levels of computational difficulty from the same small source pool. These results suggest that merge vertex selection affects both feasibility and computational difficulty.

Summary

Meaningful computational studies require sufficiently large and diverse test sets, but the availability of suitable real-world network instances is often limited. We generate additional infrastructure network instances by repeatedly extracting and joining connected subinstances in different ways, reusing their topology and parameters. We derive bounds on added skewness and structural changes, and propose a strategy for selecting the vertices at which subinstances are joined. This strategy adds no skewness when maximum planar subgraphs are computed. To reduce the number of infeasible instances, we compensate flows over cut edges and solve a tractable auxiliary problem during generation.

In experiments on PGLib-OPF and SNDlib, two libraries of infrastructure networks, our outer face selection method gives the smallest mean upper bounds on added skewness. Using branch-and-cut for planarization, our method certifies no added skewness for 48 of 100 PGLib inputs and all 100 SNDlib inputs. The optimization results show that the joined subinstances interact even after cut flow compensation, with coupling affecting power flows and capacity installation costs. Among the generated instances solved to optimality, SCOTS and SND runtimes range from seconds to about three hours, demonstrating variation in computational difficulty.

Our method can thus generate many additional test instances from a few existing networks, or even a single one. Reusing their topology and parameters reduces the need for domain knowledge compared with generating realistic networks from scratch. Controlling added skewness also helps preserve near-planarity, a characteristic of realistic infrastructure networks.

Author Contributions. Tim Donkiewicz: Conceptualization, Data curation, Formal analysis, Investigation, Methodology, Software, Validation, Visualization, Writing – original draft, Writing – review & editing.

Funding. This work received no specific funding.

Competing Interests. The author declares no competing interests.

Use of Large Language Models. OpenAI Codex and Anthropic Claude assisted with code development, theoretical discussions and manuscript revisions. The author reviewed and edited all outputs and takes full responsibility for the work.

Data and Code Availability. The source code, generated test instances, solver settings, and reproduction instructions are available in PlanarInstanceGeneration, tag paper.

Additional Evaluation Results

Skewness bounds

For pp extracted subgraphs, we measure added skewness and normalize it by the number of coupling edges:

a(C)=sk⁡(C)−∑i=1psk⁡(Gi),a(C) = \operatorname{sk}(C) - \sum_{i=1}^{p} \operatorname{sk}(G_i),
η(C)=a(C)∣M∣.\eta(C) = \frac{a(C)}{|M|}.

Let LQL_Q and UQU_Q denote the computed lower and upper bounds on sk⁡(Q)\operatorname{sk}(Q), respectively. By Lemma 1, bounds on added skewness are

a‾=max⁡{0,LC−∑i=1pUGi},\underline{a} = \max\left\{0, L_C - \sum_{i=1}^{p} U_{G_i}\right\},
a‾=min⁡{∣M∣−(p−1),UC−∑i=1pLGi}.\overline{a} = \min\left\{|M|-(p-1), U_C-\sum_{i=1}^{p} L_{G_i}\right\}.

Dividing these bounds by ∣M∣|M| gives η‾\underline{\eta} and η‾\overline{\eta}. Thus, [a‾,a‾][\underline{a},\overline{a}] bounds the absolute increase in skewness, while [η‾,η‾][\underline{\eta},\overline{\eta}] bounds this increase relative to the number of added coupling edges. Underlines and overlines denote lower and upper bounds, respectively. Table 5 summarizes the results.

Other structural characteristics

We discuss Figure 8 and Figure 9 in § 7.2.

Degrees of selected merge vertices

KK most often selects endpoints of degree one in PGLib and degree two in SNDlib (Figure 10).

Generation and application outcomes

In Figure 11, “Feasible” denotes a run with a feasible solution but no proof of optimality. “No solution” denotes a run ending without either a feasible solution or a proof of infeasibility.

Two Sankey diagrams showing SCOTS, $Z=1$ ($N=500$) and SND ($N=500$) outcomes. SCOTS: 262 attempts (100%), 100 accepted (38.2%), rejected; feasibility check 33 (12.6%), size requirements unmet 129 (49.2%); 500 (100%) composites yielding optimal 293 (58.6%), feasible 35 (7.0%), no solution 17 (3.4%), and infeasible 155 (31.0%). SND: 142 attempts (100%), 100 accepted (70.4%), rejected; size requirements unmet 42 (29.6%); 500 (100%) composites yielding optimal 130 (26.0%), feasible 84 (16.8%), no solution 286 (57.2%), and infeasible 0 (0.0%).

Figure 11. Percentages refer to all attempts or 500 composites per application. Size requirements concern instance size and available outer face vertices. Band widths are proportional within stages.

The PGLib rejection counts depend on the fixed evaluation order R, HD, KK, OF-H, OF-B, since each attempt stops at the first failure. All SNDlib rejections occur at the target size check.

Flows between subinstances

For PGLib, we compare the mean absolute base-case flows on coupling and inherited edges in the SCOPF solutions (Figure 13a).

For SNDlib, we solve Tract with capacities on inherited edges fixed as in preprocessing and one capacity module installed on each coupling edge. Among minimum-cost routings, we minimize total flow to avoid unnecessary circulation. We then sum flows over all commodities and both directions on each edge and compare the means on coupling and inherited edges (Figure 13b).

Outer face vertex selection rules

For OF-B on PGLib, we compare the four outer face selection rules described in § 7.4, using the main experiment’s coupling count and planarization limits. We solve SCOPF with overload slack to optimality or proven infeasibility (Table 6). The 69 matched inputs are those for which all four rules accept identical subinstances with the same target sizes and seeds.

Selection ruleAll 100 inputs69 matched inputs
Consecutive6245
Equidistant6043
Skip one where possible5745
Consecutive, prefer degree >1>16146

Table 6. Counts of SCOPF runs returning a feasible solution with OF-B. Bold: setting used in the main experiment.

Normalization across voltage levels

For PGLib, we normalize the accepted composites before SCOPF evaluation (Table 7). We assume positive total apparent demand in every subinstance. For each subinstance ii with vertex set ViV_i, we use

RHDKKOF-HOF-BTotal
Without normalization6470536162310
With normalization5870465757288

Table 7. Counts of SCOPF runs returning a feasible solution before and after normalization across voltage levels; 100 composites per method; overload slack permitted. Bold: setting used in the main experiment.

di=1∣Vi∣∑v∈ViPd,v2+Qd,v2Vvnom,d_i = \frac{1}{\lvert V_i\rvert}\sum_{v\in V_i}\frac{\sqrt{P_{d,v}^{2}+Q_{d,v}^{2}}}{V_{v}^{\mathrm{nom}}},
αi=median⁡j(dj)di.\alpha_i = \frac{\operatorname{median}_{j}(d_j)}{d_i}.

where Pd,vP_{d,v} and Qd,vQ_{d,v} are active and reactive demands, VvnomV_{v}^{\mathrm{nom}} is nominal voltage in kilovolts, and the median is over subinstances in the same composite. We multiply demands, shunt injections, generator outputs and bounds, line ratings, and line charging by αi\alpha_i, divide internal resistance and reactance by αi\alpha_i, and reparameterize generator costs. Voltage data, tap ratios, topology, and coupling branches are unchanged.

Across the 343 extracted subinstances, scale factors range from 0.000 726 to 885.339.

References

  1. [1]Sogol Babaeinejadsarookolaee, Adam Birchfield, Richard D Christie, Carleton Coffrin, Christopher DeMarco, Ruisheng Diao, Michael Ferris, Stephan Fliscounakis, Scott Greene, Renke Huang, et al. The power grid library for benchmarking AC optimal power flow algorithms. arXiv preprint arXiv:1908.02788, 2019. doi: 10.48550/arXiv.1908.02788. URL https://github.com/power-grid-lib/pglib-opf/releases/tag/v23.07. PGLib-OPF release v23.07.DOI
  2. [2]Clayton Barrows, Seth Blumsack, and Russell Bent. Computationally efficient optimal transmission switching: Solution space reduction. In 2012 IEEE Power and Energy Society General Meeting, pages 1–8. IEEE, 2012. doi: 10.1109/PESGM.2012.6345550.DOI
  3. [3]Marc Barthélemy. Spatial networks. Physics Reports, 499(1–3):1–101, 2011. doi: 10.1016/j.physrep.2010.11.002.DOI
  4. [4]Hamid Behnia and Mahdi Akhbari. Integrated generation and transmission maintenance scheduling by considering transmission switching. International Transactions on Electrical Energy Systems, 29(4):e2792, 2019. doi: 10.1002/etep.2792.DOI
  5. [5]Vahid Beiranvand, Warren Hare, and Yves Lucet. Best practices for comparing optimization algorithms. Optimization and Engineering, 18(4):815–848, 2017. doi: 10.1007/s11081-017-9366-1.DOI
  6. [6]Adam B. Birchfield and Thomas J. Overbye. Graph crossings in electric transmission grids. In 2021 North American Power Symposium (NAPS), pages 1–6, 2021. doi: 10.1109/NAPS52732.2021.9654543.DOI
  7. [7]Adam B. Birchfield, Ti Xu, Kathleen M. Gegner, Komal S. Shetye, and Thomas J. Overbye. Grid structural characteristics as validation criteria for synthetic networks. IEEE Transactions on Power Systems, 32(4):3258–3265, 2017. doi: 10.1109/TPWRS.2016.2616385.DOI
  8. [8]Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. Efficiently generating geometric inhomogeneous and hyperbolic random graphs. Network Science, 10(4):361–380, 2022. doi: 10.1017/nws.2022.32.DOI
  9. [9]Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7(4):448–461, 1973. doi: 10.1016/S0022-0000(73)80033-9.DOI
  10. [10]Aleksandar Bojchevski, Oleksandr Schur, Daniel Zügner, and Stephan Günnemann. NetGAN: Generating graphs via random walks. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 610–619, 2018. https://proceedings.mlr.press/v80/bojchevski18a.html.
  11. [11]Louis Bonnet, Simon Belieres, Mike Hewitt, and Sandra Ulrich Ngueveu. A complex network analysis approach for generating realistic instances of the scheduled service network design problem. HAL preprint hal-05345829, 2025. URL https://hal.science/hal-05345829.
  12. [12]John M. Boyer and Wendy J. Myrvold. On the cutting edge: Simplified o(n) planarity by edge addition. Journal of Graph Algorithms and Applications, 8(3):241–273, 2004. doi: 10.7155/jgaa.00091.DOI
  13. [13]Annika Buchholz, Stephanie Riedmüller, Matthew Passage, and Janina Zittel. Benchmarking realistic synthetic instances against a large-scale district heating network: A multi-objective optimization study for berlin. arXiv:2606.02195, 2026.
  14. [14]Felipe Campelo and Fernanda Takahashi. Sample size estimation for power and accuracy in the experimental comparison of algorithms. Journal of Heuristics, 25(2):305–338, 2019. doi: 10.1007/s10732-018-9396-7.
  15. [15]Felipe Campelo and Elizabeth F. Wanner. Sample size calculations for the experimental comparison of multiple algorithms on multiple problem instances. Journal of Heuristics, 26 (6):851–883, 2020. doi: 10.1007/s10732-020-09454-w.
  16. [16]Corrie Jacobien Carstens, Michael Hamann, Ulrich Meyer, Manuel Penschuck, Hung Tran, and Dorothea Wagner. Parallel and I/O-efficient randomisation of massive networks using global curveball trades. In 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:15, 2018. doi: 10.4230/LIPIcs.ESA.2018.11.
  17. [17]Moses Charikar. Greedy approximation algorithms for finding dense components in a graph. In Klaus Jansen and Samir Khuller, editors, Approximation Algorithms for Combinatorial Optimization, volume 1913 of Lecture Notes in Computer Science, pages 84–95. Springer, 2000. doi: 10.1007/3-540-44436-X_10.
  18. [18]Varsha Chauhan, Alexander Gutfraind, and Ilya Safro. Multiscale planar graph generation. Applied Network Science, 4:46, 2019. doi: 10.1007/s41109-019-0142-3.
  19. [19]Naiyuan Chiang and Andreas Grothey. Solving security constrained optimal power flow problems by a structure exploiting interior point method. Optimization and Engineering, 16(1):49–71, 2015. doi: 10.1007/s11081-014-9250-1.
  20. [20]Markus Chimani and Tilo Wiedera. Cycles to the rescue! novel constraints to compute maximum planar subgraphs fast. In 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018. doi: 10.4230/LIPIcs.ESA.2018.19.
  21. [21]Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel. The open graph drawing framework (OGDF). In Roberto Tamassia, editor, Handbook of Graph Drawing and Visualization, chapter 17. CRC Press, 2014. URL https://www.ogdf.uni-osnabrueck.de/wp-content/uploads/2019/04/ogdf.pdf.
  22. [22]Markus Chimani, Ivo Hedtke, and Tilo Wiedera. Exact algorithms for the maximum planar subgraph problem: New models and experiments. ACM Journal of Experimental Algorithmics, 24(1):2.1:1–2.1:21, 2019. doi: 10.1145/3320344.
  23. [24]Eduardo Cotilla-Sanchez, Paul D. H. Hines, Clayton Barrows, and Seth Blumsack. Comparing the topological and electrical structure of the north american electric power infrastructure. IEEE Systems Journal, 6(4):616–626, 2012. doi: 10.1109/JSYST.2012.2183033.
  24. [25]Annelies De Corte and Kenneth Sörensen. HydroGen: an artificial water distribution network generator. Water Resources Management, 28(2):333–350, 2014. doi: 10.1007/s11269-013-0485-y.DOI
  25. [26]R. W. Decker, H. H. Glover, and J. P. Huneke. The genus of the 2-amalgamations of graphs. Journal of Graph Theory, 5(1):95–102, 1981. doi: 10.1002/jgt.3190050107.
  26. [27]Janez Demšar. Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7:1–30, 2006. https://jmlr.org/papers/v7/demsar06a.html.DOI
  27. [28]Tao Ding and Chaoyue Zhao. Robust optimal transmission switching with the consideration of corrective actions for n- k contingencies. IET Generation, Transmission & Distribution, 10(13):3288–3295, 2016. doi: 10.1049/iet-gtd.2016.0126.DOI
  28. [31]Emily B Fisher, Richard P O’Neill, and Michael C Ferris. Optimal transmission switching. IEEE Transactions on Power Systems, 23(3):1346–1355, 2008. doi: 10.1109/TPWRS.2008.922256.DOI
  29. [33]Antonio Frangioni and Bernard Gendron. 0–1 reformulations of the multicommodity capacitated network design problem. Discrete Applied Mathematics, 157(6):1229–1241, 2009. doi: 10.1016/j.dam.2008.04.022.DOI
  30. [34]Daniel Funke, Sebastian Lamm, Ulrich Meyer, Manuel Penschuck, Peter Sanders, Christian Schulz, Darren Strash, and Moritz von Looz. Communication-free massively distributed graph generation. Journal of Parallel and Distributed Computing, 131:200–217, 2019. doi: 10.1016/j.jpdc.2019.03.011.DOI
  31. [35]C. Grigg, P. Wong, P. Albrecht, R. Allan, M. Bhavaraju, R. Billinton, Q. Chen, C. Fong, S. Haddad, S. Kuruganty, W. Li, R. Mukerji, D. Patton, N. Rau, D. Reppen, A. Schneider, M. Shahidehpour, and C. Singh. The IEEE reliability test system-1996. IEEE Transactions on Power Systems, 14(3):1010–1020, 1999. doi: 10.1109/59.780914.
  32. [36]Michael Hamann, Ulrich Meyer, Manuel Penschuck, Hung Tran, and Dorothea Wagner. I/O-efficient generation of massive graphs following the LFR benchmark. ACM Journal of Experimental Algorithmics, 23:2.5:1–2.5:33, 2018. doi: 10.1145/3230743.DOI
  33. [37]Tong Han, Yue Song, and David J Hill. Ensuring network connectedness in optimal transmission switching problems. IEEE Transactions on Circuits and Systems II: Express Briefs, 68(7):2603–2607, 2021. doi: 10.1109/TCSII.2021.3059070.
  34. [38]Tong Han, David J Hill, and Yue Song. Formulating connectedness in security-constrained optimal transmission switching problems. IEEE Transactions on Power Systems, 37(5):4137–4140, 2022. doi: 10.1109/TPWRS.2022.3184122.
  35. [39]Kory W. Hedman, Richard P. O’Neill, Emily Bartholomew Fisher, and Shmuel S. Oren. Optimal Transmission Switching With Contingency Analysis. IEEE Transactions on Power Systems, 24(3):1577–1586, August 2009. ISSN 1558-0679. doi: 10.1109/TPWRS.2009.2020530.DOI
  36. [40]Majid Heidarifar, Meysam Doostizadeh, and Hassan Ghasemi. Optimal transmission reconfiguration through line switching and bus splitting. In 2014 IEEE PES General Meeting/ Conference & Exposition, pages 1–5. IEEE, 2014. doi: 10.1109/PESGM.2014.6939408.DOI
  37. [41]Majid Heidarifar, Panagiotis Andrianesis, Pablo Ruiz, Michael C Caramanis, and Ioannis Ch Paschalidis. An optimal transmission line switching and bus splitting heuristic incorporating ac and n-1 contingency constraints. International Journal of Electrical Power & Energy Systems, 133:107278, 2021. doi: 10.1016/j.ijepes.2021.107278.DOI
  38. [42]John N Hooker. Needed: An empirical science of algorithms. Operations Research, 42(2):201–212, 1994. doi: 10.1287/opre.42.2.201.DOI
  39. [43]John N Hooker. Testing heuristics: We have it all wrong. Journal of Heuristics, 1(1):33–42, 1995. doi: 10.1007/BF02430364.DOI
  40. [44]Jonas Hörsch, Fabian Hofmann, David Schlachtberger, and Tom Brown. PyPSA-Eur: An open optimisation model of the european transmission system. Energy Strategy Reviews, 22:207–215, 2018. doi: 10.1016/j.esr.2018.08.012.DOI
  41. [45]Trager Joswig-Jones, Kyri Baker, and Ahmed S. Zamzam. OPF-Learn: An open-source framework for creating representative AC optimal power flow datasets. In 2022 IEEE Power & Energy Society Innovative Smart Grid Technologies Conference (ISGT), 2022. doi: 10.1109/ISGT50606.2022.9817509.
  42. [46]Michael Jünger and Petra Mutzel. Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica, 16(1):33–59, 1996. doi: 10.1007/s004539900036.DOI
  43. [47]Michael Jünger and Stefan Thienel. Introduction to ABACUS—a branch-and-cut system. Operations Research Letters, 22(2–3):83–95, 1998. doi: 10.1016/S0167-6377(98)00013-3.DOI
  44. [48]Tomihisa Kamada and Satoru Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31(1):7–15, 1989. doi: 10.1016/0020-0190(89)90102-6.DOI
  45. [49]Mojtaba Khanabadi, Hassan Ghasemi, and Meysam Doostizadeh. Optimal transmission switching considering voltage security and n-1 contingency analysis. IEEE Transactions on Power Systems, 28(1):542–550, 2013. doi: 10.1109/TPWRS.2012.2207464.DOI
  46. [50]Mojtaba Khanabadi, Yong Fu, and Cong Liu. Decentralized transmission line switching for congestion management of interconnected power systems. IEEE Transactions on Power Systems, 33(6):5902–5912, 2018. doi: 10.1109/TPWRS.2018.2838046.DOI
  47. [51]Amin Khodaei and Mohammad Shahidehpour. Transmission switching in security-constrained unit commitment. IEEE Transactions on Power Systems, 25(4):1937–1945, 2010. doi: 10.1109/TPWRS.2010.2046344.DOI
  48. [52]Amin Khodaei and Mohammad Shahidehpour. Security-constrained transmission switching with voltage constraints. International Journal of Electrical Power & Energy Systems, 35(1):74–82, 2012. doi: 10.1016/j.ijepes.2011.09.014.DOI
  49. [53]Simon Knight, Hung X. Nguyen, Nickolas Falkner, Rhys Bowden, and Matthew Roughan. The internet topology zoo. IEEE Journal on Selected Areas in Communications, 29(9):1765–1775, 2011. doi: 10.1109/JSAC.2011.111002.
  50. [54]Varvara Kovaleva and Alexander Ponomarenko. A benchmark generator of realistic logistic transport networks with nonlinear edge costs and transshipment capacities. arXiv:2606.20653, 2026.arxiv.org/abs/2606.20653
  51. [55]Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, 2014.
  52. [56]Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research, 11:985–1042, 2010. https://jmlr.org/papers/v11/leskovec10a.html.
  53. [57]Peijie Li, Xiaoqian Huang, Junjian Qi, Hua Wei, and Xiaoqing Bai. A connectivity constrained milp model for optimal transmission switching. IEEE Transactions on Power Systems, 36(5):4820–4823, 2021. doi: 10.1109/TPWRS.2021.3089029.DOI
  54. [58]Yongzhe Li, Lin Guan, Zihan Cai, Zuxian Lin, Jiyu Huang, and Liukai Chen. Scale-adaptive power flow analysis with local topology slicing and multi-task graph learning. arXiv:2601.01387, 2026.arxiv.org/abs/2601.01387
  55. [59]Annegret Liebers. Planarizing graphs—a survey and annotated bibliography. Journal of Graph Algorithms and Applications, 5(1):1–74, 2001. doi: 10.7155/jgaa.00032.DOI
  56. [60]Andrea Lodi and Andrea Tramontani. Performance variability in mixed-integer programming. In Theory Driven by Influential Applications, INFORMS TutORials in Operations Research, pages 1–12. INFORMS, 2013. doi: 10.1287/educ.2013.0112.DOI
  57. [61]Sean Lovett, Miha Zgubic, Sofia Liguori, Sephora Madjihureem, Hamish Tomlinson, Sophie Elster, Chris Apps, Sims Witherspoon, and Luis Piloto. OPFData: Large-scale datasets for AC optimal power flow with topological perturbations. arXiv:2406.07234, 2024.arxiv.org/abs/2406.07234
  58. [62]Catherine C McGeoch. A Guide to Experimental Algorithmics. Cambridge University Press, 2012. ISBN 9781107001732. doi: 10.1017/CBO9780511843747.DOI
  59. [63]Wided Medjroubi, Ulf Philipp Mueller, Malte Scharf, Carsten Matke, and David Kleinhan. Open data in power grid modelling: New approaches towards transparent grid models. Energy Reports, 3:14–21, 2017. doi: 10.1016/j.egy.2016.12.001.
  60. [64]M. E. J. Newman. Assortative Mixing in Networks. Physical Review Letters, 89(20):208701, October 2002. doi: 10.1103/PhysRevLett.89.208701.DOI
  61. [65]Richard P O’Neill, Kory W Hedman, Eric A Krall, Anthony Papavasiliou, and Shmuel S Oren. Economic analysis of the n-1 reliable unit commitment and transmission switching problem using duality concepts. Energy Systems, 1:165–195, 2010. doi: 10.1007/s12667-009-0005-6.DOI
  62. [66]S. Orlowski, R. Wessály, M. Pióro, and A. Tomaszewski. SNDlib 1.0—Survivable Network Design Library. Networks, 55(3):276–286, 2010. doi: 10.1002/net.20371.DOI
  63. [68]Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI), pages 4292–4293, 2015. https://networkrepository.com.DOI
  64. [69]Pablo A Ruiz, Aleksandr Rudkevich, Michael C Caramanis, Evgenyi Goldis, Elli Ntakou, and C Russ Philbrick. Reduced mip formulation for transmission topology control. In 2012 50th annual Allerton conference on communication, control, and computing (Allerton), pages 1073–1079. IEEE, 2012. doi: 10.1109/Allerton.2012.6483337.DOI
  65. [70]Raphael Saavedra, Alexandre Street, and José M. Arroyo. Day-Ahead Contingency-Constrained Unit Commitment With Co-Optimized Post-Contingency Transmission Switching. IEEE Transactions on Power Systems, 35(6):4408–4420, November 2020. ISSN 1558-0679. doi: 10.1109/TPWRS.2020.2996499.DOI
  66. [71]Kate Smith-Miles and Simon Bowly. Generating new test instances by evolving in instance space. Computers & Operations Research, 63:102–113, 2015. doi: 10.1016/j.cor.2015.04.022.
  67. [72]Neil Spring, Ratul Mahajan, and David Wetherall. Measuring ISP topologies with Rocketfuel. In Proceedings of the 2002 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), pages 133–145, 2002. doi: 10.1145/633025.633039.DOI
  68. [73]Christian L. Staudt, Michael Hamann, Alexander Gutfrain[d], Ilya Safro, and Henning Meyerhenke. Generating realistic scaled complex networks. Applied Network Science, 2:36, 2017. doi: 10.1007/s41109-017-0054-z.DOI
  69. [74]Huy Truong, Andrés Tello, Alexander Lazovik, and Victoria Degeler. DiTEC-WDN: A large-scale dataset of hydraulic scenarios across multiple water distribution networks. Scientific Data, 12:1733, 2025. doi: 10.1038/s41597-025-06026-0.DOI
  70. [75]Jeffrey S. Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical Software, 11(1):37–57, 1985. doi: 10.1145/3147.3165.DOI
  71. [76]Klaus Wagner. Über eine eigenschaft der ebenen komplexe. Mathematische Annalen, 114(1):570–590, 1937. doi: 10.1007/BF01594196.DOI
  72. [77]Chenhan Xiao, Xinyu He, Haoran Li, Hanghang Tong, and Yang Weng. Operationally feasible synthetic power-grid scenarios via learning the AC-operable joint distribution. arXiv:2608.03878, 2026.arxiv.org/abs/2608.03878
  73. [79]Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. GraphRNN: Generating realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 5708–5717, 2018. https://proceedings.mlr.press/v80/you18a.html.arxiv.org/abs/1802.08773

Paper details

vlnc:W_jzsnz6v3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents