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.

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 -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 network | Outages | |||||||
| 14 | 30 | 57 | 73 | 118 | 300 | Other | ||
| 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 . We write for its underlying graph. The pair 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 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 . collects all supply and demand values attached to a node. For each , is a function whose value is the lower bound and is the upper bound for supply or demand (depending on whether it assumes a positive or negative value) at node . In particular, when , the supply or demand at is fixed to that value. Otherwise, it is a variable within these bounds. If and denote realized flows and supplies where , we impose flow conservation
i.e., total outgoing flow equals total incoming flow plus the supply attached to the node. 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 , 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 . 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, denotes the fixed optimization problem for which we generate instances. denotes an application-specific, tractable auxiliary optimization problem used during instance generation. It serves as a proxy for the suitability of for and need not certify feasibility or infeasibility for . We solve 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 obtained by ignoring edge orientations, removing self-loops and replacing parallel edges by a single edge. Further, let be the neighborhood of and its degree.
Our primary graph property is the skewness
where . A subgraph attaining this maximum is called a maximum planar subgraph; computing one is also called planarization. Throughout, we denote planar subgraphs by . 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.

Figure 2. are maximum planar subgraphs. Numbers in parentheses count distinct boundary vertices. Shading marks the chosen faces before joining. The dotted edge belongs to . 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
and the maximum degree .
The local clustering coefficient of is
In other words, is the fraction of possible triangles that include . We report the average clustering coefficient .
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:
where is the length of a shortest path between and in .
Let and let be the eigenvalues of the Laplacian , where is the adjacency matrix and is the diagonal matrix of vertex degrees, in the same vertex order as . The second eigenvalue is the algebraic connectivity; it is positive exactly when is connected, and a small positive value indicates a bottleneck.
Finally, the degree assortativity [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 : 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 and their disjoint union , the graph whose vertex set and edge set are the disjoint unions of the and the , so that the sources share no vertex or edge. Adding a set of coupling edges, each between a vertex of one source and a vertex of another, yields the composite , where denotes the addition of the edge set .
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 and have been moved to the outside). Following the boundary of a face gives a sequence of incident vertices and edges that returns to its starting vertex. We denote this boundary walk by , in which a vertex or edge may occur more than once (e.g., when a vertex of degree one lies on the boundary). Let be the set of distinct vertices occurring in . We order the vertices in by their first occurrences in .
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 is connected. Then the skewness of the composite satisfies
Proof. The edges of split into the source edges and the coupling edges, so . For the lower bound, let be a maximum planar subgraph of . Each restriction is planar and contains at most edges. Together with at most coupling edges, this gives and hence . For the upper bound, choose a maximum planar subgraph of each . Replace each source graph by a single vertex and retain the coupling edges between these vertices. The resulting multigraph is connected and has vertices, so it has a spanning tree with edges. Let be the corresponding set of coupling edges in . The graph is planar: it joins vertex-disjoint planar graphs according to a tree, with every edge of acting as a bridge. It omits source edges and 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 edges from , the same argument gives . The following lemma characterizes when the lower bound is attained.
Lemma 2 (Attainment of the lower skewness bound). The equality
holds if and only if there are maximum planar subgraphs for which is planar. In particular, for two sources, this condition holds whenever is a noncrossing matching between distinct vertices incident with chosen faces of planar embeddings of maximum planar subgraphs and . Consequently, for the two chosen faces, i.e., can only be as large as the smaller of the two outer face sizes.
Proof. If is planar, it is a planar subgraph of with edges. Thus, . The reverse inequality follows from the proof of Lemma 1, so equality holds.
Conversely, suppose the equality holds and let be a maximum planar subgraph of . By assumption, planarizing deletes exactly edges from its edges. Therefore
The right-hand side is the largest number of edges can have: at most from each source , plus the coupling edges. Since has exactly that many edges, it contains all coupling edges and edges from every source. Thus, every is a maximum planar subgraph of , and is the required planar graph. □
Lemma 3 (Boundary order matching). Let and 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
where is the number of vertex occurrences in one traversal, excluding the final repetition of the starting vertex. Let , and choose indices
i.e., some vertices may be skipped, but their order along each boundary walk must be preserved. Suppose the vertices are distinct and the vertices are distinct, i.e., at most one occurrence of each vertex is selected from each boundary walk. Then the matching
is noncrossing.
Proof. We insert the matching edges 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 , we may need to mirror one drawing so that, after inserting , the unused endpoints occur along the outer face boundary in the order . Thus, the first edge can be drawn through the common outer face without crossings. The induced face boundary walk becomes longer, traversing the new edge twice. For , the construction is complete after adding .
Inductively, suppose that have been inserted without crossings, where , and that the current graph has a face with a boundary walk that contains the unused endpoints in the order
possibly with intermediate vertices skipped according to the chosen indices, and the first edge and previously added edge . We add the next edge . By construction, both and are incident with the same face of the current graph, and is noncrossing. The new edge connects the first and last unused endpoints in the displayed order. One resulting face is bounded by and 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 whenever unused endpoints remain; after inserting , the matching is complete without crossings. □
The same principle applies when more than two source graphs are composed sequentially. For , let denote the composite obtained after the joins of with coupling edge sets .
Corollary 1 (Sequential composition). Let and choose a maximum planar subgraph . Then, compose with one at a time, with . At step , let be a maximum planar subgraph and let be a noncrossing matching between distinct vertices incident with chosen faces of planar embeddings of and . If is retained for the next step, then the final composite satisfies
Proof. For the base case , we have , the chosen subgraph is maximum planar, and .
For the induction step, let and assume that is a maximum planar subgraph of and that
The noncrossing matching makes planar. Applying Lemma 2 to and therefore gives
The forward direction in the proof of Lemma 2 also shows that is a maximum planar subgraph of . Thus both induction claims hold for , and setting proves the result. □
Writing for the set of all coupling edges, Lemma 1 shows that the additional skewness of a sequential composition of subgraphs lies between and . 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 , 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 and the chosen subgraphs .
Lemma 4 (Skewness bound for non-maximum planar subgraphs). If are planar subgraphs for which is planar, then
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, . It is planar by hypothesis and has edges. This gives . Since , the terms cancel out, giving
The additional skewness above the lower bound is thus at most the sum of the missing edge set cardinalities of the chosen subgraphs, , and this upper bound is zero when each 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 be the composite graph. For , let be the number of coupling edges incident with , let be the set of merge vertices, and let . For (iv), additionally assume the sequential construction and , where each is a matching between and . Then the following hold:
(i) and .
(ii) Let
be the degree distribution of the disjoint source graphs before composition. Then, for every ,
i.e., for any degree , the fraction of degree- vertices changes by at most the fraction of merge vertices.
(iii) The maximum degree satisfies
i.e., composition cannot reduce the largest source maximum degree and can increase it by at most the maximum coupling degree.
(iv) Any vertex satisfies . Let
be the average clustering coefficient over all source graphs before composition. Then
i.e., the average clustering coefficient can decrease by at most the fraction of merge vertices.
Proof. The source graphs are vertex-disjoint and adds exactly edges, proving (i). For , counting its source and coupling edges gives . Only the vertices in change degree; hence, for each , at most vertices switch their degree- class, proving the bound on in (ii). Taking maxima in the degree identity gives (iii). If , its neighborhood is unchanged, so .
Suppose a triangle meets multiple source graphs, and let be the largest index for which it meets . Irrespective of whether it has one or two vertices in , the two edges between and earlier source graphs are contained in and share an endpoint, contradicting that is a matching. Thus no triangle in contains a coupling edge. Therefore, composition leaves the number of triangles through each vertex unchanged while its degree can only increase, so . Since equality holds outside and all clustering coefficients lie in , 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 be induced by , with , and let be the flows from a feasible solution of Tract. For and , the cut flow compensation is ’s net flow across the cut,
which can be positive or negative.
Proposition 2 (Cut flow compensation). Let be a feasible solution for , with realized flows and supplies , and let be given by (1). For every and , shift the supply limits in either to and (fixed compensation), or to and (variable compensation). Suppose that every constraint of other than flow conservation and supply limits is satisfied by the restriction of together with the compensated supplies. Then this restriction, with realized supplies , is feasible for .
Proof. For every and , feasibility of in gives
Separating internal and cut edges and rearranging yields
Thus the restricted solution satisfies flow conservation with the compensated supplies. Since , 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 has a continuous potential , 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 and on disjoint node sets and , with node potentials and from feasible solutions (see Proposition 2). Let be a set of coupling edges between the instances. Each connects to with . Suppose the flow of each edge is defined by
For each such edge, let be its offset before compensation, taking if none exists, and set
Suppose that, for every , this offset is admissible and the edge bounds allow . If no other constraint introduced with $e excludes these values, then the constituent solutions extend to a feasible solution for on the composed instance after adding any number of such edges.
Proof. Retain the constituent solutions and use the offsets above. For every with and , we obtain
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, may vary between 0 (no angle difference compensation) and (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 bounds the number of transmission branches whose status may be changed. SCOPF is the special case with , in which the network topology is fixed. The contingency set contains sets of failed branches. The base case 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 , fixed loads and generation bounds for , generation costs, line parameters and operating limits, contingencies including the base case, and a topological action limit . |
| Feasible solution. | Generation , voltage angles , line flows , branch status decisions and nonnegative branch overload variables satisfying the topological action limit, nodal balance, Kirchhoff voltage laws, generation limits and the relaxed thermal constraints for every . |
| 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 is . The generation bounds and fixed demands determine the supply limits in . contains the thermal limits and the remaining physical and cost parameters.
Here, 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 is a DC-OPF (without contingencies) problem with fixed original topology and strict branch limits. The subinstances are feasible for by Proposition 2. The composite’s feasibility for may be guaranteed by Corollary 2, since DC power flow problems are potential-based flows with voltage angles corresponding to the node potentials .
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 contains subsets specifying the failed edges and includes the base case . Instance. A graph , commodities with source , sink and demand , available module types with their capacities and installation costs on each edge , and contingencies including the base case.
Feasible solution. Module counts for each edge and available module type , and commodity flows for and , satisfying the demands and shared edge capacities, with zero flow on failed edges.
Objective. Minimize capacity installation cost.
For each commodity , the supply limits in are fixed to at , at , and zero elsewhere. 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 in six stages, followed by a feasibility check. The algorithm draws 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 , the joins are performed sequentially.
Source selection. The library is preprocessed once. An application may first restrict it using a declared Boolean filter function , where means that is eligible. For example, may select supported data features by filtering on or a size range by filtering on . 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
For each generation attempt, we sample a number of sources from the integers in , where . We then draw the sources , , independently and uniformly from with replacement, relabeling if necessary to make all node sets disjoint. The stored solution provides a flow for every edge and commodity for the subsequent cut flow compensation.
Subgraph extraction. For each requested instance , a target size is drawn uniformly at random from the integers in . The parameters give lower and upper bounds on the fraction of vertices retained from each source. Each subinstance size must be an integer in . If the selected sources cannot together provide exactly 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 . Each instance is then reduced to a connected subgraph with and by a randomized breadth-first search from a uniformly sampled starting node. The induced instance inherits all node and edge attributes from . For the later cut flow compensation, the cut edges are recorded.
Cut flow compensation. Using the stored solution , we compute the net cut flow from (1) for each retained node incident to a cut edge and each commodity . 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 and its underlying graph by .
Merge vertex selection. At join , the current composite is joined with the next extracted graph . Let
We request
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 and . We select merge vertex pairs so that no vertex occurs in more than one pair, redrawing sources if or . We compare four merge vertex selection methods:
a) random (R): sample distinct vertices uniformly from each graph; pair in sampling order;
b) high-degree (HD): take the 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 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 vertices and edges, random candidates can be selected in time ([75]) and high-degree candidates in time ([9]). The classical Kamada–Kawai method takes time, where 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 time ([12]). Computing a maximum planar subgraph, by contrast, is NP-hard ((Yannakakis, 1978)).
Sequential composition. Let denote the composite instance after joining the first subinstances, with and . At join , we obtain by adding the coupling edges between and , 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 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 after composition, discarding the attempt unless a feasible solution is found. For each requested output, the algorithm makes at most 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 vertices has at most edges, or if it contains no triangle (i.e., with or , respectively). Thus, a subgraph exceeding the applicable bound requires edge deletions. For with , let be the set of edges with both endpoints in . We use the subgraph Euler inequalities (Chimani and Wiedera, [20], § 4)
where indicates whether edge is deleted. The choice is always valid, and is valid when no triangle has all three vertices in . 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 and, whenever no triangles remain, also . For each choice of , we retain a subset maximizing the right-hand side 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 and be the selected planar subgraphs of and . Their OF join is planar by Lemma 3 even if the selected subgraphs are not maximum. In both OF-B and OF-H, we compare 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 and be the computed skewness lower bounds for and . For the next planarization of , it still holds that
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 . Additionally, since and have disjoint edge sets,
always holds. If the available lower bound equals the number of edges omitted by the retained planar subgraph of , 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
where is the commodity set of and is the number of flow variables in for SND. Table 2 summarizes the exclusions and resulting source pools.
| Library | Initial instances | Exclusions | |||
| Euler | |||||
| PGLib | 66 | 0 | 1 | 49 | 16 |
| SNDlib | 26 | 5 | 4 | 1 | 16 |
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 | ||||||
| case73_ieee_rts | 73 | 108 | 4 | 3.7% | 0 | 0.0% |
| case89_pegase | 89 | 206 | [40, 55] | [31, 32] | ||
| case118_ieee | 118 | 179 | 0 | 0.0% | 0 | 0.0% |
| case162_ieee_dtc | 162 | 280 | [16, 30] | 0 | 0.0% | |
| case179_goc | 179 | 222 | 1 | 0.5% | 1 | 0.5% |
| case197_snem | 197 | 223 | 0 | 0.0% | 0 | 0.0% |
| case200_activ | 200 | 245 | [1, 6] | 1 | 0.6% | |
| case240_pserc | 240 | 348 | 10 | 2.9% | 1 | 0.4% |
| case300_ieee | 300 | 409 | 9 | 2.2% | 2 | 0.7% |
| case500_goc | 500 | 650 | [14, 18] | 2 | 0.4% | |
| case588_sdet | 588 | 677 | [10, 13] | 0 | 0.0% | |
| case793_goc | 793 | 904 | [11, 17] | 2 | 0.3% | |
| case1354_pegase | 1354 | 1710 | [24, 50] | [10, 11] | ||
| case1888_rte | 1888 | 2308 | [25, 54] | [9, 10] | ||
| case1951_rte | 1951 | 2375 | [26, 57] | 10 | 0.5% | |
| case2000_goc | 2000 | 2806 | [59, 225] | 13 | 0.6% |
Table 3. Source skewness intervals (single values are exact) and relative upper bounds in gray. Time limit: 24 h. PGLib: with all lines, without lines between voltage levels, and 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 . Table 4 lists the generation settings.
| Setting | Symbols | PGLib | SNDlib |
| Source networks | |||
| Retained vertex fraction | |||
| Target vertices | |||
| Maximum attempts | 25 | 25 | |
| Outer face vertex selection | Consecutive | Consecutive | |
| Cut flow compensation | Variable | Fixed |
Table 4. Generation settings.
| Source | ||||
| abilene | 12 | 15 | 0 | 0.0% |
| atlanta | 15 | 22 | 0 | 0.0% |
| cost266 | 37 | 57 | 0 | 0.0% |
| france | 25 | 45 | 0 | 0.0% |
| geant | 22 | 36 | 2 | 5.6% |
| germany50 | 50 | 88 | 2 | 2.3% |
| giul39 | 39 | 86 | 4 | 4.7% |
| india35 | 35 | 80 | 4 | 5.0% |
| janos-us-ca | 39 | 61 | 0 | 0.0% |
| janos-us | 26 | 42 | 0 | 0.0% |
| nobel-eu | 28 | 41 | 0 | 0.0% |
| nobel-germany | 17 | 26 | 0 | 0.0% |
| nobel-us | 14 | 21 | 1 | 4.8% |
| norway | 27 | 51 | 1 | 2.0% |
| sun | 27 | 51 | 1 | 2.0% |
| zib54 | 54 | 80 | 0 | 0.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 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 , we report the shifted geometric mean
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.

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.

