Loann Giovannangeli

Frederic Lalanne

Romain Giot

Romain Bourqui

IN IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 1 Overlap Removal by Stochastic Gradient Descent with(out) Shape Awareness

Keywords: Layout adjustment, Overlap removal, Stress optimization, Stochastic gradient descent

In many 2D visualizations, data points are projected without considering their surface area, although they are often represented as shapes in visualization tools. These shapes support the display of information such as labels or encode data with size or color. However, inappropriate shape and size selections can lead to overlaps that obscure information and hinder the visualization's exploration. Overlap Removal (OR) algorithms have been developed as a layout post-processing solution to ensure that the visible graphical elements accurately represent the underlying data. As the original data layout contains vital information about its topology, it is essential for OR algorithms to preserve it as much as possible. This article presents an extension of the previously published FORBID algorithm by introducing a new approach that models OR as a joint stress and scaling optimization problem, utilizing efficient stochastic gradient descent. The goal is to produce an overlap-free layout that proposes a compromise between compactness (to ensure the encoded data is still readable) and preservation of the original layout (to preserve the structures that convey information about the data). Additionally, this article proposes SORDID, a shape-aware adaptation of FORBID that can handle the OR task on data points having any polygonal shape. Our approaches are compared against state-of-the-art algorithms, and several quality metrics demonstrate their effectiveness in removing overlaps while retaining the compactness and structures of the input layouts.

INTRODUCTION

In most 2D visualizations, data are projected from an initial highdimensional space and represented as shapes, either to encode some of its properties or to fulfill some aesthetic criteria. However, most layout algorithms (e.g., Multi Dimensional Scaling [START_REF] Tipping | Probabilistic principal component analysis[END_REF], [START_REF] Van Der Maaten | Visualizing data using t-SNE[END_REF], Graph Layout [START_REF] Hachul | Drawing large graphs with a potential-fieldbased multilevel algorithm[END_REF], [START_REF] Kamada | An algorithm for drawing general undirected graphs[END_REF], [START_REF] Zheng | Graph drawing by stochastic gradient descent[END_REF]) process data points as elements without shape or size. If not chosen carefully, these shapes and sizes can create overlaps in the visualization, and severely hinder its exploration by hiding information. Resolving these overlaps is still an open problem referred to as the Overlap Removal (OR) task [START_REF] Chen | Node overlap removal algorithms: A comparative study[END_REF], [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF].

If not directly handled by the dimension reduction algorithm (e.g., [START_REF] Harel | Drawing graphs with non-uniform vertices[END_REF], [START_REF] Kamps | Constraint-based spring-model algorithm for graph layout[END_REF]), it is then the responsibility of a post-processing OR algorithm to solve the task. Such algorithms take a set of data points with properties such as position, shape and size as input and move them to remove all the existing overlaps. The produced layout is called overlap-free; and is supposed to improve the readability of the initial layout. As described by Chen et al. [START_REF] Chen | Node overlap removal algorithms: A comparative study[END_REF], [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF] survey, we identify two main criteria an OR algorithm should optimize to achieve satisfactory overlap-free layout: (i) the preservation of the compactness, C comp. ; and (ii) the preservation of the initial layout C lay. , described in the following.

The C comp. criterion states that an overlap-free layout should limit the increase in surface of the initial layout. Indeed, an algorithm that uniformly upscales the coordinates of the initial layout until there is no overlap solves the task (e.g., uniform Scaling [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF]) as long as there is no perfect overlap (i.e., data with the exact same position). However, upscaling the initial layout implies to reduce the graphic element sizes when rendered in a viewbox of fixed size (e.g., viewport on a monitor). Such upscaling should remain limited, otherwise the data encoded within the shape representations becomes too small and unreadable.

The other criterion, C lay. , defines the necessity to preserve the initial layout structures. As post-process OR algorithms are applied on already designed layouts, they must expect that these layouts were already generated by some algorithm, or even manually built to encode some task-relevant information. Preserving the user mental map [START_REF] Eades | Preserving the mental map of a diagram[END_REF] is mandatory to ensure they can relate the data points in the adjusted layout to those in the initial one. Hence, input layouts must be considered as ground truths from which the OR algorithm should not deviate too much.

While overlap can exist in any 2D visualization, we consider the OR task in a graph layout context in this article. The Graph Drawing community has always been involved in research on the OR task and we leverage its literature to extend the research (see Section 2). Thus, the data points in this article are nodes positioned by a graph layout algorithm. Overlaps between the nodes are considered in the geometric space, such that two nodes overlap if the intersection of their shape representation is not null.

This article proposes an extended version of FORBID [START_REF] Giovannangeli | FORBID: Fast Overlap Removal By stochastic gradIent Descent for Graph Drawing[END_REF] (Fast Overlap Removal by Stochastic Gradient Descent) and also presents SORDID, its shape-aware generalization. Both are Overlap Removal algorithms that aim at optimizing the C lay. and C comp. criteria explicitly. Their idea is to combine a search for an optimal scale of the initial layout with some node movements to remove the overlaps. The optimal scale is found by binary search. At each step in the binary search, node movements are computed to remove overlaps modeling a stress optimization problem. The stress optimization is realized with a simulated Stochastic Gradient Descent algorithm from the literature [START_REF] Zheng | Graph drawing by stochastic gradient descent[END_REF] with a fixed number of iterations. Fixing the number of iterations comes down to give the algorithm a limited budget of node movements. Thus, it looks for the minimum scale (i.e., optimizing C comp. ) at which it can remove overlaps by using at most budget movements (i.e., optimizing C lay. ).

As far as we know, FORBID is the first OR algorithm to explicitly include the initial layout upscaling as a property to optimize. Most algorithms from the literature measure the upscaling as a side-effect of the node movements but do not explicitly control it.

The first contribution of this article is an extensive presentation of FORBID [START_REF] Giovannangeli | FORBID: Fast Overlap Removal By stochastic gradIent Descent for Graph Drawing[END_REF] algorithm. Being designed to remove overlaps in layouts where all the nodes have a common shape (e.g., rectangle, circle), it can't handle nodes with any shape efficiently. The common way to adapt standard OR algorithms to any shape is by approximating the node shapes by their bounding box, either circular or rectangular (see Figure 1c). However, such approximation is not efficient as many empty spaces remain unused. Hence, the second contribution of this article is the generalization of FORBID to polygonal nodes. This shape-aware extension is referred to as SORDID and can remove overlaps in layouts where nodes have any polygonal shape by decomposing them into triangles with a Delaunay triangulation [START_REF] Chew | Constrained delaunay triangulations[END_REF]. The overlap removal task is then considered between sets of triangles composing the nodes, and it is able to produce overlap-free layouts with fine adjustments (including imbrications) of the polygonal nodes, as presented in Figure 1d. Finally, both approaches are evaluated and compared with state-of-the-art algorithms on a set of quality metrics specifically selected for this purpose. The evaluation includes various node shapes and demonstrates our algorithms capabilities to optimize the C comp. and C lay. criteria. FORBID 1 and SORDID 2 implementations are available online.

The remainder of this paper is organized as follows. Section 2 presents related works principally centered around the description of OR algorithms and their evaluation as proposed in [START_REF] Chen | Node overlap removal algorithms: A comparative study[END_REF], [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF]. Section 3 describes FORBID algorithm and SORDID, its shapeaware adaptation. Section 4 reports their evaluation and comparison with state-of-the-art algorithms, while Section 5 discusses visual 1 FORBID: github.com/labribkb/FORBID 2 SORDID: github.com/labribkb/sordid examples of overlap-free layouts from several OR algorithms, and our algorithms convergence. Finally, Section 6 concludes the article and presents leads for future works.

Notations: Let G = (V, E) be an undirected graph with V = {v 1 , v 2 , ..., v N } its set of N = |V | nodes and E ⊆ V × V its set of edges. A graph layout is defined as a tensor X ∈ R N×2 where X i is the 2D projection of the node v i . An initial (i.e., input) layout is denoted by X 0 while a corresponding overlap-free layout is denoted by X ′ . For convenience, we define the set of overlapping pairs of nodes in a graph by O ⊆ V ×V . The Euclidean distance between v i and v j is denoted ||X i -X j ||. The minimal rectangle in which all node representations of a layout fit in is called the Bounding box of the layout and is denoted BB.

RELATED WORKS

This section presents related works on the Overlap Removal task, and describes some of its main algorithms. Moreover, some methods tackling Overlap Removal with a different approach or in different contexts (e.g., scatterplots) are discussed.

Motivation for Post-process Overlap Removal

The main goal of Overlap Removal (OR) algorithms is to produce drawings where all the information can be visualized. Hence, some works [START_REF] Harel | Drawing graphs with non-uniform vertices[END_REF], [START_REF] Kamps | Constraint-based spring-model algorithm for graph layout[END_REF] proposed graph layout algorithms that directly handled nodes with a shape and area, and guaranteed that the graph layout would not contain overlap. Harel and Koren [START_REF] Harel | Drawing graphs with non-uniform vertices[END_REF] proposed an adaptation of the seminal Kamada-Kawai [START_REF] Kamada | An algorithm for drawing general undirected graphs[END_REF] stress layout algorithm to produce graph drawings with elliptical nodes where there is neither node-node nor edge-node overlap. Handling the node sizes while laying them out is theoretically the ideal approach. However, in practice, many layout algorithms are designed without considering the node shapes (and thus overlap) constraints, and it is not possible to overload each and every layout technique to handle overlaps. The overlaps appear during the graph layout rendering, and the node shapes and sizes are design choices either set arbitrarily (i.e., it is more aesthetically pleasing to visualize shapes than dots) or to map some node properties on their representation. Hence, generic post-process OR algorithms were designed to satisfy the overlap-free constraint of any layout. The main difference between them is their input. Pre-process algorithms being coupled with the layout process, they can leverage the graph structure itself, while post-process algorithms usually assume they only have access to some minimalist geometric data (i.e., the node positions, shapes and sizes in 2D). In fact, most post-process Overlap Removal algorithms do not use the input graph edges at all. The main criterion for these algorithms is to minimize the deformation of their input layout, since it already conveys some semantics of the data and must be considered as ground-truth.

