Seddik Yassine Abdelouadoud
email: yassine.abdelouadoud@minesparis.psl.eu

Robin Girard
email: robin.girard@minesparis.psl.eu

Sébastien Vallet

Agglomerative Hierarchical Clustering Applied to Medium Voltage Feeder Hosting Capacity Estimation

Keywords: voltage feeders, hosting capacity, clustering

In this paper, we will assess the relevance of applying hierarchical agglomerative clustering algorithms on medium voltage feeder descriptive parameters (average line impedance, capacity, total length, etc.) in order to select representative feeders for long term planning studies. To achieve this, we start by creating a dataset of medium voltage feeders (bus and line geometries and characteristics) by combining domain knowledge with open datasets of distribution network layouts, district level electricity consumptions and building footprints. We then use this dataset to calculate descriptive attributes for each feeder as well as their maximal load hosting capacity and the associated type of constraint. Afterwards we perform a statistical analysis of the descriptive attributes in order to select the most relevant to use as inputs of the clustering algorithms. Finally, we apply a hierarchical agglomerative clustering algorithm with varying number of clusters, assess the quality of the results using internal and external validation and evaluate the ability of the medoids of each cluster to represent the behavior of the corresponding feeders.

I. INTRODUCTION

To achieve their long term goals of decarbonisation, many countries are planning to replace their use of fossil fuels by electric alternatives (e.g. EVs and heat pumps) along with the development of low-carbon electricity generation, including distributed renewable energies. From the standpoint of the electricity distribution network, this will entail shifts in loading conditions and power flows (including the possible appearance of reverse power flows). The extent to which these shifts will result in changes in operational and investment costs will depend on the electrical and topological characteristics of each medium and low voltage network as well as the geographical distribution of the associated loads and generations and their future evolution. As a consequence, evaluating the costs and benefits of a decarbonisation strategy (including the deployment of Smart Grid technologies such as distributed storage or VAR control) would, in theory, require the simulation 979-8-3503-9678-2/23/.00 ©2023 IEEE of projected load flows for every medium and low voltage network. As this would be impractical for large distribution networks comprising thousands of medium voltage networks and hundreds of thousand of low voltage networks, significant research interest has been devoted to identifying "representative" or "typical" medium or low voltage feeders. The purpose of this effort is to allow complex network studies to be performed on a limited subset of feeders, from which results for the complete set can be extrapolated. The first example of such a study is [START_REF] Willis | A Computerized, Cluster Based Method of Building Representative Models of Distribution Systems[END_REF], in which 12 representative medium voltage feeders are selected using a K-Means clustering algorithm. An external validation is performed by comparing the results of network studies (voltage drop, total losses, power factor, etc.) performed on the entire system with those extrapolated from the representative feeders. The second example is [START_REF] Fouda | Eigenvalue approach clustering algorithm for building equivalent models of distribution systems[END_REF] which used an eigenvalue approach to clustering to select representative feeders based on their impedance and active and reactive power flows. After the authors of [START_REF] Schneider | A Taxonomy of North American radial distribution feeders[END_REF] (summarized in [START_REF] Schneider | Modern Grid Initiative Distribution Taxonomy Final Report[END_REF]) produced a "taxonomy of 24 prototypical feeder models" for the U.S. Department of Energy, a renewed interest in the subject led to the publication of several studies following a similar pattern such as [START_REF] Li | Statistical identification of prototypical low voltage distribution feeders in Western Australia[END_REF], [START_REF] Broderick | Clustering methodology for classifying distribution feeders[END_REF] or [START_REF] Rigoni | Representative Residential LV Feeders: A Case Study for the North West of England[END_REF] : The authors in [START_REF] Bletterie | On the Classification of Low Voltage Feeders for Network Planning and Hosting Capacity Studies[END_REF] and [START_REF] Attila | Hierarchical Agglomerative Clustering of Selected Hungarian Medium Voltage Distribution Networks[END_REF] provide a complete review of such studies, in particular by categorizing them according to the type of clustering algorithm and the scales of both the system studied and the representative networks selected. In this article, we will adopt a similar approach and focus in particular on examining to what extent the networks selected can be used to extrapolate results on hosting capacity for the complete system. To achieve this, we will introduce quality measures of the clustering results related to the ability of the representative feeders to predict both the type of constraint and the hosting capacity of the feeders in their cluster.

II. DATASET CREATION

