Node Overlap Removal Algorithms: A Comparative Study

Arnaud Sallaberry; Fati Chen; Laurent Piccinini; Pascal Poncelet

REVIEW 4 major objections 5 minor 18 references

Node Overlap Removal Algorithms: A Comparative Study

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read VPSC and R Wordle-L produce the best overlap-free graph layouts in a five-criterion comparison of eight algorithms.

desk verdict Useful first large benchmark and metric taxonomy for overlap removal, but the VPSC/Wordle-L top-two claim rests on one hand-picked metric per criterion with no sensitivity analysis. read the letter →

arxiv 1908.07363 v2 pith:TWKDOJD4 submitted 2019-08-20 cs.CG

Fati Chen , Laurent Piccinini , Pascal Poncelet , Arnaud Sallaberry This is my paper · ORCID

classification cs.CG

keywords nodeoverlapremovalgraphdrawinglayoutadjustmentqualitymetricsmentalmappreservationalgorithmcomparisonvisualization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper sets out to settle a practical question for visualization designers: given an initial graph layout in which nodes overlap, which post-processing algorithm removes the overlap while best preserving the layout a user has in mind? It reviews 21 quality metrics from the literature, groups them into five quality criteria, and selects one representative metric per criterion, then runs eight state-of-the-art overlap-removal algorithms on 854 graphs under that common measurement protocol. The conclusion is that VPSC and R Wordle-L deliver the best overall quality, with R Wordle-L superior on preserving global shape and VPSC far faster. If the comparison is right, designers have a clear default choice depending on whether speed or shape fidelity matters more. The paper also gives the community a reusable evaluation protocol: future algorithms can be scored on the same five metrics and compared directly.

What carries the argument

The argument is carried by a five-metric evaluation instrument, one representative per quality criterion: oo_nni (normalized number of inversions, capturing orthogonal-order preservation), sp_ch_a (ratio of convex-hull areas, capturing spread minimization), gs_bb_iar (improved bounding-box aspect-ratio deviation, capturing global-shape preservation), nm_dm_imse (mean squared node displacement after a shift-and-scale alignment, capturing node-movement minimization), and el_rsdd (relative standard deviation of Delaunay edge-length ratios, capturing edge-length preservation). This metric set, combined with a fixed experimental protocol using FM3 and SFDP initial layouts and eight algorithms on 854 graphs, is what makes the ranking of algorithms comparable.

What would settle it

Rerun the same eight algorithms on the same 854 graphs using the non-selected within-class metrics (for example gs_ch_sd for global shape, nm_knn for node movement, and sp_bb_a for spread) and check whether VPSC and R Wordle-L still lead; if another algorithm tops the revised ranking, the representative-metric choice, not the algorithms themselves, drives the conclusion.

Watch

Extended reading notes

Core claim

The central claim is that, among eight overlap-removal algorithms evaluated on a uniform set of five quality metrics over 840 synthetic and 14 real-world graphs, VPSC and R Wordle-L dominate on quality: VPSC matches or nearly matches the best on all criteria except global shape, where R Wordle-L is better, while VPSC requires substantially less running time. Uniform scaling scores best on four of the five metrics but is deemed unsatisfactory because it inflates the drawing area. PFS' and PRISM are intermediate, and GTREE suffers from large node movements on synthetic graphs. Across random, tree, small-world, and scale-free graphs the relative results do not change significantly, so the recommendation is not graph-type specific.

Load-bearing premise

The entire ranking assumes the five selected metrics are faithful, comparable proxies for the five quality criteria; choosing a different reasonable metric within a class could change which algorithm is declared best.

Editorial extensions

If this is right

Designers who need fast overlap removal on larger graphs should prefer VPSC, since it matches R Wordle-L on four of the five quality criteria and runs much faster.
When preserving the global silhouette of the original layout matters most, R Wordle-L is the better choice.
Uniform scaling should not be used in practice despite its top metric scores, because it expands the drawing area too much.
Future overlap-removal papers can report the five representative metrics so their results are directly comparable with this study.
The ranking appears stable across random, tree, small-world, and scale-free graphs, so algorithm choice need not depend on graph type.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper leaves the relative weight of the five criteria to the designer; a task-weighted composite score could change the VPSC-versus-R Wordle-L trade-off for a specific application.
Because the selected metrics are proxies, the natural robustness check is to rerun the comparison with the discarded within-class metrics such as gs_ch_sd or nm_knn; the paper's reported correlations suggest they behave similarly but not identically.
The conclusion about graph-type independence was tested only on graphs up to 1,000 nodes with one initial layout family per type, so extrapolation to larger graphs or other layout algorithms is an extension of the paper's claim.
A designer who cares about local neighborhood preservation rather than raw displacement might rank GTREE differently, since GTREE did well on real-world graphs but poorly on the movement-distance metric.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This paper is the first to compare eight node overlap removal algorithms on a common corpus of 854 graphs, and it organizes 21 metrics into five quality classes. That alone makes it useful for visualization designers who need to pick an algorithm.