Post-Process Overlap Removal Algorithms

To remove all the node-node overlaps in a layout, the first step is to identify them. The naive way to find all overlaps (or detect if there is at least one) is to search exhaustively between all pairs of nodes, leading to a complexity in O(N 2 ). Dwyer et al. [START_REF] Dwyer | Fast node overlap removal[END_REF] proposed scan-line to search for overlaps by sorting the nodes horizontally and vertically at first. It enables to skip many comparisons and significantly accelerates the search. It achieves a complexity of O(N log N) to detect if a layout contains overlaps. The algorithm remains quadratic on the number of nodes to identify all the overlaps in a layout, but in practice the skipped comparisons make it significantly faster than a full pairwise search. Many OR algorithms (e.g., [START_REF] Hayashi | A layout adjustment problem for disjoint rectangles preserving orthogonal order[END_REF], [START_REF] Huang | A new algorithm for removing node overlapping in graph visualization[END_REF], [START_REF] Misue | Layout adjustment and the mental map[END_REF]), including the method presented in the article, rely on this scan process to detect overlaps.

The state-of-the-art of OR algorithms is well described in Chen et al. [START_REF] Chen | Node overlap removal algorithms: A comparative study[END_REF], [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF] surveys, and these algorithms focus on the main criteria C comp. and C lay. (see Section 1). PFS [START_REF] Misue | Layout adjustment and the mental map[END_REF], PFS' [START_REF] Hayashi | A layout adjustment problem for disjoint rectangles preserving orthogonal order[END_REF], FTA [START_REF] Huang | A new algorithm for removing node overlapping in graph visualization[END_REF], RWordle-L [START_REF] Strobelt | Rolledout Wordles: A Heuristic Method for Overlap Removal of 2D Data Representatives[END_REF] and uniform scaling [START_REF] Chen | Node overlap removal algorithms: A comparative study[END_REF], [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF] rely on the scan line algorithm to identify overlaps and remove them sequentially. PFS, PFS' and FTA are made of two passes handling horizontal and vertical movements separately, while RWordle-L moves nodes on both axes simultaneously. All these algorithms have a quadratic complexity as they process all pairs of nodes at some point (e.g., when moving them).

Mariott et al. [START_REF] Marriott | Removing Node Overlapping in Graph Layout Using Constrained Optimization[END_REF] proposed several approaches to remove overlaps in a layout based on constrained optimization to maximize the C lay. criterion. The main goal of these approaches is to preserve the user mental map [START_REF] Eades | Preserving the mental map of a diagram[END_REF] of the graph so that he can understand how the nodes/edges in the adjusted layout relate to those in the initial layout. VPSC [START_REF] Dwyer | Fast node overlap removal[END_REF], [START_REF] Dwyer | Fast node overlap removal-correction[END_REF] also models OR as a set of constraints to relax but tends to highly deform the initial layout. Its complexity is O(CN logC) where C is the number of constraints in O(N); leading to a final complexity in O(N 2 log N). Finally, Diamond [START_REF] Meulemans | Efficient optimal overlap removal: Algorithms and experiments[END_REF] is another constraint programming-based OR algorithm in O(N 2 ) that optimizes orthogonal order preservation. Its originality is to temporarily rotate nodes by 45 • , representing them as diamonds to ease the constraint relaxations.

Gansner and North [START_REF] Gansner | Improved Force-Directed Layouts[END_REF] introduced the idea of a proximity model to remove overlaps. Their algorithm computes a Voronoi diagram using the center of polygonal nodes. Then, every overlapping node is moved to the centroid of its Voronoi cell. If this step does not resolve all the overlaps, the layout coordinates are upscaled to expand the drawing, and the process is restarted. In addition to node-node overlaps, they propose a method to remove node-edge overlaps, allowing edge bends when necessary. While this algorithm is claimed to handle nodes represented by any polygonal shape, it only makes use of the node shapes to identify the overlaps. By design, this approach is not prone to enable node shapes imbrication to minimize node movements, since the nodes are always moved from their position to the centroid of their Voronoi cell.

Finally, PRISM [START_REF] Gansner | Efficient, proximity-preserving node overlap removal[END_REF], [START_REF] Gansner | Efficient node overlap removal using a proximity stress model[END_REF] is, as far as we know, the first stressbased OR algorithm. It models OR as a stress optimization problem in a proximity graph defined as the Delaunay triangulation of the initial layout. The proximity graph models the shortest distances in the initial layout, and PRISM optimizes distances alongside its edges assuming that these are where the overlaps are most likely to occur. As this assumption is often not exact, they iteratively augment the proximity graph's edges and re-compute forces until there is no overlap. In the end, PRISM is in O(t(mkN + N log N)) where m and k are optimization hyper-parameters, and t depends on the number of overlaps (that can be greater than N). GTREE [START_REF] Nachmanson | Node overlap removal by growing a tree[END_REF] is another stress-based algorithm that leverages PRISM proximity graph to remove overlaps, building a minimum spanning tree upon it to reduce the number of forces to compute. Both GTREE and PRISM results showed that stress-based approaches to OR could be very efficient. These methods are the closest ones to FORBID and SORDID, since they also model the node movements as a stress optimization task.

Most of the OR algorithms presented in this section are designed to solve the task on nodes with the same shape. In practice, the node shapes could be different as long as it is possible (i) to check if two nodes overlap, and (ii) to compute the distance between two nodes such that they do not overlap. Nonetheless, their design and implementation focus on the context where nodes have a common shape and they are evaluated as such. The exception is the work of Gansner and North [START_REF] Gansner | Improved Force-Directed Layouts[END_REF] that is adaptable to layouts with varying node shapes to a certain extent (e.g., as long as the node shapes are not significantly larger than their Voronoi cell). However, none of these algorithms are designed to leverage the node shapes to improve the adjustments brought to the layout. In SORDID, our goal is to make use of the node shapes to detect overlaps and compute node displacements in order to produce finer adjustments of the layout, making use of empty spaces that exist within the bounding box of node representations.

Overlap Removal for other Criteria

Other techniques have been designed to achieve OR task, but with different focuses. In the following, we present two works that are worth mentioning, although they are not part of our benchmark as they do not tackle the same problem. More specifically, they are dedicated to scatterplots with a focus on scalability, while most of the methods presented above focus on quality and do not scale well due to their quadratic complexity.

DGRID was originally designed to produce compact visualizations [START_REF] Hilasaca | A visual approach for user-guided feature fusion[END_REF], [START_REF] Mamani | A visual approach for user-guided feature fusion[END_REF], where every datum corresponds to exactly one pixel on screen, and they adapted it to OR in more generic scatterplots [START_REF] Hilasaca | Overlap Removal of Dimensionality Reduction Scatterplot Layouts[END_REF]. The algorithm's idea is to create a grid over the initial layout, with dummy points representing locations where actual nodes could be moved minimizing displacement. Then, the nodes are assigned to grid cells using a KD-tree [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF] as the spatial partitioning strategy. DGRID is in O(N log N) and among the fastest OR methods because it does not need to identify overlaps as the position gridifications intrinsically make them impossible. However it suffers from local distortions due to the grid boundaries that limit the node displacements.

ScatterplotUnfold [START_REF] Li | Dual Space Coupling Model Guided Overlap-Free Scatterplot[END_REF] is a recent overdraw removal technique. As opposed to all the algorithms presented above, it focuses on the Visual Space (which is why they handle overdraw and not overlap). The algorithm does not necessarily aim at removing overlaps, but rather focuses on the preservation of the data representation on screen. Their goal is to preserve the visualization of clusters and the density distribution of the initial drawing. To achieve this, they manipulate parameters relative to the layout rendering (e.g., node color, transparency, radius on screen). FORBID and SORDID fit in the category they call Node dispersion and from which they aim at overcoming the intrinsic flaws (e.g., density distribution preservation, computational efficiency).

GIST [START_REF] Giovannangeli | Guaranteed Visibility in Scatterplots with Tolerance[END_REF] is another Visual Space algorithm that uses stochastic gradient descent to resolve overdraws, and aims at guaranteeing the nodes visibility in the final image that represents the layout. The originality of this algorithm is to mix the optimization of the node movements in the Geometric Space, with constraints on the node sizes in the Visual Space to make sure that they remain visible in the desired image resolution. It also uses a bounded tolerance to soften the overlap constraints and ease its optimization process.

Other approaches such as Data Abstraction [START_REF] Chen | Visual abstraction and exploration of multi-class scatterplots[END_REF], [START_REF] Mayorga | Splatterplots: Overcoming overdraw in scatter plots[END_REF] or Sampling [START_REF] Chen | A recursive subdivision technique for sampling multi-class scatterplots[END_REF], [START_REF] Chen | Pyramid-based Scatterplots Sampling for Progressive and Streaming Data Visualization[END_REF] have been designed to process 2D scatterplots and ensure that they faithfully represent the original data. However, these methods do explicitly focus on reducing the number of represented elements to avoid overdraws. This strategy is not the scope of this article which is why we do not discuss them further.