Obtaining a large enough, homogeneous and coherent network dataset (including network topology, line characteristics and load distributions) is the first step in the selection of representative networks. In this article, we will achieve this by relying on open datasets made available in France under a 2016 law governing the release of data produced by public entities. As these datasets do not contain all the information we need, we will combine them with domain knowledge to fill in the gaps. While the datasets are available for all of mainland France, we will focus in this study on Auvergne-Rhône-Alpes, a large region with a diverse mix of climate conditions and population densities.

A. Data sources

We will make use of three open datasets to create the network dataset :

1) Distribution network layout. This dataset contains the geographic positions of HV/MV and MV/LV substations as well the geometries of the MV and LV lines.

Overhead and underground lines are differentiated but no other characteristics are known. Currently the dataset is available only for the parts of the network managed by the french DSO ENEDIS (95% of the country size). 2) Local energy consumption. This dataset contains the annual energy consumptions (electricity and utility gas) as well as number of customer by sector (residential, industry, service sector, agriculture) and by IRIS 1 . 3) BD TOPO®, produced by IGN. This dataset contains, among other things, the footprints, sector (residential, industry, service sector, agriculture) and number of floors of every building

B. Network topology creation and line characteristics allocation

To establish the topology (i.e. how the lines and buses are connected), the first step is to create the set of feeders supplied by a given HV/MV substation by selecting the lines closest to the substation. Then the feeders are grown by connecting subsequent lines according to the proximity of their extremities. If a line can be connected to more than one feeder, it is connected to the shortest one. Buses are created at the points of connection between two lines. If a MV/LV substation is close to a bus, it is merged with it.

To allocate the line characteristics, two different procedures are applied for overhead and underground lines. For overhead lines, the backbone of the feeder is identified by iteratively adding to the backbone the line with the most downstream 1 Sub-municipal territorial division created for the purpose of statistics publication MV/LV substations, starting from the HV/MV substations. The procedure is stopped when there are no lines with more than 10 downstream MV/LV substations. Then the characteristics of 148 mm² cables are allocated to lines that are part of the backbone, while the other lines receive the characteristics of 54 mm² cables. For the underground lines, the feeders are separated into two categories : "dedicated" feeders supplying less than 5 MV/LV substations, for which the characteristics of 240 mm² cable are allocated, and other feeders for which the characteristics of 150 mm² cable are allocated.

This algorithm has been designed and implemented by Roseau Technologies.

C. Bus annual and peak load allocation

To allocate the annual and peak loads to each bus, we use the local energy consumption and BD TOPO®datasets in the following manner :

1) Determine the buildings inside each IRIS by performing a spatial join between building footprints and IRIS borders using the "within" relationship. For the building footprints that intersect several IRIS, assign them to the IRIS for which the intersection has the largest area. 2) For each building, calculate the floor area by multiplying the footprint area by the number of floors. If it is unknown, assume that there is one floor. 3) For each IRIS and each sector, allocate the annual load and number of customers to each building of the same IRIS and sector proportionally to its floor area 4) Define the building connected directly to the MV network as those for which the annual load by customer is above a given threshold. The threshold is set to 70 MWh/customer so that the number of MV customers fits publicly available country level statistics on MV customers. 5) Define a bus as supplying a MV customer when a MV/LV substation is present but no public LV network is connected to it. 6) Perform a spatial join between LV-supplied building footprints and LV buses using the "closest" relationship and aggregate the annual loads and number of customers if a bus is the closest one to several buildings. If there are multiples buses that are the closest ones for a given building, divide the annual loads and number of customers by the number of buses and allocate the result to them. Do the same for MV-supplied buildings and MV customer buses. 7) For each MV/LV substations with LV feeders connected to it, aggregate the annual loads and numbers of customers of the LV buses it supplies. 8) Compute the peak load by dividing the annual loads by a factor of 3900 hours for LV customers and 5500 hours for MV customers. These factors have been computed

using country level open data on 30-minute resolution load data.

D. Medium to low voltage transformer nominal power allocation

As we aim to compute the load hosting capacity of MV feeders, it is necessary to estimate the nominal power of MV/LV transformers as this can constitute a limit to the electricity supplied by a given feeder. To achieve this, we rely on domain knowledge of the nominal powers of standard transformers (between 50 kVA and 1000 kVA) and the associated share in the existing stock.