The classification is a real contribution, and the authors make sensible choices in places, like replacing the unbounded aspect-ratio metric with their refined gs_bb_iar. They also report running times, which matters for practical use, and the qualitative rankings in the text are consistent with the boxplots they show.

The soft spot is the one the stress-test flags: each of the five criteria is represented by exactly one metric, selected by the authors' judgment. The selection is not the problem by itself, but they never show that the relative ranking of the eight algorithms is insensitive to that choice. They report a correlation of 0.77 between gs_bb_iar and gs_ch_sd, which is high but not high enough to rule out rank changes among VPSC, FTA, PRISM, and R Wordle-L. And there is no significance testing or confidence intervals on the boxplots, so 'best quality results' may claim more than the data support. The lack of released code and data also makes it hard to check whether node sizes or dataset construction affect the outcome.

These are fixable. A sensitivity analysis that reruns the ranking with alternative metrics, or a permutation test on the rankings, would settle the main worry. I would not call the paper misleading; it is a careful empirical study with a reasonable but provisional conclusion.

Who it is for: anyone working on layout adjustment or graph drawing evaluation. It deserves a serious referee, but not publication without the robustness checks. I would send it to review with a request for sensitivity analysis and artifacts.

Referee Report

4 major / 5 minor

Summary. This paper presents a comparative study of node overlap removal algorithms. The authors first review 21 quality metrics from the literature, classify them into five quality criteria (orthogonal ordering preservation, spread minimization, global shape preservation, node movement minimization, and edge length preservation), and select one representative metric per class, including a new normalized aspect-ratio metric (gs_bb_iar). They then compare eight overlap removal algorithms (Scaling, PFS, PFS', FTA, VPSC, PRISM, R Wordle-L, and GTREE) on 840 synthetic graphs and 14 real-world graphs, using the five selected metrics plus running time. The central conclusion is that VPSC and R Wordle-L achieve the best quality results, with R Wordle-L superior in global shape preservation and comparable on other criteria, while VPSC is faster.

Significance. If the comparison is sound, the paper provides a useful service to visualization designers by organizing a scattered metric literature, proposing a normalized improvement over an existing metric, and offering the first broad empirical comparison of eight overlap removal algorithms on a substantial benchmark. The experimental protocol is clearly described, the dataset is large and diverse, and the authors are careful to separate quality dimensions. However, the significance is limited by the subjective selection of representative metrics, the absence of statistical tests, and an unspecified node-size model, all of which bear directly on whether the headline ranking is robust.

major comments (4)

[Sec. 3, especially Secs. 3.2–3.5] The selection of one representative metric per quality criterion is load-bearing for the paper's conclusion, but the authors do not show that the ranking of the eight algorithms is insensitive to this choice. For example, gs_bb_iar is preferred over gs_ch_sd based on a correlation coefficient of 0.77; a correlation that leaves 40% unexplained can still permit rank changes among the top algorithms such as VPSC, FTA, PRISM, and R Wordle-L. I recommend adding a sensitivity analysis that recomputes the rankings under alternative representatives within each class (or across all 21 metrics), so that the reader can see whether the conclusion 'VPSC and R Wordle-L obtained the best quality results' is an artifact of metric choice.
[Sec. 4.1, Figs. 1–2] The qualitative claims, such as 'R Wordle-L outperforms VPSC on global shape preservation and is comparable on the other criteria,' are based on aggregated boxplots and means without any paired significance tests, confidence intervals, or effect-size measures. The distributions in Figs. 1 and 2 visibly overlap, so differences between the top algorithms may be within noise. I ask the authors to add paired statistical tests (e.g., Wilcoxon signed-rank with appropriate multiple-comparison correction) or bootstrap confidence intervals for the five metrics, and to report effect sizes. This is necessary to support the central ranking claim.
[Sec. 4, Step 1 (Datasets)] The experimental protocol never specifies how node widths and heights (w_v, h_v) are assigned for the synthetic and real-world graphs. Overlap removal algorithms and all five quality metrics depend directly on these sizes; without a precise node-size model the experiment is not reproducible, and the results may not generalize to other node-size distributions. The paper should state the node-size generation procedure (e.g., uniform random, proportional to degree or area of the initial FM^3 layout) and ideally include a robustness check across different size models.
[Sec. 5, Conclusion] The sentence 'we did not observe any significant differences in terms of results' across graph types is an overstatement because no statistical tests are reported for this comparison either. This should either be removed or supported by a proper interaction analysis of graph type with algorithm performance.

minor comments (5)

[Sec. 3.4, Table 2] The notation in the column for the normalizing function is ambiguous: '1/k√(2×n)' should be typeset as 1/(k*sqrt(2*n)) or similar, and the variable k should be defined earlier in the same paragraph to avoid confusion with the KNN parameter in nm_knn.
[Sec. 3.5] In the formula for el_rsdd, the subscript 'E2_dt' appears twice where the text defines the Delaunay edge set as 'Edt'; please correct these typos.
[Sec. 4.1, first paragraph] The phrase 'as it is proved that they maintain the original orthogonal ordering' would benefit from a citation or a short proof sketch, since the reader cannot verify this claim from the text alone.
[Sec. 4, Step 3] The paper does not state whether the same graph layouts (FM^3 for synthetic, SFDP for real-world) are used as initial embeddings for all algorithms, nor how ties and degenerate cases (e.g., nodes with identical initial coordinates) are handled. A brief clarification would improve reproducibility.
[Conclusion] The phrase 'Scaling optimises 4 out of 5 criteria' is slightly misleading because Scaling's best score on oo_nni is trivially expected from its definition; the reader should be told that the statement refers to the measured medians on the presented datasets.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the comparison is an empirical evaluation against external benchmarks using independently defined metrics.

full rationale

The paper's central claim, that VPSC and R Wordle-L obtain the best quality results, is an empirical comparison of eight published node overlap removal algorithms on 854 synthetic and real-world graphs. The five quality metrics are defined in Section 3 from geometric properties of the initial and adjusted embeddings (e.g., bounding boxes, convex hulls, distances), and they are not fitted to any algorithm's output or to the final ranking. The selection of one representative metric per criterion is justified by interpretability and pairwise correlations among metrics, which is a methodological choice rather than a circular reduction: the chosen metrics are not defined in terms of the algorithms being compared, nor are they derived from the conclusion. No parameters are fitted to the data and then presented as predictions. The authors do not rely on self-citations: the reference list contains no works by the present authors, and no uniqueness theorem or prior claim by the authors is invoked to force the choice of algorithms or metrics. Although one metric, gs_bb_iar, is a new refinement of an existing metric, it is explicitly proposed and then applied consistently to all algorithms; this is not a case where the target result is built into the measurement by construction. Concerns about whether the chosen representative metrics are the most appropriate, or whether the headline ranking is robust to alternative metric choices, are substantive evaluation-design questions, but they do not make the derivation circular. Therefore the paper receives a circularity score of 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim (which algorithms are best) does not rest on fitted numerical parameters. It rests on the choice of metric classes, the representative metrics, and the experimental protocol. No new entities are introduced.

assumptions (4)

domain assumption The five identified criteria are the relevant quality dimensions for overlap removal.
Section 3 organizes all reviewed metrics into these classes and treats the set as complete, with no external validation.
ad hoc to paper The selected representative metrics adequately capture their respective criteria.
Section 3 selects representatives based on interpretability, normalization, and correlation (e.g., gs_bb_iar over gs_ch_sd at r=0.77, nm_dm_imse over others). These are judgment calls, not proven equivalences.
domain assumption The experimental protocol reflects typical overlap removal usage.
Section 4.1 fixes node sizes implicitly, uses FM3 and SFDP for initial layouts, and graph generators from OGDF; the influence of these choices on the ranking is not analyzed.
domain assumption Algorithms are implemented according to their original papers with appropriate parameters.
The paper relies on implementations of PFS, FTA, VPSC, PRISM, R Wordle-L, and GTREE without providing code or parameter settings, so faithfulness to the originals is assumed.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Node Overlap Removal Algorithms: A Comparative Study." pith.science (2026). https://pith.science/paper/TWKDOJD4

@misc{pith2026190807363,
  author       = {Pith},
  title        = {Pith review of: Node Overlap Removal Algorithms: A Comparative Study},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TWKDOJD4}},
  note         = {Machine review of arXiv:1908.07363}
}