FORBID AND SORDID ALGORITHMS

This section presents FORBID, a post-process Overlap Removal (OR) algorithm, and SORDID, its generalization to generic node shapes. Both algorithms follow the same structure, and aim at optimizing a stress function by simulating stochastic gradient descent while looking for the optimal upscaling ratio of the initial layout. Figure 2 presents a high-level abstraction view of the building blocks the algorithms are made of.

FORBID

This section presents FORBID (for Fast Overlap Removal by Stochastic Gradient Descent), and focuses on rectangular nodes.

Stress Model for Overlap Removal

Stress for graphs. Inherited from the MultiDimensional Scaling (MDS) [START_REF] Kruskal | [END_REF], the stress energy function has demonstrated great performance as an objective function in the graph context, and especially in graph layout algorithms [START_REF] Brandes | An experimental study on distance-based graph drawing[END_REF], [START_REF] Kamada | An algorithm for drawing general undirected graphs[END_REF], [START_REF] Ortmann | A sparse stress model[END_REF], [START_REF] Zheng | Graph drawing by stochastic gradient descent[END_REF]. The stress function can be expressed as:

σ (X) = ∑ v i ,v j ∈V W i j (||X i -X j || -δ i j ) 2 (1)
where δ i j represents the ideal distance between nodes v i and v j , and W i j is a weighting factor for the pair (v i , v j ). W i j is usually set to δ -2 i j such that the higher the ideal distance between two nodes is, the less they produce energy. Optimizing stress then comes down to fit a distribution of distances in a low-dimensional space (e.g., 2D) to the distribution of ideal distances taken from a high-dimensional space too complex to be represented.

The goal of graph layout algorithms is to map every node from the theoretical space to a 2D position. Thus, stress was intuitively adapted in this context by setting the ideal distance between pair of nodes to their shortest path length in the theoretical object.

A similar reasoning was proposed by Gansner and Hu [START_REF] Gansner | Efficient, proximity-preserving node overlap removal[END_REF] to adapt the stress to the Overlap Removal task in PRISM. The idea ``zoom out" Fig. 2: Simplified workflow of FORBID algorithm representing how the stress and upscaling criteria are organized together. Gears represent the algorithms FORBID relies on (i.e., S GD 2 [START_REF] Zheng | Graph drawing by stochastic gradient descent[END_REF] and scan line [START_REF] Dwyer | Fast node overlap removal[END_REF]), and colored boxes represent layouts while white boxes represent the search for the optimal scaling. is to tailor the notion of ideal distance such that optimizing the function will tend to remove overlaps while also preserving the initial layout. This is done by defining a two folded ideal distance. If a pair of nodes p i j = (v i , v j ) does not overlap (i.e., p i j / ∈ O), the ideal distance is set to their distance in the initial layout δ i j = ||X 0 i -X 0 j ||. This states that if two nodes do not overlap, the distance between them should be preserved. On the other hand, if p i j ∈ O, the ideal distance is set to some value such that the two nodes do not overlap anymore. That way, fitting the ideal distances distribution will intrinsically remove overlaps. The actual ideal distance value between two nodes is a design choice that must be high enough so that they do not overlap anymore. Nevertheless, it must also remain small enough since two nodes that overlap in the initial layout should remain close in the overlapfree layout. For example, PRISM [START_REF] Gansner | Efficient, proximity-preserving node overlap removal[END_REF] defined their ideal distance as δ i j = r i j ||X i -X j || where r i j is the minimal expansion factor of the vector --→ X i X j such that the two nodes are moved following the direction between their centers until they do not overlap anymore.

This model of ideal distances comes down to create a space in which the distances between all pairs of nodes in the initial layout are preserved, and there is no longer any overlap. Such a space cannot be in 2D as preserving the distances between all pairs of nodes is not possible when we move some of them to remove overlaps. This ideal space is necessarily of higher dimension. The stress optimization then tries to fit the distribution of distances in the 2D plan to this ideal high dimensional space.

FORBID stress implementation. In contrast to PRISM, the ideal distance between two nodes in FORBID is set according to their size. More formally, it is the distance between v i and v j centers if they were tangent in their corner as shown in Figure 3:

δ i j =        ||X 0 i -X 0 j ||, if (v i , v j ) / ∈ O w i +w j 2 2 + h i +h j 2 2 , if (v i , v j ) ∈ O (2)
where X 0 is the initial layout, while w k and h k are the width and height of the node v k . Having too tight a definition of the ideal distance such as PRISM's one means that there is only one direction alongside which the nodes can be moved to satisfy that distance.

On the other hand, our model of the ideal distances makes sure that two nodes cannot overlap anymore no matter what their relative position is. We expect that this constraint will be easier to relax Fig. 3: FORBID ideal distance for an overlapping pair of nodes as defined in Equation 2. This is the smallest distance such that the nodes cannot overlap, no matter what their relative position is.

overall and ease the algorithm's convergence; though it might come at the cost of some inversions in the nodes orthogonal order. Finally, the weight factor W i j is an adjustable power of δ i j based on whether two nodes v i and v j overlap:

W i j =    δ α i j , if (v i , v j ) / ∈ O δ α * K i j , if (v i , v j ) ∈ O (3)
where α ∈ R is a factor related to the ideal distance between the nodes (typically set to α = -2 such that the closer two nodes are, the higher their weight is), and K ∈ R is a weight to tune the importance given to overlapping pairs of nodes.

Stress Optimization

Among the existing approaches to optimize a stress function [START_REF] Ahmed | Multicriteria Scalable Graph Drawing via Stochastic Gradient Descent[END_REF], [START_REF] Ahmed | Graph Drawing via Gradient Descent, (GD) 2[END_REF], [START_REF] Devkota | Stress-Plus-X (SPX) Graph Layout[END_REF], [START_REF] Wang | Revisiting stress majorization as a unified framework for interactive constrained graph visualization[END_REF], FORBID leverages that of S GD 2 [START_REF] Zheng | Graph drawing by stochastic gradient descent[END_REF]. The originality of S GD 2 is to propose a constraint relaxation framework that mimics a stochastic gradient descent to optimize the objective function.

In standard stress optimization algorithms, every node movement is computed by an aggregation of attraction and repulsion forces with every other node in the graph. To overcome the cost of such methods, S GD 2 uses a constrained graph layout [START_REF] Bostock | D 3 data-driven documents[END_REF], [START_REF] Dwyer | Scalable, versatile and simple constrained graph layout[END_REF] approach to model the stress optimization as a set of constraints between every pair of nodes that are relaxed individually [START_REF] Jakobsen | Advanced character physics[END_REF]. Every pair is moved in direction of the gradient of the stress between its nodes. More precisely, two nodes v i and v j are moved in opposite direction based on the divergence between the euclidean distance ||X i -X j || and the ideal distance δ i j , following the direction between their centers. The movement can be negative to move the nodes closer.

The algorithm optimizes the distances between all pairs of nodes for a given number of iterations, using an annealing step size η to reduce the movements amplitude and converge toward a solution as the optimization progresses. Stress optimization is meant to fit a distance distribution in a low dimensional space to that of a higher dimensional one (i.e., δ ). However, with our stress model of the OR task, modifications in the low dimensional space (i.e., node movements) can affect the high dimensional space. More precisely, the distribution of ideal distances depends on the overlaps in the layout (see Equation 2). By moving the nodes during an iteration, some overlaps will be removed but some new ones can be created. Thus, it becomes necessary to re-evaluate the ideal distances such that the algorithm will always optimize the node movements to fit a distribution of distances that corresponds to the current layout with its overlaps.

Optimal Scaling

We define upscaling the layout as multiplying all its node coordinates by a fixed factor. This comes down to uniformly expand (or compress) the drawing without changing the relative distances between the nodes. For any Overlap Removal (OR) algorithm, the initial layout upscaling is a major concern. OR algorithms are required when the information encoded within the nodes must remain visible. When the graph representations are rendered in a viewbox of fixed resolution, upscaling the layout results in reduction of the node sizes on screen, which should therefore be minimized. Yet, it is not always possible to remove all the overlaps in a layout without upscaling, for example when the sum of the node areas is higher than its bounding box. Moreover, this lower bound may not be satisfactory either, especially if it requires severe distortion of the initial layout.

The upscaling of the initial layout should then (i) remain limited such that the node sizes do not get too small; and (ii) should be sufficient such that there is enough space to draw an overlap-free layout that preserves the initial layout structures. In most algorithms in the literature, the initial layout upscaling is a side-effect induced by the node movements, and is an evaluation criterion to compare with other algorithms.

In FORBID, finding the optimal scaling ratio is part of the algorithm. It is not optimized alongside the node movements with S GD 2 since it must be set to compute the ideal distances necessary to the node movements optimization. It is found by binary search between 1 (i.e., the scale of the initial layout) and an upper bound s max . To ensure that FORBID converges toward an overlap-free layout, s max is set to the scaling ratio of the Scaling [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF] algorithm which guarantees that there is no overlap anymore (if there is no perfect overlap). The search is ended when the difference between two consecutive scale factors is lower than a precision threshold s p . The depth of the binary search is s ≤ log s max -1 s p .

FORBID Algorithm and FORBID' Variant