To assign a nominal power to each MV/LV substations substations supplying LV customers, we sort them by increasing order of peak load and associate them with increasing transformer nominal power while respecting the share of nominal powers in the existing stock. When the peak load is above 1000 kW, the first multiple of 1000 kW above the peak load is selected. The same procedure is applied to substations supplying MV customers.

E. Descriptive attributes

Using the procedure described above, we obtain a set of 4551 MV feeders supplied by 391 HV/MV substations, for which the topology, geometry, line characteristics and MV/LV substation nominal powers are known. From this, we compute a set of 24 descriptive parameters taken mainly from [START_REF] Schneider | A Taxonomy of North American radial distribution feeders[END_REF] and [START_REF] Bletterie | On the Classification of Low Voltage Feeders for Network Planning and Hosting Capacity Studies[END_REF], with particular care taken to include parameters relevant to hosting capacity estimation.

F. Elimination of erroneous feeders

Due to the exhaustivity of the source datasets, special purpose MV feeders (e.g. backup feeders) are present in the resulting dataset. After analyzing a sample of feeders, we have decided to remove the feeders with a total line length below 50 m or a total nominal power below 250 kVA. This corresponds to 395 feeders, or 8.7 % of the sample, but only 0.53 % of the total line length and 0.39 % of the total nominal power.

G. Load hosting capacity

The load hosting capacity of each feeder is computed by performing a sequence of power flows2 with increasing apparent power supplied to the MV/LV substations. At each step, the apparent power supplied to every substation is increased by 0.5 % until it reaches 110 % of the nominal power. Then, the compliance with voltage and thermal line rating constraints is evaluated for each step. If a constraint is violated at step N , the hosting capacity is set to the total active load supplied at step N -1 and the type of constraint ("voltage" or "line rating") is attributed to the feeder. If the constraints are violated in none of the steps, the hosting capacity is set to the total active load supplied at the last step and the type of constraint "transformer rating" is attributed to the feeder. The voltage compliance check is performed for minimal voltages ranging from 0.95 p.u. to 1.02 p.u. in order to evaluate the sensitivity to voltage quality requirements.

III. CLUSTERING A. Variable selection

Using correlated variables as clustering inputs can lead to bias, redundancy and create a false impression of cluster separation. To prevent this, we will select a subset of "poorlycorrelated" variables, using a methodology heavily inspired by [START_REF] Bletterie | On the Classification of Low Voltage Feeders for Network Planning and Hosting Capacity Studies[END_REF]. Concretely, we calculate the Spearman correlation coefficient for each pair of variables and apply a hierarchical clustering algorithm using the distance defined in Eq. 1.

Dist(x, y) = 1 -|Corr spearman (x, y)|

(1)

The rationale for such a procedure is to identify clusters of variables among which the correlation (negative or positive) is high. Fig. 1 displays the evolution of the distance between merged clusters as a function of the number of clusters, with an "elbow" suggesting the presence of 6 clusters. For each of the 6 clusters, we choose the variable with the highest relative standard deviation as its representative :

• Overhead line mean length (in km)

• Maximal line thermal capacity (in kVA)

• Total line length divided by total nominal power (in km/kVA) • Total nominal power of MV/LV substations (in kVA)

• kWΩ (see [START_REF] Bletterie | On the Classification of Low Voltage Feeders for Network Planning and Hosting Capacity Studies[END_REF])

• Impedance closeness

B. Algorithm description

While K-means clustering has drawbacks in the context of representative feeder identification 3 , it has been the most widely used for this purpose to date as it is more computationally efficient than the alternatives on large datasets. For this study, we have elected to use an agglomerative hierarchical clustering (AHC) with a Ward linkage and euclidean distance by taking advantage of the efficient implementation provided by [START_REF] Müllner | fastcluster: Fast hierarchical, agglomerative clustering routines for r and python[END_REF]. Input variables are standardized by removing the mean and scaling to unit variance. The number of clusters considered varies from 10 to 4150 by increment of 10. For each cluster, the medoid (i.e. the feeder whose average distance with the other cluster member is the smallest) is used as representative. 3 Difficulty in identifying non-globular, unevenly sized clusters

C. Internal validation

Internal validation of the clustering results is often used to assist in selecting a suitable number of clusters. It relies on quality measurements that depend only on the input variables. For AHC using Ward linkage, a straightforward option is to use the distance between the two clusters merged at any given step. In that case, the elbow method is applied to select the number of clusters. Another widely used quality measurement is the silhouette score, whose value should be maximised. Fig. 2 presents the two quality measurements for clusters counts varying between 2 and 100. Using the distance between merge clusters, the optimal number of clusters seems to lie between 20 and 30, while using the silhouette score it seems to lie between 10 and 15.