Figure 4. Distribution of upper bounds on normalized added skewness on all 100 final instances.
| Domain | Method | No added skewness | Exact skewness | |||||
| PGLib | R | 21.502 | 1.014 | 9.637 | 0.108 | 0.677 | 0 | 14 |
| HD | 20.617 | 1.106 | 9.128 | 0.113 | 0.645 | 0 | 16 | |
| KK | 17.656 | 0.861 | 6.907 | 0.082 | 0.513 | 3 | 21 | |
| OF-H | 11.377 | 0.057 | 1.928 | 0.005 | 0.213 | 37 | 46 | |
| OF-B | 10.916 | 0.000 | 1.454 | 0.000 | 0.176 | 48 | 49 | |
| SNDlib | R | 3.479 | 2.806 | 2.917 | 0.290 | 0.299 | 8 | 90 |
| HD | 3.106 | 2.542 | 2.563 | 0.259 | 0.262 | 10 | 96 | |
| KK | 2.208 | 1.645 | 1.649 | 0.175 | 0.176 | 18 | 99 | |
| OF-H | 0.584 | 0.014 | 0.014 | 0.001 | 0.001 | 98 | 100 | |
| OF-B | 0.577 | 0.000 | 0.000 | 0.000 | 0.000 | 100 | 100 |
Table 5. Skewness over 100 matched inputs per domain. First five numeric columns: shifted geometric mean bounds; last two: counts with and , 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.

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.

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.

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 . 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.

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 , permit overload slack, and exclude single-line contingencies that disconnect the network. SCOPF warmstarting is enabled. For SND, the contingency set contains the base case and all single-edge failures under which all demand terminals remain in
(a) Random: .
(b) High degree: .
(c) Kamada–Kawai: .
(d) Outer face (heuristic): .
(e) Outer face (branch-and-cut): .
Figure 5. Final composites for input i070, drawn with Kamada–Kawai layouts that may visually favor KK. Apparent crossings do not measure skewness. Legend: case179_goc; case300_ieee; case793_goc; 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.

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

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.