As described in Figure 2, the first step in FORBID is to define a scaling ratio using the binary search (see Section 3.1.3). The binary search builds what we call passes in the algorithm. In every pass, FORBID tries to remove all overlaps at the current scale by moving the nodes with the stress optimization algorithm (see Section 3.1.2) for a fixed number of iterations. We also introduced a minimum movement condition that works as an early stopping for a pass if the node movements are not significant anymore (e.g., less than 10 -7 ). If there remain overlaps after a pass P, the next pass P + 1 will be given a higher upscaling ratio (i.e., more space is needed to produce an overlap-free layout). On the other hand, there are two possibilities if there is no overlap after moving the nodes. If the difference between the scaling ratio of the previous pass P -1 and that of the current pass P is higher than a threshold s p (for scale precision), we consider that the search is not refined enough and we start a new pass P + 1 with a smaller scaling ratio (i.e., we could find a more compact overlap-free layout). However, if the difference of scaling ratio is lower than s p , we stop the optimization and return the overlap-free layout.

To summarize, the binary search looks for the optimal scaling ratio that enables the stress optimization algorithm to remove overlaps without too much node movements. This enable to limit both the upscaling effect and the distortion of the initial layout.

The number of passes is given by the depth of the binary search s ≤ log s max -1 s p , the detection of overlaps with scan-line [START_REF] Dwyer | Fast node overlap removal[END_REF] is in O(N log(N)) and S GD 2 stress optimization algorithm is in O(N 2 ) such that FORBID complexity is O(s N 2 ).

FORBID and FORBID' variants. There remain one design choice to make in order to have an exhaustive description of FORBID. In fact, since every pass P takes a layout X as input and produces a new layout X P , there are two choices to start the next step P + 1. The first possibility is to start P + 1 from the output layout of P (i.e., X P ), as shown in Figure 4a. This means that the algorithm will be allowed to move the nodes further and further as P increases. We expect that allowing more movement in this way will enable the model to converge faster, at the cost of a larger deformation of the initial layout. On the other hand, the second possibility is to start P + 1 from the (scaled) initial layout X 0 (see Figure 4b). This will induce less deformation of the initial layout, but will most likely slow the convergence down.

The first variant (starting P + 1 from X P ) is called FORBID while the second (starting P + 1 from X 0 ) is referred to as FORBID'. The difference between both is highlighted by the red arrows in their respective illustration in Figure 4.

SORDID

This section presents SORDID (for Shape-aware Overlap Removal by Stochastic Gradient Descent), the shape-aware adaptation of FORBID. While FORBID optimizes one distance for every pair of nodes, SORDID decomposes every node's polygon into triangles, and optimizes the distances between the triangles of every pair of nodes. As far as we know, SORDID is the first method to handle OR with nodes of various shapes by decomposing them, as opposed to most methods from the literature that handle arbitrary node shapes by considering their minimum bounding circle or rectangle.

Where FORBID complexity is O(s N 2 ), SORDID one is higher due to the decomposition of the nodes into smaller elements, leading to a significant increase in the number of distances to optimize. The decomposition being bounded by the number of vertices of the polygons, the worst case complexity of SORDID is O(s N 2 t) where t is the maximum number of vertices of the polygons in a layout.

Node Shape Representation

SORDID handles various shapes by decomposing them into triangles with a Constrained Delaunay Triangulation [START_REF] Chew | Constrained delaunay triangulations[END_REF]. It means that in reality, any shape that is not a polygon must be approximated with a polygon. Another limitation that we didn't overcome is the handling of hollow shapes, such as donuts. Instead, SORDID triangulates polygons using their outer border only.

In the next sections, we consider that a node can either be considered by its actual shape, or by the set of triangles that compose its shape. In addition, the minimum bounding circle of every node's shape is computed and will be used later.

Overlap Detection Between Polygonal Nodes

The test for overlap between two nodes v i and v j follows a hierarchical process. We first verify if the minimum bounding circles of their shape are overlapping. If not, then the two nodes cannot overlap. But if the bounding circles do overlap, it does not mean that the node shapes overlap either. In this case, SORDID will go a step deeper in the node representations by checking if the minimum bounding circle of any triangle composing v i does overlap with that of any triangle composing v j . If not, then there is no overlap between v i and v j . But for each overlapping bounding circle between pairs of triangles composing v i and v j , SORDID finally checks whether the triangles actually overlap.

SORDID also leverages scan-line [START_REF] Dwyer | Fast node overlap removal[END_REF] (see Section 2) accelerated detection of overlaps using the stored leftmost and rightmost points of every node to detect skippable tests.

Ideal Distance and Movements

In SORDID, the ideal distances are also conditioned by the node overlaps. For a pair of nodes p i j = (v i , v j ) / ∈ O (i.e., that does not overlap), the ideal distance is set to the distance between the node centers in the initial layout, as described in Equation 2. In this case, only one movement will be computed between the two node centers to optimize that distance.

δ i j = ||X 0 i -X 0 j ||, ∀(v i , v j ) / ∈ O (4)
On the other hand, when p i j ∈ O, there are as many ideal distances as there are pairs of triangles between the triangulated representation of the two nodes. For every pair of triangle, if they do not overlap, then the ideal distance is the euclidean distance between the center of their minimum bounding circles. If they do overlap, the ideal distance is the sum of their minimum bounding circle radiuses.

∆ i j,kl =    ||c(T k ) -c(T l )||, if (T k , T l ) / ∈ Ω i j r(T k ) + r(T l ), if (T k , T l ) ∈ Ω i j , ∀(v i , v j ) ∈ O, ∀(T k , T l ) ∈ DT i × DT j (5)
Fig. 5: SORDID ideal distance for an overlapping pair of nodes, as defined in Equation 5. This figure only illustrates the distance between the overlapping triangles, but the distance between all the pairs of triangles composing v i and v j are computed.

where the set of triangles composing a node v i is defined as DT i (standing for Delaunay Triangulation) and (T k , T l ) ∈ DT i × DT j are the pairs of triangles between the triangulation of v i and v j . The ideal distance for one pair of triangles (T k , T l ) composing v i and v j is defined by ∆ i j,kl . The set of overlapping pairs of triangles in DT i × DT j is represented by Ω i j . Finally, c(T ) and r(T ) give the center and radius of the minimum bounding circle of a triangle T . An illustration of an ideal distance between two overlapping triangles composing polygonal nodes is presented in Figure 5.

It is important to note that when a movement is computed between two triangles, its direction follows the vector between their minimum bounding circle centers, and the whole nodes (i.e., all the triangles composing the two nodes) are moved. In practice, it means that there are much more distances to optimize in SORDID than in FORBID, and we expect it to be slower. Nevertheless, this fine-grained definition of ideal distances enables tight adjustments (and even imbrications) of polygonal nodes.

The weight factor also adapts FORBID's definition (see Equation 3) using the triangles from Delaunay Triangulation of the node shapes:

W i j = ||X 0 i -X 0 j || α , ∀(v i , v j ) / ∈ O (6)
ω i j,kl =    (||c(T k ) -c(T l )||) α , if (T k , T l ) / ∈ Ω i j (r(T k ) + r(T l )) α * K , if (T k , T l ) ∈ Ω i j , ∀(v i , v j ) ∈ O, ∀(T k , T l ) ∈ DT i × DT j (7)
where α ∈ R is a factor related to the ideal distance between the nodes, and K ∈ R is a weight to configure the importance given to overlapping pairs of nodes/triangles. Finally, the stress optimized by SORDID, considering the triangulation of polygonal nodes, is expressed as:

σ (X) = ∑ (v i ,v j ) / ∈O W i j (||X i -X j || -δ i j ) 2 + ∑ (v i ,v j )∈O ∑ (T k ,T l )∈DT i ×DT j ω i j,kl (||c(T k ) -c(T l )|| -∆ i j,kl ) 2 (8
) where δ i j and W i j are defined in Equation 4and Equation 6.

To sum up most of the framework design, we remind that Figure 4 presents the arrangement of its building blocks. In addition, two behaviors were omitted from the framework description. The first is to conduct a pass of stress optimization without changing the scale factor of the initial layout, if the area of the initial layout's bounding box is higher than the sum of the node areas. Doing so prevents the algorithm from going through a complete optimization when the task can be solved in the initial layout's scale. The second omitted behavior is responsible for guaranteeing that FORBID generates an overlap-free layout. Hence, during the whole optimization, we recall a best version of the layout we found to return it in the end, should the last pass in the algorithm not be an overlap-free layout. If no overlap-free layout is ever found, the algorithm returns the initial layout upscaled by the scaling ratio that guarantees that there is no overlap anymore (see Section 3.1.3).

EVALUATION

This section presents the results of FORBID and SORDID evaluation as well as their comparison with state-of-the-art Overlap Removal (OR) algorithms. The section is split in two evaluations: (i) on rectangular nodes, and (ii) on polygonal nodes. Our algorithms are compared with the state-of-the-art baseline algorithms (see Section 4.1.1) on a selection of metrics described in Section 4.1.3.

Some results presented in this section differ from those in the printed original study [START_REF] Giovannangeli | FORBID: Fast Overlap Removal By stochastic gradIent Descent for Graph Drawing[END_REF] as there was an error on the el rsdd metric reports. This error was made to the disadvantage of FORBID and FORBID' and has been corrected in the latest online version.

Evaluation protocol

This section presents the design choices made to evaluate FORBID and SORDID. We follow the protocol defined by Chen et al. [START_REF] Chen | Node overlap removal algorithms: A comparative study[END_REF], [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF] for reproducibility purposes. That includes quality metrics, datasets and baseline algorithms to compare with.