D. External validation

External validation consists in confronting the clustering results to an external measurement of quality, i.e. one not relying on the variables used in the clustering process. In general, this is performed after the internal validation, in order to verify that the number of clusters chosen is suitable for the purpose of the study. In our case, we want to ensure that the representative feeders are able to accurately estimate both the hosting capacities and the types of constraint of the feeders from their cluster. To illustrate this, Fig. 3 contains a scatter plot of actual feeder hosting capacity (minimal voltage set to 0.98) as a function of their representative feeder hosting capacity in the case of 30 clusters.

While this number of clusters was deemed suitable according to internal measurements, we can observe that the correlation between actual and predicted values is poor and that some clusters seem to contain feeders with different types of constraints.

By building on the works in [START_REF] Bletterie | On the Classification of Low Voltage Feeders for Network Planning and Hosting Capacity Studies[END_REF] and [START_REF] Broderick | Accuracy of clustering as a method to group distribution feeders by PV hosting capacity[END_REF], we propose two external quality measures that can be computed for each number of clusters :

• The coefficient of determination of the predicted hosting capacity relative to the actual one, which aims at measuring the ability of the representative feeders to predict the hosting capacity of their cluster members. • The share of feeders with a type of constraint identical to their representative feeder, which aims at measuring the Fig. 3: Actual vs predicted hosting capacities (30 clusters) ability of the representative feeders to predict the type of constraint of their cluster members. As an example, in the case presented in Fig. 3, the coefficient of determination is 0.66, while the share of feeders with a correct type of constraint is 81.4 %. While the specific level of accuracy needed is purpose-dependent, it is safe to say that such a low level would not be suitable for most of the applications of representative that have been envisioned. Fig. 4 and Fig. 5 show the evolution of the two external quality measurements for numbers of clusters ranging from 10 to 1000, and for the range of minimal voltages considered.

E. Result interpretation

In a broad sense, we have managed to reproduce both the results in [START_REF] Broderick | Accuracy of clustering as a method to group distribution feeders by PV hosting capacity[END_REF], where large dispersions of hosting capacities inside clusters were observed when using numbers of clusters in the range of 10 to 30, and the results of [START_REF] Bletterie | On the Classification of Low Voltage Feeders for Network Planning and Hosting Capacity Studies[END_REF], where relatively low levels of constraint type purity were observed when using numbers of clusters below 10. However, it should be noted that the quality measurements used in those studies (boxplot-based Fig. 5: Quality measurement of constraint type prediction in [START_REF] Broderick | Accuracy of clustering as a method to group distribution feeders by PV hosting capacity[END_REF] and cluster purity in [START_REF] Bletterie | On the Classification of Low Voltage Feeders for Network Planning and Hosting Capacity Studies[END_REF]) only aim at measuring the level of homogeneity inside clusters, while the measurements introduced here aim at measuring the quality of the prediction provided by the representative feeders. As a consequence, these can be used to select a number of clusters (and thus representative networks) to use in a particular study as a function of the level of accuracy expected for the study.

We can also observe that both quality measurements increase rapidly up to around 200 clusters, after which the incremental gains accrued by increasing the number of clusters become marginal. Thus we can consider that, absent specific accuracy requirements, the choice of 200 clusters represents a good compromise between number of clusters and quality (see Fig. 6 for a scatter plot with 200 clusters). We can remark that this is one to two orders of magnitude higher than what is generally considered an optimal choice of number of clusters (see Table 2 in [START_REF] Attila | Hierarchical Agglomerative Clustering of Selected Hungarian Medium Voltage Distribution Networks[END_REF], in which 10-25 is considered a "large number" of clusters). In this study, we have applied an agglomerative hierarchical clustering algorithm to a set of more than 4000 MV feeders in order to extract representative feeders. We have then employed internal quality measurements that are generally used to determine the optimal number of clusters and have shown that this approach leads to a number of clusters that is too small to adequately represent the diversity of feeder behaviour in terms of load hosting capacity. This has led us to introduce two new external quality measurements related to the hosting capacity. These new measurements suggest that the appropriate number of clusters is one to two orders of magnitude higher than what is generally admitted. While this result is significant in itself, several avenues of inquiry remain open, in particular pertaining to its generalization to other clustering algorithms, feeder datasets (especially larger datasets) and study objectives (e.g. PV hosting capacity or Volt-Var control).