read the original abstract

Many algorithms have been designed to remove node overlapping, and many quality criteria and associated metrics have been proposed to evaluate those algorithms. Unfortunately, a complete comparison of the algorithms based on some metrics that evaluate the quality has never been provided and it is thus difficult for a visualization designer to select the algorithm that best suits his needs. In this paper, we review 21 metrics available in the literature, classify them according to the quality criteria they try to capture, and select a representative one for each class. Based on the selected metrics, we compare 8 node overlap removal algorithms. Our experiment involves 854 synthetic and real-world graphs.

Figures

Figures reproduced from arXiv: 1908.07363 by the authors.

**Figure 1.** and 2 show the aggregated metrics values on the synthetic and realworld datasets. Unsurprisingly, Scaling, PFS and PFS’ obtain the best scores at oo_nni as it is proved that they maintain the original orthogonal ordering. Though, all the algorithms tested got good results for this criterion [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗

**Figure 2.** Mean values of the selected metrics among the real-world graphs. Scaling preserves the initial global shape4 (gs_bb_iar score). PFS is the worst algorithm on this criterion. The other algorithms obtained good median scores on synthetic graphs, but the third quartile scores show that FTA and VPSC can produce a certain amount of distorted embeddings. This is confirmed by the tests on real-world graphs, where they obta… view at source ↗

**Figure 3.** Aggregated running times among the synthetic graphs, function of number of nodes (10 to 1,000): first quartile, median and third quartile [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Mean values of running times among the real-world graphs. as it increases the size of the embedding too much. PFS is also not satisfying as it got poor results on 3 criteria. FTA obtained intermediate results over all the criteria, which is less good than all its remai…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 17 canonical work pages

[1]

Science 286(5439), 509–512 (1999)

Barabaśi, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)

work page 1999
[2]

In: Tamassia, R

Chimani, M., Gutwenger, C., Jünger, M., Klau, G.W., Klein, K., Mutzel, P.: The open graph drawing framework (OGDF). In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization., pp. 543–569. Chapman and Hall/CRC (2013)

work page 2013
[3]

In: International Symposium on Graph Drawing

Dwyer, T., Marriott, K., Stuckey, P.J.: Fast node overlap removal. In: International Symposium on Graph Drawing. pp. 153–164. Springer (2005)

work page 2005
[4]

Publicationes Mathematicae Debrecen6, 290–291 (1959)

Erdös, P., Rényi, A.: On random graphs. Publicationes Mathematicae Debrecen6, 290–291 (1959)

work page 1959
[5]

Journal of Graph Algorithms and Applications14(1), 53–74 (2010)

Gansner, E., Hu, Y.: Eﬃcient, proximity-preserving node overlap removal. Journal of Graph Algorithms and Applications14(1), 53–74 (2010)

work page 2010
[6]

Software: practice and experience30(11), 1203–1233 (2000)

Gansner, E.R., North, S.C.: An open graph visualization system and its applica- tions to software engineering. Software: practice and experience30(11), 1203–1233 (2000)

work page 2000
[7]

In: Pach, J

Hachul, S., Jünger, M.: Drawing large graphs with a potential-ﬁeld-based multi- level algorithm. In: Pach, J. (ed.) Graph Drawing. pp. 285–295. Springer Berlin Heidelberg, Berlin, Heidelberg (2005)

work page 2005
[8]

Hayashi, K., Inoue, M., Masuzawa, T., Fujiwara, H.: A layout adjustment problem fordisjointrectanglespreservingorthogonalorder.In:Whitesides,S.H.(ed.)Graph Drawing. pp. 183–197. Springer Berlin Heidelberg, Berlin, Heidelberg (1998)

work page 1998

Show all 18 references

[9]

Mathematica Journal 10(1), 37–71 (2005)

Hu, Y.: Eﬃcient, high-quality force-directed graph drawing. Mathematica Journal 10(1), 37–71 (2005)

2005
[10]

In: Proceedings of the 26th Australasian computer science conference-Volume 16

Huang, X., Lai, W.: Force-transfer: a new approach to removing overlapping nodes in graph layout. In: Proceedings of the 26th Australasian computer science conference-Volume 16. pp. 349–358. Australian Computer Society, Inc. (2003)

2003
[11]

Information Sciences177(14), 2821 – 2844 (2007)

Huang, X., Lai, W., Sajeev, A., Gao, J.: A new algorithm for removing node over- lapping in graph visualization. Information Sciences177(14), 2821 – 2844 (2007)

2007
[12]

In: Proceedings of the 2005 Asia-Paciﬁc Symposium on Information Visualisation - Volume 45

Li, W., Eades, P., Nikolov, N.: Using spring algorithms to remove node overlapping. In: Proceedings of the 2005 Asia-Paciﬁc Symposium on Information Visualisation - Volume 45. pp. 131–140. APVis ’05, Australian Computer Society, Inc., Dar- linghurst, Australia (2005)

2005
[13]

Journal of Graph Algorithms and Applications2(1), 1–24 (1998)

Lyons, K.A., Meijer, H., Rappaport, D.: Algorithms for cluster busting in anchored graph drawing. Journal of Graph Algorithms and Applications2(1), 1–24 (1998)

1998
[14]

Constraints8(2), 143–171 (2003)

Marriott, K., Stuckey, P., Tam, V., He, W.: Removing node overlapping in graph layout using constrained optimization. Constraints8(2), 143–171 (2003)

2003
[15]

Journal of Visual Languages & Computing6(2), 183–210 (1995)

Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. Journal of Visual Languages & Computing6(2), 183–210 (1995)

1995
[16]

In: International Symposium on Graph Drawing and Network Visualization

Nachmanson, L., Nocaj, A., Bereg, S., Zhang, L., Holroyd, A.: Node overlap re- moval by growing a tree. In: International Symposium on Graph Drawing and Network Visualization. pp. 33–43. Springer (2016)

2016
[17]

Computer Graph- ics Forum31(3), 1135–1144 (2012)

Strobelt, H., Spicker, M., Stoﬀel, A., Keim, D., Deussen, O.: Rolled-out wordles: A heuristic method for overlap removal of 2d data representatives. Computer Graph- ics Forum31(3), 1135–1144 (2012)

2012
[18]

Nature 393, 440–442 (1998)

Watts, D.J., Strogatz, S.H.: Collective dynamics of ’small-world’ networks. Nature 393, 440–442 (1998)

1998

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Science 286(5439), 509–512 (1999)

Barabaśi, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)