Baseline Algorithms

Chen et al. [START_REF] Chen | Node overlap removal algorithms: A comparative study[END_REF], [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF] presented a complete survey comparing many Overlap Removal (OR) algorithms from the literature. Following their results, the baseline algorithms we selected are PFS' [START_REF] Hayashi | A layout adjustment problem for disjoint rectangles preserving orthogonal order[END_REF], PRISM [START_REF] Gansner | Efficient, proximity-preserving node overlap removal[END_REF], and Diamond [START_REF] Meulemans | Efficient optimal overlap removal: Algorithms and experiments[END_REF], each of them being state-of-the-art in its approach to the OR task. They are respectively based on scan-line, stress optimization and constraint relaxation. In addition, since FORBID belongs to the stress optimization approach, we also included GTree [START_REF] Nachmanson | Node overlap removal by growing a tree[END_REF] as it is supposed to be an improvement of PRISM and it will enable more comparison within the family. Please refer to Section 2 for a more detailed description of these algorithms.

Datasets

Following Chen et al. [START_REF] Chen | Node overlap removal algorithms: A comparative study[END_REF], [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF] evaluation protocol, we use the Generated and Graphviz datasets available online 1 .

Generated is a set of 840 synthetic graphs specifically created for the benchmark of Chen et al. [START_REF] Chen | Node overlap removal algorithms: A comparative study[END_REF], [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF]. It is made of 120 graphs of size 10, 20, 50, 100, 200, 500, 1000, laid out with the FM 3 algorithm [START_REF] Hachul | Drawing large graphs with a potential-fieldbased multilevel algorithm[END_REF].

Graphviz is a set of 14 real-world graphs from the Graphviz suite [START_REF] Gansner | An open graph visualization system and its applications to software engineering[END_REF]. They have between 36 and 1463 nodes and are laid out with SFDP algorithm [START_REF] Hu | Efficient, high-quality force-directed graph drawing[END_REF].

These two datasets are made of nodes with a rectangular shape. Since SORDID works on polygonal nodes, we created modified versions of the two datasets to evaluate it on additional shapes. More precisely, we preserve the node positions (i.e., their center), and their rectangle's dimension in the original datasets is used as basis for the polygons. The polygons will be defined in the next, and Figure 6 presents an example for each of them. Assuming that a node was defined with a center (x, y) and a rectangular shape (w, h), all the following shapes are built to have the maximal size that fit in a circle of center (x, y) with a radius r = max(w, h)/2.

Star. A star has a random number of arms between 3 and 6. The arm lengths is based on the original rectangular node and is defined as max(w, h)/2. The hollow parts of a star is max(w, h)/6 away from its center.

Diamond. A diamond is defined as the maximum regular diamond that fits in the original rectangle of the node.

Spade. A spade is made by connecting two discretized "ears" (i.e., circular arcs) with three points: one for the top and two defining the "tail" of the shape.

These transformations are applied for all nodes in all graphs of both Graphviz and Generated datasets. We did not consider polygon rotations in this evaluation. Information on the initial layout of every dataset are reported in Table 1.

Metrics

With Post-process Overlap Removal (OR) algorithms, we assume that the provided initial layouts were computed to optimize some criteria, producing a meaningful representation for the end-user. Hence, a good OR algorithm should be able to remove all the overlaps in the initial layout while also preserving its aspect.

As the OR algorithms that will be compared remove all overlaps in the layouts, the evaluation of their results is based on their preservation of the initial layout. Since initial layouts can be deteriorated in different ways, we leverage five quality metrics from Chen et al. [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF] survey to capture various kinds of deterioration. Other metrics can measure the compliance with C comp. and C lay. criteria (e.g., [START_REF] Gray | A Scalable Method for Readable Tree Layouts[END_REF], [START_REF] Li | Dual Space Coupling Model Guided Overlap-Free Scatterplot[END_REF]). We chose to use the metrics defined by Chen et al. [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF] to leverage their results and extend the study. All these metrics are oriented lower is better.

Nodes orthogonal order. oo nni counts the number of times the orthogonal order of the nodes has been violated.

oo nni = ∑ (v i ,v j )∈V 2 ,i̸ = j 1(x 0 i > x 0 j ∧ x ′ i < x ′ j ), +1(y 0 i > y 0 j ∧ y ′ i < y ′ j ) N(N -1) (9)
where

X 0 i = (x 0 i , y 0 i ) (resp. X ′ i = (x ′ i , y ′ i ))
are the 2D coordinates of v i in the initial layout X 0 (resp. overlap-free layout X ′ ). The metric is normalized to enable the comparison of layouts with different number of nodes.

Convex hull area. sp ch a is the ratio of the overlap-free layout's convex hull's area over that of the initial layout, the optimal value being 1. This metric comes down to evaluate the expansion of the layout and thus captures its upscaling. It is the main metric to evaluate the criterion C comp. .

sp ch a = A(ConvexHull(X ′ )) A(ConvexHull(X 0 )) (10)
where ConvexHull computes the smallest convex region containing all the nodes of a layout. ConvexHull is computed taking into consideration the node shapes and sizes, and not only their center. Aspect ratio. gs bb iar measures the deviation of the overlapfree layout's aspect ratio compared to that of the initial layout.

gs bb iar = max W ′ * H 0 H ′ * W 0 , H ′ * W 0 W ′ * H 0 ( 11
)
where W 0 and H 0 (resp. W ′ and H ′ ) are the initial layout X 0 (resp. overlap-free layout X ′ ) rectangular bounding box width and height. Node movements. nm dm imse measures the average deformation of the initial layout by quantifying node movements from their position in the initial layout to their position in the overlapfree layout. Since the layout upscaling is already captured by another metric (i.e., Convex Hull Area), Node movements is made unsensitive to the scale and range of the layouts. Doing so enables this metric to capture the raw deformation of the initial layout and is especially useful to evaluate the criterion C lay. .

nm dm imse = 1 N ∑ v i ∈V ||X ′ i -shift(scale(X 0 i ))|| 2 (12)
where shi f t and scale functions project the positions of the initial layout in the value domain of the overlap-free layout. These transformations are linear based on the layout bounding box sizes. Edge length preservation. el rsdd captures the uniformity of distance preservation. As opposed to Node Movements that penalizes any relative node movement, Edge Length Preserv. measures the average deviation of distances alongside the edges of the Delaunay Triangulation of the initial layout. The intuition is that if some quantity of movement is required to solve the task, all the nodes should move a little (as opposed to a few nodes moving a lot). Formally, the metric is defined as:

ρ uv = ||X ′ u -X ′ v || ||X 0 u -X 0 v || , ∀(u, v) ∈ E DT , ρ = 1 |E DT | ∑ (u,v)∈E DT ρ uv , el rsdd = 1 |E DT | ∑ (u,v)∈E DT (ρ uv -ρ) 2 ρ ( 13
)
where E DT is the set of edges of the Delaunay Triangulation of the initial layout X 0 , and ρ uv represents (u, v) edge length's deviation ratio in the overlap-free layout. Fig. 8: SORDID, FORBID and some selected state-of-the-art OR algorithms performance according to the aesthetic metrics described in Section 4.1.3 on the Graphviz dataset. All plots have a log scale on the Y-axis. All metrics are oriented lower is better. The complete description of these representations is given in Section 4.1.4. Trends are close to that on the Generated dataset (see Figure 7).

Statistical Validation and Results Presentation

Statistical validation. In the following, we will compare the performance of various algorithms on relatively large sets of data.

To improve the faithfulness of the evaluation, we support the performance analysis with statistical tests following the protocol of Purchase [START_REF] Purchase | Experimental human-computer interaction: a practical guide with visual examples[END_REF]. For every metric, an ANOVA test is first conducted to assert whether the differences between the algorithms is due to chance or not. To do so, we use the repeated measures nonparametric test of Friedman [START_REF] Friedman | The use of ranks to avoid the assumption of normality implicit in the analysis of variance[END_REF] with a confidence threshold α = 0.05. If this test passes, post-hoc pairwise comparisons are tested with Conover [START_REF] Conover | Practical nonparametric statistics[END_REF] at confidence α = 0.05. Results report. The metric score distribution of the algorithms are reported in box-plots (e.g., Figure 7a). All them have Y-axis log scales. Below each plot is represented a matrix of pairwise significance. If the Friedman test didn't pass (e.g., Figure 8e) the matrix is faded as pairwise comparisons should not be interpreted. Otherwise, black circles in the matrix encode pairwise significance between the corresponding line/column algorithms, while red circles encode the non-significance. Since all the metrics can be read as lower is better, an algorithm is better than another if its distribution (i.e., box) is more dense on a smaller value domain, and if the difference between them is statistically significant.

Evaluation on Rectangular Nodes

This section focuses on the evaluation and comparison of FORBID, SORDID, their variant and state-of-the-art algorithms on rectangular nodes. Figure 7 reports the performance of these algorithms on the Generated dataset, while Figure 8 reports them on the Graphviz dataset. Please refer to Section 4.1.4 for more information on the results presentation.

Performance on Generated

Figure 7a shows that all the algorithms succeed in minimizing Nodes Ortogh. Order according to the order of magnitude of their performance (overall < 10 -1 ). By design, PFS' has a score of 0 on that metric since it cannot violate the nodes orthogonal order. FORBID' and SORDID' have similar performance to PRISM and are a slightly better than GTree. The difference is not significant between neither FORBID and SORDID, nor FORBID' and SORDID'. Finally, Diamond performance is significantly worse than other algorithms on that metric as it consistently deteriorates it more than them.