Figure 13. Base-case flows. Boxplots as in Figure 8. SNDlib axis linear below 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 extracted subgraphs, we measure added skewness and normalize it by the number of coupling edges:
Let and denote the computed lower and upper bounds on , respectively. By Lemma 1, bounds on added skewness are
Dividing these bounds by gives and . Thus, bounds the absolute increase in skewness, while 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.

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 rule | All 100 inputs | 69 matched inputs |
| Consecutive | 62 | 45 |
| Equidistant | 60 | 43 |
| Skip one where possible | 57 | 45 |
| Consecutive, prefer degree | 61 | 46 |
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 with vertex set , we use
| R | HD | KK | OF-H | OF-B | Total | |
| Without normalization | 64 | 70 | 53 | 61 | 62 | 310 |
| With normalization | 58 | 70 | 46 | 57 | 57 | 288 |
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.
where and are active and reactive demands, 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 , divide internal resistance and reactance by , 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]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]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]Marc Barthélemy. Spatial networks. Physics Reports, 499(1–3):1–101, 2011. doi: 10.1016/j.physrep.2010.11.002.DOI
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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.
- [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.
- [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
- [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.
- [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
- [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
- [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
- [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
- [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
- [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.
- [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
- [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.
- [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.
- [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
- [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
- [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
- [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
- [43]John N Hooker. Testing heuristics: We have it all wrong. Journal of Heuristics, 1(1):33–42, 1995. doi: 10.1007/BF02430364.DOI
- [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
- [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.
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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.
- [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
- [55]Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, 2014.
- [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.
- [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
- [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
- [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
- [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
- [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
- [62]Catherine C McGeoch. A Guide to Experimental Algorithmics. Cambridge University Press, 2012. ISBN 9781107001732. doi: 10.1017/CBO9780511843747.DOI
- [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.
- [64]M. E. J. Newman. Assortative Mixing in Networks. Physical Review Letters, 89(20):208701, October 2002. doi: 10.1103/PhysRevLett.89.208701.DOI
- [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
- [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
- [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
- [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
- [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
- [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.
- [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
- [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
- [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
- [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
- [76]Klaus Wagner. Über eine eigenschaft der ebenen komplexe. Mathematische Annalen, 114(1):570–590, 1937. doi: 10.1007/BF01594196.DOI
- [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
- [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