1 )

 1 Computation of feeder parameters 2) Elimination of outliers or erroneous feeders 3) Statistical study of feeder parameters (e.g. analysis of correlation and principal components) 4) Selection of parameters to use as inputs of the clustering algorithm 5) Selection and design of the clustering algorithm, including the selection of the number of clusters 6) Interpretation and/or validation of the results

Fig. 1 :

 1 Fig. 1: Distance between merged clusters

Fig. 2 :

 2 Fig. 2: Clustering internal quality measurements

Fig. 4 :

 4 Fig. 4: Quality measurement of hosting capacity prediction

Fig. 6 :

 6 Fig. 6: Actual vs predicted hosting capacities (200 clusters)

BFS using a three-phase balanced, radial, line impedance model as described in[START_REF] Sy Abdelouadoud | Optimal power flow of a distribution system based on increasingly tight cutting planes added to a second order cone relaxation[END_REF]. The source voltage is set to 1.03 p.u.


Olivier Devillers
email: olivier.devillers@inria.fr

Sylvain Lazard
email: sylvain.lazard@inria.fr

One-Bend Drawing of K_n in 3D, revisited

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

doi:10.7155/jgaa.00079 doi:10.7155/jgaa.00095 doi:10.7155/jgaa.00128 Drawing of complete bi-partite graph K k,k 2.1 General idea of [START_REF] Cohen | Three-dimensional graph drawing[END_REF][START_REF] Devillers | Drawing Kn in Three Dimensions with One Bend per Edge[END_REF] constructions Make k groups of n k vertices

The complete graph of each group is below its line The complete bi-partite graph between each pair

Y max = O( p n log n) Volume = O(n 2 log 2 n) p n O u r re su lt [ 3 ] Y max p n log 2 n
Comparison with [START_REF] Devillers | Drawing Kn in Three Dimensions with One Bend per Edge[END_REF] Plot of

Box = [0, 1] ⇥ [0, k] ⇥ [ k 2 2 , 0]
Vertices on Y -axis Bends at X = 1, Z <0

Vertices on lines parallel to Y -axis

Grid of bends at X = constant Can be done in a box

[0, 2] ⇥ [0, k] ⇥ [0, k] X Y Z

Distinct edges:

) they lie in distinct pages have bends at distinct Z Although graphs are usually drawn in 2D, some authors have considered 3Ddrawings with vertices placed on an integer grid and try to minimize the volume of the enclosing box. If the edges are constrained to be straight line segments, Cohen et al. [START_REF] Cohen | Three-dimensional graph drawing[END_REF] proposed a crossing free drawing of the complete graph K n within an optimal bounding box of volume ⇥(n 3 ). Some authors consider the possibility of allowing some bends per edges. Bose, et al. [START_REF] Bose | The maximum number of edges in a three-dimensional grid-drawing[END_REF] showed a ⌦(n 2 ) lower bound on the volume of a kbend drawing of K n (for any k). Dyck et al. [START_REF] Dyck | Drawing Kn in Three Dimensions with Two Bends Per Edge[END_REF] achieved a O(n 2 ) construction with two bends per edge. If we restrict the number of bends to at most one per edge, Morin and Wood [START_REF] Morin | Three-dimensional 1-bend graph drawings[END_REF] k vertices and use two basic tools: the collinear drawing of the complete graph of each group (all vertices of a group are collinear) and the bi-collinear drawing of the complete bi-partite graph for each pair of groups (vertices are on two parallel lines). The trick is to arrange these subgraphs so that their hulls are disjoints.

Our ideas:

In this paper, we allow the hulls of some bi-partite graphs to intersect provided that the bunches of edges do not intersect. Edges are drawn iteratively, checking the possible conflicts with already drawn edges. We draw the complete graph in a box of size [0,

p n] ⇥ [0, Y max ] ⇥ [ n, n log n],
where Y max is computed for each n. We conjecture and check experimentally that Y n = O( p n log n) reaching a volume of O(n 2 log 2 n) close to the quadratic lower bound. Collinear drawing of complete graphs. Morin and Wood proposed to draw the complete graph K k with all vertices on the Y -axis and O(k 3 ) volume (with various aspect ratio for the enclosing box). We will use it with a box [0

, 1] ⇥ [0, k] ⇥ [ k 2 2
, 0] by placing the vertices at (0, i, 0) for i 2 [0, k) and bend at (1, y, j) where y is any integer in [0, k] and j is used to number the k(k 1) 2 edges of K k . Each edge is drawn in its own page (plane containing the Y -axis), and thus there are no crossings.