On Aspect Ratio (see Figure 7b), we can see that our four methods are significantly better than all the others. We assume this score is related to the explicit handling of the upscaling factor in our algorithms. Indeed, the initial layout positions are uniformly upscaled alongside the X and Y dimensions to create more empty spaces. This uniform upscaling does not deteriorate the layout bounding box's aspect ratio. Only the node movements that come afterward can modify that ratio, and we can see that the deviation remains minimal.

Figure 7c presents Convex Hull Area performance, a measurement of the overlap-free layout's compactness. The distributions show that our methods have better results than state-of-the-art algorithms overall. As expected (see Section 3.1.4), the FORBID' and SORDID' variants of the algorithm produce less compact layouts than their standard counterparts, although the difference between FORBID and SORDID is not significant.

Node Movements is the main metric to measure the initial layout preservation (i.e., C lay. criterion), for which Figure 7d presents all algorithm results on the Generated dataset. We can see that our algorithms have significantly less node movements than other state-of-the-art-methods. The difference is not significant between FORBID (resp. FORBID') and SORDID (resp. SORDID'). We can also note that the FORBID' and SORDID' variants have consistently less node movements than their standard counterparts. This confirms the assumption (see Section 3.1.4) that starting every new pass from the initial layout, rather than from the output of the previous pass, leads the model towards an overlap-free layout with less relative movements.

The last metric to compare the selected algorithms on, Edge Length Preserv., measures how uniform the deformation of the closest nodes in the initial layout is. The performance on that metric are reported in Figure 7e. We can see that PFS' is the best on that metric, followed by PRISM and GTREE, then SORDID' and FORBID'. SORDID and FORBID have slightly worse results, and Diamond have the worst among the selected algorithms. Again, the prime variants have better metric values than the standard ones. This result could be expected as they produce less node relative movements, but it also means that the produced movements were more uniformly distributed across the nodes.

Performance on Graphviz

Overall, the results on the Graphviz dataset (see Figure 8), corroborate those observed on the Generated. There are less significant pairwise differences on Graphviz than Generated, mainly because of Graphviz's size of 14 graphs. With such a small volume of data, statistical tests cannot validate the significance of pairwise differences if the results are not strongly correlated. On Nodes Ortogh. Order, PFS' is still the best while FORBID' and SORDID' compete with GTree and PRISM. On the other hand, FORBID, SORDID are worse, and Diamond is the worst on that metric. Aspect Ratio is still highly in favor of FORBID, SORDID and their variants. On Convex Hull Area and Node Movements, we can also observe that our algorithms are overall better than state-of-the-art methods (except for PRISM that overperforms on Convex Hull Area) with SORDID suffering from one problematic case on both metrics (see the outlier in Figure 8c and8d). Finally, the ANOVA test did not pass on the Edge Length Preserv. metric. It means that, according to the statistical test, the variation of performance according to the algorithms used for each graph could be due to chance. Pairwise comparison should not be interpreted in this case. Eventually, the trends between the boxes are close to those observed on the Generated dataset.

Synthesis on Rectangular Nodes

In this section, we have seen that FORBID and FORBID' competed well with state-of-the-art algorithms. On some metrics, they even significantly outperform them (e.g., Aspect Ratio, Node Movements and Convex Hull Area to a lesser extent).

As expected, we observed that the prime variant of FORBID and SORDID consistently led to overlap-free layouts that better preserve the initial layout (i.e., optimizing C lay. ), at the cost of some upscaling. On the other hand, the standard variant tends to produce compact layouts optimizing C comp. . SORDID being a generalization of FORBID, we assumed that the difference between them was not significant on rectangular nodes as this shape is strictly equivalent to its rectangular bounding box. The evaluation demonstrates that it is indeed the case as the difference between them is never significant, except between SORDID' and FORBID' on Convex Hull Area with Generated.

Evaluation on Polygonal Nodes

This section presents the results of SORDID, SORDID', FORBID, FORBID' and PFS' on the Generated dataset with polygonal node representations as described in Section 4.1.2. We only compare the Overlap Removal (OR) algorithms proposed in this article with PFS' as it is the best performing state-of-the-art algorithm according to the evaluation on rectangular nodes (see Section 4.2). In addition, we only compare the algorithms on the Generated dataset as it is the largest considered in this evaluation, and thus the one on which results are the most significant. The Graphviz dataset will be later used for visual evaluation (see Section 5.2). To handle polygonal nodes with standard OR algorithms such as FORBID and PFS', the common way is to provide them a bounding box of the node shapes (here, the rectangular bounding box). One can note that the rectangular bounding boxes of the Diamond shapes are equal to to the rectangular nodes that were evaluated in the previous Section 4.2. Hence, the metric scores of FORBID, FORBID' and PFS' on the Diamond shape are the same as in the evaluation on Rectangular nodes (up to some randomness in the optimization's initialization).

As the trends between the methods' performance are similar across various shapes on some metrics, the results are discussed by metric (rather than by dataset of shape) in the following. The main assumption we can make in this evaluation is that a method that handles polygonal nodes directly (i.e., SORDID), should lead to more compact overlap-free layouts. Indeed, as opposed to a bounding box approach, the fine-grained awareness that the algorithm has of the node shape representations should enable it to make more use of the empty spaces in the layout. In general, we expect a shape-aware algorithm to provide better results on polygonal nodes than standard algorithms that must approximate the node shapes. The results of these evaluations are presented in Figures 9, 10 and 11 for the Spade, Diamond, and Star shapes respectively.

On the Nodes Ortogh. Order metric, the methods performance is the same across the three shapes. PFS' has never produced any inversion of the nodes orthogonal order, as its design does not allow it. We can observe that SORDID and SORDID' are slightly better than their FORBID and FORBID' counterparts on this metric. We think this result is due to the shape-aware approach's capability to have finer adjustments between the nodes to relax the overlap constraints. These fine adjustments can lead to significant benefits, especially in denser regions of the layouts, where an approach on bounding boxes would have no other choice but to move some nodes out of the dense region to be able to relax the overlap constraints, which is more prone to inversions in the nodes orthogonal order.

FORBID and SORDID are still significantly better than PFS' on Aspect Ratio, as shown in Figure 9b, 10b and 11b. The difference is significant between SORDID and FORBID (and their prime counterparts), meaning that the shape-aware approach leads to better preservation of the initial layout's aspect ratio. Since the aspect ratio can only be deteriorated by node movements in our methods, this result was expected in view of our assumption that a shape-aware algorithm should be able to use more empty spaces to resolve overlaps, making the task easier to solve with less movement.

Convex Hull Area is the main metric to evaluate how compact the overlap-free layout produced by an algorithm is, and we expect SORDID shape-aware approach to achieve better results. As presented in Figure 9c, 10c and 11c, it is the case with the three shapes, but in different proportions. SORDID and SORDID' provide the most benefits compared to FORBID and PFS' (i.e., bounding box approaches) on the Diamond shape. We argue that this is because this shape is the most prone to fine adjustments and imbrications, especially compared to the Spade shape. On Stars, it is noteworthy that the difference between SORDID and SORDID' is not significant. We could expect better results for SORDID and SORDID' on the Star shape as we can easily imagine stars to be imbricated alongside their arms. However, this is rarely possible in practice as the star arms orientation is fixed and they cannot be rotated. With our shapes generation, having neighboring stars with arms sharing the same orientation on a common side is very rare, especially since the arm orientation of a star depends on its number of arms (which is random). Figure 9d, 10d and 11d present the algorithm results on the Node Movements metric. As we can see, SORDID and SORDID' are consistently better on that metric. Although we assume that a shape-aware approach should be able to remove overlaps using less node movements by using more available empty spaces than an approach with bounding boxes, it was not evident that this behavior could be observed on this metric. Indeed, since Node Movements measurement ignores the overlap-free layout's upscaling, it can favor a method that uniformly upscales the initial layout and does not move any node, compared to another method that moves some nodes to limit the upscaling.

Finally, the results on Edge Length Preserv. are presented in Figure 9e, 10e and 11e. On Spade and Star shapes, PFS' is better than both SORDID and FORBID, while SORDID is better on the Diamond shape. Overall, the shape-aware approach of SORDID always shows better results than FORBID. As a reminder, this metric captures the uniformity of short distances degradation. Hence, we can conclude that the fine adjustments that SORDID makes are significantly beneficial to the layouts it produce.

Overall, we observed that the shape-aware approach of SOR-DID consistently led to better results than the adaptation of standard algorithms that uses the bounding box of the node shapes. We also found evidence supporting the assumption that a shape-aware approach would lead to more compact overlap-free layout by achieving more fine-grained adjustments between the node shapes. The evaluation demonstrates the good capacity of this approach to minimize the node movements and upscaling necessary to remove all overlaps.

Execution Times

This section discusses the execution times of FORBID, SORDID and the state-of-the-art Overlap Removal (OR) algorithms of the evaluation. Diamond algorithm's execution times are not reported as they were dramatically higher than other methods (as presented in Chen et al. [START_REF] Chen | Node overlap removal algorithms: A comparative study[END_REF], [START_REF] Chen | Node Overlap Removal Algorithms: an Extended Comparative Study[END_REF]). All the algorithm execution times were measured on the same i9-12900KF CPU. It is important to note that the decomposition of the node shapes with the Delaunay Triangulation, and the computation of the pairwise ideal distances that come with it, are parallelized in SORDID to alleviate the additional cost induced by the decomposition. This parallel execution makes it about twice as fast, and makes its execution time acceptable despite the additional cost of the node shape decompositions, and considering the increases in quality observed in Section 4.3. In both FORBID and SORDID, we also tried to parallelize the stochastic optimization of pairwise node movements, but found that it led to results of lower quality. We think that processing the node movements sequentially improves the optimization as any node coordinate update takes into consideration the movements that were already applied to the node during the iteration.