work page 1999

[2] [2]

In: Tamassia, R

Chimani, M., Gutwenger, C., Jünger, M., Klau, G.W., Klein, K., Mutzel, P.: The open graph drawing framework (OGDF). In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization., pp. 543–569. Chapman and Hall/CRC (2013)

work page 2013

[3] [3]

In: International Symposium on Graph Drawing

Dwyer, T., Marriott, K., Stuckey, P.J.: Fast node overlap removal. In: International Symposium on Graph Drawing. pp. 153–164. Springer (2005)

work page 2005

[4] [4]

Publicationes Mathematicae Debrecen6, 290–291 (1959)

Erdös, P., Rényi, A.: On random graphs. Publicationes Mathematicae Debrecen6, 290–291 (1959)

work page 1959

[5] [5]

Journal of Graph Algorithms and Applications14(1), 53–74 (2010)

Gansner, E., Hu, Y.: Eﬃcient, proximity-preserving node overlap removal. Journal of Graph Algorithms and Applications14(1), 53–74 (2010)

work page 2010

[6] [6]

Software: practice and experience30(11), 1203–1233 (2000)

Gansner, E.R., North, S.C.: An open graph visualization system and its applica- tions to software engineering. Software: practice and experience30(11), 1203–1233 (2000)

work page 2000

[7] [7]

In: Pach, J

Hachul, S., Jünger, M.: Drawing large graphs with a potential-ﬁeld-based multi- level algorithm. In: Pach, J. (ed.) Graph Drawing. pp. 285–295. Springer Berlin Heidelberg, Berlin, Heidelberg (2005)

work page 2005

[8] [8]

Hayashi, K., Inoue, M., Masuzawa, T., Fujiwara, H.: A layout adjustment problem fordisjointrectanglespreservingorthogonalorder.In:Whitesides,S.H.(ed.)Graph Drawing. pp. 183–197. Springer Berlin Heidelberg, Berlin, Heidelberg (1998)

work page 1998