X Y Z X Y Z
Bi-collinear drawing of complete bi-partite graphs. The construction proposed by Morin and Wood [5, §3] uses, as building blocks, drawings of complete bi-partite graphs with exactly one bend point per edge. These drawings are called one-bend bi-collinear drawings because the two sets of vertices of K n,m are furthermore constrained to lie on two different lines parallel to the Y -axis.

Vertices are placed at (0, i, 0) for 0 6 i < n and (x, y + j, z) for 0 6 j < m with (x, y, z) 2 Z 3 . The bend point is placed at (x 0 , j, z 0 + i) 0 < x 0 < x and z 0 2 Z Choosing x 0 = 1, z 0 = 0, (x, y, z) = (2, 0, 0), the volume is 3nm. Notice that this construction is contained in two convex bodies, called wedges, which are the convex hulls of, respectively, the bends and the n vertices, and the bends and the m vertices. Disjointness of edges is granted by considering the different planes parallel to the Yaxis they belong to.

Notice that this construction still works if we place the bends of the edges from (0, i, 0) to (x, y + j, z) at (x 0 , y ij , z 0 + i) (instead of (x 0 , j, z 0 + i)) where (y i,j ) j are sequences of integers that are strictly increasing with j (sequences may depend on i).

Our construction.

We follow the idea of previous constructions to (i) split the set of n vertices in k groups of size n k , (ii) place the groups on some lines parallel to the Y -axis in the XY -plane, (iii) draw for each group its complete graph in a box below the XY -plane, and (iv) draw for each pair of groups its complete bi-partite graph in two wedges above the XY -plane. However, unlike previous constructions, we allow the possibility for some wedges to intersect, although the different line segments in the wedges remain crossing free. We thus propose the following strategy: -We split the vertices in k = p n groups of k vertices. -Vertex v i,j , 0 6 i, j < k is at coordinates (2i, j, 0). -The complete graph of group v i,? is drawn in the box

[2i, 2i + 1] ⇥ [0, k] ⇥ [ k 2
, 0]. -The bend for the edge from v i,j to v i 0 ,j 0 with i < i 0 is placed at e i,j,i 0 ,j 0 = (i 0 + i, y i,j,i 0 ,j 0 , z i 0 i k j) where

X Z n n log n 2 p n z 1 = 1, z i = l i i 1 z i 1 m + 1
, and y i,j,i 0 ,j 0 is determined algorithmically. Such a placement guarantees disjoint up-going (resp.down-going) wedges and a maximal height of O(n log n). To avoid intersections between up-going and down-going segments the bends are placed iteratively at the smallest y that preserves the monotonicity and does not create crossing with already drawn edges. We achieve a drawing within a box

[ 2 , 3 ] 1 .

 231 : use distinct k and distinct placements Consecutive Y unnecessary Use monotonic Y Given X and Z Our contribution: O(n 2 log 2 n) Conjecture Experimental validation The problem: Vertices with integer coordinates Edges = two line segments (bend at int) Minimize volume of enclosing box Known:

FullZZ 3 2

 3 version: inria.hal.science/hal-04182069 X Y Each group is on a line parallel to the Y -axis 3.2 Our ideas: Make p n groups of p n vertices at Z = 0 Complete graph of each group below Z = 0 Complete bi-partite graph of each pair of groups Up/Down intersection n X Iterative top-down drawing to avoid edge intersections n log n 2 p n Drawing in [0, 2 p n] ⇥ [0, Y max ] ⇥ [ n 2 , n log n] Intersecting wedges Disjoint upgoing wedges Disjoint dowgoing wedges Shift new bend in Y Volume = O(Y max n log n)

  [0, Y max ] ⇥ [ n, n log n], where Y max = O(n 2 ) is determined by the algorithm. Based on the the computation of Y max for many values of n (see below), we conjecture that Y max = O( p n log n), yielding a volume of O(n 2 log 2 n).

  get a volume of O( n 3 log 2 n ), later improved by Devillers et al. to O(n 2.5 ) [3]. Both constructions split the set of vertices in k groups of n