We only report the results on Graphviz with Rectangular nodes, since they were consistently similar with other shapes and on Generated. Reporting on Graphviz enables comparison of the algorithms' execution times in regard of the input graph properties. Thus, we identify three groups of difficulty, as presented in Figure 12.

On easy graphs, FORBID, FORBID' and PFS' are instantaneous (i.e., less than 5ms). SORDID and SORDID' are instantaneous as well on most cases, but take more time on b143 (14ms and 51ms respectively). On the other hand, GTree and PRISM are consistently slower on these graphs. Even though these examples are easy (i.e., the number of nodes and overlaps is small), we can already observe some difference between the algorithms.

On medium graphs, FORBID, FORBID' are among the fastest, followed by SORDID GTree and SORDID', while PRISM is the slowest by a significant margin.

FORBID and SORDID are overall the fastest on hard graphs, SORDID results being surprising as its complexity is higher than that of FORBID, but its execution time is lower. This improvement is mostly due to some difference in their optimization. SORDID', FORBID' and GTree are overall slower and have relatively close execution times. Finally, PRISM is still slower than the others.

On medium and hard graphs, PFS' is still almost instantaneous; making it the fastest of the considered algorithms in this evaluation. It is also interesting to note that the graph on which the algorithms were the slowest is not the one that has the most overlaps, as b100 has only half the number of overlaps of root or badvoro. All these methods are more sensitive to increases in the number of nodes than in overlaps, as expected in view of their complexities (i.e., quadratic on the number of nodes).

Overall, we can conclude that FORBID scales well according to the task complexity. As expected, FORBID' is slower than FORBID, mostly because of its constraint to start each stress optimization from the upscaled initial layout. We also observe that SORDID and SORDID' shape-aware approaches tend to be slower, though SORDID can be faster thanks to its different model of ideal distances. Since SORDID' has the constraint of starting each optimization from the scaled initial layout of a prime variant, and the necessity to optimize more distances with the decomposition of the node shapes into triangles, it is not surprising to see that it is slower than the other variants.

DISCUSSION

This section discusses some behaviors of FORBID and SORDID observed during the evaluation, and some of their limitations. It also discusses their convergence and some visual examples.

Convergence Analysis

The convergence plots of FORBID, SORDID and their prime variant are presented in Figure 13. Each plot reports the evolution of the stress, number of overlaps and upscaling against the number of iterations in the stress optimization algorithm. Vertical dashed lines represent beginning of new passes (see Section 3.1.4).

In all these plots, we can see that the stress curves follow that of the number of overlaps. This confirms that optimizing stress to remove overlaps is efficient. The difference with prime variants is also well represented. In FORBID and SORDID, most overlaps are removed in the first few passes and the last ones are dedicated to the search for the optimal upscaling ratio while preserving the overlapfree layout. On the other hand, FORBID' and SORDID' have to restart their optimization from the scaled initial layouts every time a new pass begins, the problem being made easier or harder with a different upscaling ratio. In the end, we can also observe that the prime variants need more iterations to converge toward an overlap-free layout that satisfies the search for a compromise between C lay. and C comp. . This explains why prime variants are consistently slower.

Comparing SORDID and FORBID, we can see that the stress, number of overlaps and upscaling follow the same trend on the mode graph. On the other hand, the results are different on badvoro, which is a more complicated sample. These differences mostly come from the two approaches difference when it comes to overlap identification. For instance, we can see on badvoro that both SORDID and SORDID' began the first pass with a scaling ratio of 1. It means that according to their more fine-grained definition of the node shape representations, there was enough empty space in the initial layout to try to solve the Overlap Removal task with movements only. On the other hand, the bounding box approach of FORBID and FORBID' did not identify that. In the end, SORDID requires slightly more iterations to converge than FORBID.

It is also interesting to observe that despite having a large definition of the upper bound s max for the binary search for the optimal scaling ratio, the algorithms are able to find a solution at a lower scale. This upper bound is set to guarantee that the algorithms converge toward an overlap-free layout, but is most of the time unnecessarily high. Other upper bounds or optimization strategies could be used to find the optimal scale, but are not investigated in this article and are left for future works.

Visual Evaluation

This section discusses some visual examples of the overlap-free layouts produced by most of the algorithms selected for the evaluation. Visual examples of Graphviz graphs with rectangular nodes are presented in Figure 14.

On very small graphs such as unix, no significant difference can be observed between the algorithms. On b124, all the algorithms also have similar results, with the exception of SORDID and SORDID'. Indeed, we can see in their layouts that the "wide and flat" node was pushed far from its initial position. This behavior is probably induced by the design of ideal distances in SORDID which leads to high repulsive forces in this case. Indeed, the wide flat node is most likely decomposed into two triangles which boundig circle radiuses are relatively high. Hence, the movements involving that node have high amplitudes, and their result are clearly visible on b124. Such an example shows that there is a limit to which SORDID can preserve the initial layout when the node shapes have a high aspect ratio. SORDID and SORDID' drawings of b124 look similar in regard to that wide flat node because the amplitude of that node's movements are so high that it is moved to its final position in very few iterations. Hence, even though SORDID' begins every new pass from the initial layout node coordinates, its first few iterations consistently move the node to this location. Then, it does not find a way to put it back closer to its initial position because of the high amplitudes of the movements it involves.

On mode, FORBID, SORDID and PRISM damaged the initial layout to produce more compact embeddings. The other algorithms preserved the initial layout structure. PFS' and GTree layouts are made of some orthogonally unpleasing parts as opposed to FORBID' and SORDID' layouts that very well preserved the initial layout structure. The same behavior can be observed on xx, where FORBID, SORDID and PRISM produced compact layouts, and GTree created some unnecessarily long edges. Finally, on badvoro, we can clearly see the downside of producing very compact layouts. PRISM overlap-free layout is so compact that it becomes impossible to recognize the initial layout structures and visualize the edges. GTree overlap-free layout has also severely deteriorated the initial layout. The remaining algorithms produced satisfactory results where the initial layout structures are preserved, while maintaining some compactness.

In addition to graph visualization with nodes having a rectangular shape, Figure 15 presents some layouts of SORDID' with Diamond, Spade and Mixed node shapes. In Mixed shape visualizations, the shapes used are those presented in Figure 6 and two others: Heart and Clover. These new shapes are built in the same way as Spade, by connecting some points with discretized circular arcs. These representations demonstrate the great capacity of the shape-aware approach to leverage empty spaces that would not be used by bounding-box approaches. We can even observe the imbrications of nodes representations, especially on b124.

Limitations

Throughout the evaluation, we measured how the algorithms presented in this article performed. However, some of their behaviors could not be captured and are discussed in this section.

The first limitation concerns FORBID and SORDID algorithms. In these variants, the algorithm begins every stress optimization from the output of the previous pass. It means that the ideal distances of a pass P are based on the node positions at the end of the pass P -1. This design allows the algorithm to move the nodes more, and helps it to converge faster. On the other hand, it means that the longer the algorithm takes to converge, the more it will forget about the initial layout. At some point, the structures of the initial layout could theoretically be completely lost. In addition, even if a pass P in the stress optimization does not lead to an overlap-free layout, the next pass P + 1 will take the node positions of that pass X P as the reference to compute the ideal distances. This behavior could be prevented to improve the algorithm capability to preserve the initial layout, but this is left for future works.

Another limitation concerning both FORBID and SORDID comes from the stress optimization algorithm used [START_REF] Zheng | Graph drawing by stochastic gradient descent[END_REF]. What makes this algorithm efficient is its principle of applying forces independently between every pair of nodes. However, this principle can create problematic behaviors. We believe that it is the source of the bad placement of the "wide flat" node of SORDID and SORDID' observed on b124 in Figure 14, alongside their model of ideal distances. This behavior is quite common with stress optimization algorithms: an element is pushed far away from its initial position because of a high repulsing force with a neighbor, and it will never come back to its original position because of other nodes' repulsive forces. This pitfall is most likely accentuated by handling pairs of nodes individually. To try another efficient optimization algorithm is left for future works.

The last limitation we discuss concerns the heuristic encoded within FORBID to obtain a compromise between C comp. and C lay. , and that can be expressed as follows. Every pass in the stress optimization algorithm has a budget of node movements: it can move all pairs of nodes n iter times. If all overlaps are not removed after this budget is consumed, we assume that too much movement would be necessary to remove all overlaps and it would not comply with C lay. criterion. Hence, a new pass is started in the algorithm, changing the scale of the input layout. The issue is that this heuristic is very dependant on some hyper-parameters such as the number of iterations n iter, the weight factors of the distances to optimizes (i.e., α and K, see Section 3), and even the upper bound and the optimization strategy to find the optimal scale (here, binary search). That is to say, the optimal compromise between C comp. and C lay. criteria is only possible if the hyper-parameters provided permit them; the algorithm itself hardly provides this guarantee. Nevertheless, the parameters were fixed for all the samples in the evaluations we conducted, and the algorithms demonstrated good capabilities to produce satisfying overlap-free layouts for a large variety of graphs.

CONCLUSION

This paper has presented FORBID, an Overlap Removal (OR) algorithm that leverages upscaling and stress optimization by simulated stochastic gradient descent to minimize deformations of the initial layout. In addition, the article proposed SORDID, an adaptation of FORBID to handle any polygonal node representation. Both are based on the preservation of the scale and the node pairwise distances to produce an overlap-free layout where the the initial graph layout structures are preserved and the surface used limited. The adaptation to polygonal nodes is achieved by decomposing every polygon into triangles and processing nodes as sets of triangles.

They were compared to a selection of state-of-the-art OR algorithms. The evaluation demonstrates that FORBID is among the best techniques to forbid overlaps while preserving the initial layout and limiting the upscaling effect.

Despite their quadratic complexity, FORBID and SORDID compete with the fastests methods of the literature, handling graphs with up to a thousand nodes and/or ten thousands of overlaps in less than 10 seconds. Nevertheless the PFS' algorithm remains the fastest by a significant margin compared to any other technique.

The main lead for future works is to improve the algorithm's complexity to better handle large graphs (e.g., up to tens of thousands of nodes). The first idea to achieve this is to subsample the pairs of nodes that must be processed to remove overlaps. A multi-scale approach could enable to optimize the preservation of the initial layout structures while sampling the distances to preserve (i.e., preserve distances between-clusters and within-cluster; ignore between nodes of different clusters). Finally, with the recent advances in Deep Learning for graph drawing [START_REF] Giovannangeli | Toward Efficient Deep Learning for Graph Drawing (DL4GD)[END_REF], [START_REF] Wang | DeepGD: A Deep Learning Framework for Graph Drawing Using GNN[END_REF], training a Deep Learning model to solve the OR task could be an interesting lead to investigate. By design, these models can scale to large graphs as they are capable of solving the task they have learned in almost constant time.

Another lead for future work is to optimize the optimal scaling ratio alongside the node positions by stochastic gradient descent. In our algorithms, the scaling ratio is set before the optimization of the node movements because we build the ideal distances distribution on the upscaled layout. Yet, it would be interesting to see if we can reach better compromises between compactness and the preservation of the initial layout by optimizing both the node movements and the scaling ratio at the same time.

  (a) Slicing into super-pixels. (b) Alteration to create overlaps. (c) Bounding box approach. (d) Shape-aware approach.

Fig. 1 :

 1 Fig. 1: This figure illustrates our motivation for designing a shape-aware algorithm for Overlap Removal (OR). (a) The famous painting "La Joconde" (1506) by Leonardo da Vinci sliced into non-convex super-pixels using SLIC [1]. (b) Altered version of (a) to create overlaps by doubling the super-pixel size. (c) Result of FORBID' on (b) with a bounding box approach. (d) Result of the shape-aware OR adaptation, i.e., SORDID' on (b).

Fig. 4 :

 4 Fig. 4: Differences between FORBID (a) and FORBID' (b) variants.

Fig. 6 :

 6 Fig. 6: Polygonal shapes considered in the evaluation. Stars can have from 3 to 6 arms.

Fig. 9 :

 9 Fig.9: SORDID, FORBID and some selected state-of-the-art OR algorithms performance according to the aesthetic metrics described in Section 4.1.3 on the Generated dataset with a Spade shape (see Section 4.1.2). All plots have a log scale on the Y-axis. All metrics are oriented lower is better. The complete description of these representations is given in Section 4.1.4.

Fig. 10 :

 10 Fig.10: SORDID, FORBID and some selected state-of-the-art OR algorithms performance according to the aesthetic metrics described in Section 4.1.3 on the Generated dataset with a Diamond shape (see Section 4.1.2). All plots have a log scale on the Y-axis. All metrics are oriented lower is better. The complete description of these representations is given in Section 4.1.4.

Fig. 11 :

 11 Fig.11: SORDID, FORBID and some selected state-of-the-art OR algorithms performance according to the aesthetic metrics described in Section 4.1.3 on the Generated dataset with a Star shape (see Section 4.1.2). All plots have a log scale on the Y-axis. All metrics are oriented lower is better. The complete description of these representations is given in Section 4.1.4.

Fig. 12 :

 12 Fig. 12: Execution time (in milliseconds) of the algorithms on Graphviz with rectangular nodes. Rows are sorted by graph complexity measured in number of nodes, edges and overlaps.

Fig. 13 :

 13 Fig. 13: Convergence plots of SORDID, FORBID and their prime variant on two Graphviz graphs with Diamond shape. They report the evolution of stress, number of overlaps and scaling ratio against the total number of iterations. Vertical dashed lines represent beginning of new passes. Stress and number of overlaps are normalized by their respective maximum value, while upscaling ratio is normalized by its binary search maximum bound (see Section 3.1.3).

Fig. 14 :

 14 Fig. 14: Graph visualization of examples from the Graphviz dataset with rectangular node shapes. The images present the overlap-free layouts of SORDID, FORBID and their prime variant, as well as PFS', GTREE and PRISM. Nodes are colored in transparent red if they overlap each other, and opaque blue otherwise.

Fig. 15 :

 15 Fig. 15: SORDID' overlap-free layout examples from the Graphviz dataset with Diamond, Spade and Mixed shapes. In Mixed shapes visualizations, the shapes used are Heart and Clover in addition to those presented in Figure 6.

TABLE 1 :

 1 Number of graphs, nodes, and overlaps for each dataset in the experiment. For the number of overlaps, the second row of each dataset presents the average ± standard deviation.

			Generated	Graphviz
		# Graphs	840	14
		# Nodes	[10; 1000]	[36; 1463]
		Rectangle	[0; 36537] 3196 ± 8717	[4; 11582] 2119 ± 4080
	# Overlaps	Star Diamond	[0; 30920] 2687 ± 7338 [0; 18350] 1575 ± 4325	[4; 21921] 3746 ± 7106 [0; 8111] 1239 ± 2506
		Spade	[0; 37615] 3277 ± 8935	[5; 25370] 4432 ± 8352

  Fig.7: SORDID, FORBID and some selected state-of-the-art OR algorithms performance according to the aesthetic metrics described in Section 4.1.3 on the Generated dataset. All plots have a log scale on the Y-axis. All metrics are oriented lower is better. The complete description of these representations is given in Section 4.1.4. As expected, our algorithms can produce inversions in the nodes orthogonal order. Nevertheless, they demonstrate great capability on compactness (sp ch a) and distortion minimization (nm dm imse).

								10 2			10 7
		10 1			1.8						10 6
	oo_nni	10 2		gs_bb_iar	1.4 1.6		sp_ch_a	10 1		nm_dm_imse	10 3 10 4 10 5	el_rsdd	10 0
					1.2						10 2 10 1	10 1
	SORDID SORDID' FORBID FORBID' PFS' PRISM GTree Diamond	SO RD ID SO RD ID' FO RB ID FO RB ID' PFS ' PR ISM GT ree Dia mo nd	SORDID SORDID' FORBID FORBID' PFS' PRISM GTree Diamond 1.0	SO RD ID SO RD ID' FO RB ID FO RB ID' PFS ' PR ISM GT ree Dia mo nd	SORDID SORDID' FORBID FORBID' PFS' PRISM GTree Diamond 10 0	SO RD ID SO RD ID' FO RB ID FO RB ID' PFS ' PR ISM GT ree Dia mo nd	SORDID SORDID' FORBID FORBID' PFS' PRISM GTree Diamond 10 0	SO RD ID SO RD ID' FO RB ID FO RB ID' PFS ' PR ISM GT ree Dia mo nd	SORDID Diamond GTree PRISM PFS' FORBID' FORBID SORDID'	SO RD ID SO RD ID' FO RB ID FO RB ID' PFS ' PR ISM GT ree Dia mo nd
	(a) Nodes Ortogh. Order			(b) Aspect Ratio		(c) Convex Hull Area		(d) Node Movements	(e) Edge Length Preserv.
		10 1			2.0 2.2			10 2			10 6 10 7	10 0
	oo_nni	10 2		gs_bb_iar	1.4 1.6 1.8		sp_ch_a	10 1		nm_dm_imse	10 3 10 4 10 5
					1.0 1.2			10 0			10 2	10 1
	SORDID SORDID' FORBID FORBID' PFS' PRISM GTree Diamond	SO RD ID SO RD ID' FO RB ID FO RB ID' PFS ' PR ISM GT ree Dia mo nd	SORDID SORDID' FORBID FORBID' PFS' PRISM GTree Diamond	SO RD ID SO RD ID' FO RB ID FO RB ID' PFS ' PR ISM GT ree Dia mo nd	SORDID SORDID' FORBID FORBID' PFS' PRISM GTree Diamond	SO RD ID SO RD ID' FO RB ID FO RB ID' PFS ' PR ISM GT ree Dia mo nd	SORDID SORDID' FORBID FORBID' PFS' PRISM GTree Diamond	SO RD ID SO RD ID' FO RB ID FO RB ID' PFS ' PR ISM GT ree Dia mo nd	SORDID Diamond GTree PRISM PFS' FORBID' FORBID SORDID'	SO RD ID SO RD ID' FO RB ID FO RB ID' PFS ' PR ISM GT ree Dia mo nd
	(a) Nodes Ortogh. Order			(b) Aspect Ratio		(c) Convex Hull Area		(d) Node Movements

el_rsdd (e) Edge Length Preserv.

Generated and Graphviz graphs: https://github.com/agorajs/agora-dataset

ACKNOWLEDGMENTS

This research was founded by the french ANR project InvolvD OPE 2020-0425.