Adventures in Abstraction: Reachability in Hierarchical Drawings

Giacomo Ortali; Ioannis G. Tollis; Panagiotis Lionakis

arxiv: 1907.11662 · v1 · pith:WR53RVK2new · submitted 2019-07-26 · 💻 cs.DS · cs.HC

Adventures in Abstraction: Reachability in Hierarchical Drawings

Panagiotis Lionakis , Giacomo Ortali , Ioannis G. Tollis This is my paper

Pith reviewed 2026-05-24 15:01 UTC · model grok-4.3

classification 💻 cs.DS cs.HC

keywords directed graphsreachabilityhierarchical drawingspath decompositionchannel decompositiongraph visualizationtransitivity

0 comments

The pith

Customized path and channel decompositions visualize reachability in directed graphs by aligning vertices vertically and drawing only a subset of edges.

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

The paper develops algorithms for drawing directed graphs that emphasize reachability information through hierarchical layouts based on path and channel decompositions. It customizes these decompositions to create drawings where paths are clearly visible without introducing extra vertices. These methods run in almost linear time and allow for more abstract representations as more channels are used. This approach reduces the number of edges drawn, which helps in managing visual complexity and storing transitivity data for large graphs. Experiments explore how bends and crossings affect the clarity of the reachability display.

Core claim

By customizing the path and channel decomposition concepts, algorithms are presented that produce hierarchical drawings of directed graphs displaying reachability, with vertices of each path or channel vertically aligned, no dummy vertices introduced, and only a subset of edges drawn, all in O(kn + m) time where k is the number of paths or channels.

What carries the argument

Customized path and channel decompositions that group vertices into vertically aligned paths or channels to highlight reachability paths in the drawing.

If this is right

Only a subset of the edges needs to be drawn, reducing visual complexity of the resulting drawing.
Transitivity information can be stored using lower memory requirements for very large graphs and databases.
Drawings can be produced at increasing levels of abstraction by varying the number of paths or channels.
The approach applies directly to the problem of showing and storing transitivity information.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The vertical alignment of vertices on paths could support interactive tools for querying reachability in large networks.
The method's focus on a subset of edges might combine with existing transitive closure algorithms to handle even larger data sets.
Experiments on the trade-off between bends and crossings suggest similar decompositions could be tested on other layout styles beyond hierarchical drawings.

Load-bearing premise

Customizing path and channel decompositions will produce drawings where reachability is clearly displayed as shown by experiments balancing bends, crossings, and clarity.

What would settle it

A collection of drawings from the algorithms in which reachability between vertices cannot be determined quickly because of high numbers of crossings or non-obvious path alignments.

Figures

Figures reproduced from arXiv: 1907.11662 by Giacomo Ortali, Ioannis G. Tollis, Panagiotis Lionakis.

**Figure 1.** Figure 1: In (a) we show the drawing of a graph G as computed by Tom Sawyer Perspectives which follows the Sugiyama framework. In (b) we show the drawing Γ based on G computed by Algorithm PB-Draw. In (c) we show an abstracted hierarchical drawing computed by our final variant. 3 [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

**Figure 2.** Figure 2: Drawings of DAG 1 drawn with (a) Variant 1 and (b) Variant 2. The following theorem is proved in Section 7 of the Appendix. Theorem 1. Let G be a DAG with n vertices and m edges, let Sp be a path decomposition of G and let k be the cardinality of Sp. It is possible to compute the drawings Γ1 according to Variant 1 in O(n + m) time and the drawings Γ2, Γ3, Γ4, Γ5, and Γ6 according to Variant 2, Variant 3, V… view at source ↗

**Figure 3.** Figure 3: Drawings of DAG 1 drawn with (a) Variant 3 and (b) Variant 4. that was used to illustrate Algorithm 1 in [9] [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

**Figure 4.** Figure 4: Drawings of DAG 1 drawn with (a) Variant 5 and (b) Variant 6. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗

**Figure 5.** Figure 5: Results on number of cross edges drawn for each variant over all DAGs. First we discuss the number of edges drawn by our variants. By construction Variant 0 and Variant 1 draw exactly the same set of edges as it is evidenced by Figures 5 and 6. The same figures show that Variant 2 and Variant 3 are similar in the number of edges they draw. Clearly, the number of edges drawn by Variant 4 is significantly lo… view at source ↗

**Figure 6.** Figure 6: Results on number of edges drawn for each variant over all DAGs [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗

**Figure 7.** Figure 7: Results on number of bends for each variant over all DAGs. As can be seen in [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗

**Figure 8.** Figure 8: Results on number of crossings for each variant over the (a) DAGs 1,2,3 and (b) DAGs 4,5. The number of crossings is influenced heavily by the number of edges drawn and the extent of edge bundling [PITH_FULL_IMAGE:figures/full_fig_p012_8.png] view at source ↗

read the original abstract

We present algorithms and experiments for the visualization of directed graphs that focus on displaying their reachability information. Our algorithms are based on the concepts of the path and channel decomposition as proposed in the framework presented in GD 2018 (pp. 579-592) and focus on showing the existence of paths clearly. In this paper we customize these concepts and present experimental results that clearly show the interplay between bends, crossings and clarity. Additionally, our algorithms have direct applications to the important problem of showing and storing transitivity information of very large graphs and databases. Only a subset of the edges is drawn, thus reducing the visual complexity of the resulting drawing, and the memory requirements for storing the transitivity information. Our algorithms require almost linear time, $O(kn+m)$, where $k$ is the number of paths/channels, $n$ and $m$ is the number of vertices and edges, respectively. They produce progressively more abstract drawings of the input graph. No dummy vertices are introduced and the vertices of each path/channel are vertically aligned.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This extends the 2018 GD path/channel decomposition with customizations and new experiments on bends, crossings, and clarity for reachability drawings.

read the letter

The paper customizes the path and channel decomposition from the cited 2018 GD work to produce hierarchical drawings that highlight reachability in directed graphs. It reports almost linear time O(kn + m), avoids dummy vertices, aligns path vertices vertically, and draws only a subset of edges. The main addition is experimental results on the trade-offs between bends, crossings, and visual clarity, plus a note on storing transitivity information for large graphs and databases. These points are straightforward and build directly on the prior framework without introducing new dummy elements or major changes to the layout style. The experiments appear to be the concrete new content, showing how different decomposition choices affect the final drawing. That part gives a practical angle for people who need to visualize reachability without excessive clutter. The time bound is stated clearly and the no-dummy-vertex choice keeps the output simple. The soft spot is that the customizations are described at a high level in the abstract, so it is not obvious how substantial the changes are versus minor adjustments to the 2018 method. The clarity claims rest on the experiments, but without the specific graphs, metrics, or measurement details it is hard to judge whether the improvements are robust or depend on particular test cases. The transitivity application is mentioned but not developed with concrete storage numbers or comparisons. This is aimed at graph drawing researchers who already know the 2018 framework and want to see experimental follow-up on reachability-focused layouts. A reader working on hierarchical drawings or transitivity visualization could pick up the runtime and alignment ideas. It deserves peer review because it reports new experiments on an established approach with a clear complexity statement, even if the full validation of the clarity results would need the manuscript details.

Referee Report

2 major / 2 minor

Summary. The paper presents algorithms for visualizing directed graphs to emphasize reachability information. Building on path and channel decompositions from the GD 2018 framework, the authors customize these concepts to produce hierarchical drawings in which vertices of each path or channel are vertically aligned, no dummy vertices are added, and only a subset of edges is drawn. The algorithms are claimed to run in O(kn + m) time and to yield progressively more abstract drawings; experimental results are reported on the interplay among bends, crossings, and visual clarity. Direct applications to compact storage of transitivity information in large graphs and databases are discussed.

Significance. If the claimed linear-time bound holds and the customizations demonstrably improve reachability clarity without post-hoc parameter tuning, the work would offer a practical contribution to graph drawing and to the compact representation of transitive closures. The absence of dummy vertices and the vertical-alignment property are attractive for readability and for downstream applications such as database visualization. The experimental focus on bends versus crossings is a positive step toward falsifiable claims about clarity, though its strength cannot be evaluated from the abstract alone.

major comments (2)

[Abstract] The abstract asserts an O(kn + m) running time but supplies neither the algorithm description, the definition of the customized path/channel decomposition, nor a proof sketch. Without these, it is impossible to verify whether the bound is achieved or whether the customizations preserve the properties needed for the reachability claim.
[Abstract] The claim that the drawings 'clearly show the existence of paths' rests on experimental results whose measurement protocol (how reachability clarity is quantified, how post-hoc choices of k are made, and which baseline drawings are used) is not described. This makes the central empirical support for the customizations impossible to assess.

minor comments (2)

[Abstract] Grammatical error: 'n and m is the number' should read 'n and m are the numbers'.
[Abstract] The phrase 'progressively more abstract drawings' is used without a precise definition of the abstraction ordering or the stopping criterion.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the comments on our manuscript. We address each major comment below, clarifying the relationship between the abstract and the full technical content.

read point-by-point responses

Referee: [Abstract] The abstract asserts an O(kn + m) running time but supplies neither the algorithm description, the definition of the customized path/channel decomposition, nor a proof sketch. Without these, it is impossible to verify whether the bound is achieved or whether the customizations preserve the properties needed for the reachability claim.

Authors: The abstract is a concise summary. The manuscript supplies the requested material: the customized path and channel decompositions are defined in Section 3, the algorithms (including the vertical-alignment and no-dummy-vertex properties) are presented in Section 4, and the O(kn + m) analysis appears in the same section together with the argument that the selected edges preserve reachability. The customizations inherit the reachability guarantees of the GD 2018 framework while adding the alignment constraint. revision: no
Referee: [Abstract] The claim that the drawings 'clearly show the existence of paths' rests on experimental results whose measurement protocol (how reachability clarity is quantified, how post-hoc choices of k are made, and which baseline drawings are used) is not described. This makes the central empirical support for the customizations impossible to assess.

Authors: The experimental protocol, including the clarity metric, the procedure for selecting k, and the baseline drawings, is described in Section 5. The abstract reports the outcome of those experiments. A one-sentence reference to Section 5 could be added to the abstract if the editor prefers. revision: partial

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The abstract describes algorithms that customize path and channel decomposition concepts from the cited GD 2018 framework, then presents new experimental results on the interplay of bends, crossings, and clarity along with a claimed O(kn+m) runtime. No derivation, equation, or self-referential definition is exhibited that reduces any claimed result to its own inputs by construction; the citation supplies an external starting point that is then modified, and the work adds independent content via customizations and applications to transitivity storage. This is the normal case of a paper that is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the validity of the GD 2018 path and channel decomposition framework as a foundation for customization; no free parameters, new entities, or ad-hoc axioms beyond standard graph theory are introduced in the abstract.

axioms (1)

domain assumption The path and channel decomposition framework proposed in GD 2018 is suitable for representing and visualizing reachability in directed graphs.
The algorithms are explicitly based on customizing this prior framework.

pith-pipeline@v0.9.0 · 5717 in / 1177 out tokens · 33393 ms · 2026-05-24T15:01:19.233471+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Tom Sawyer Software, www.tomsawyer.com

work page
[2]

IEEE Trans

Gansner, E.R., Koutsoﬁos, E., North, S.C., Vo, K.: A technique for draw- ing directed graphs. IEEE Trans. Software Eng. 19(3), 214–230 (1993). https://doi.org/10.1109/32.221135, https://doi.org/10.1109/32.221135

work page doi:10.1109/32.221135 1993
[3]

Hopcroft, J.E., Karp, R.M.: An n 5/2 algorithm for maximum match- ings in bipartite graphs. SIAM J. Comput. 2(4), 225–231 (1973). https://doi.org/10.1137/0202019, https://doi.org/10.1137/0202019

work page doi:10.1137/0202019 1973
[4]

ACM Trans

Jagadish, H.V.: A compression technique to materialize transitive closure. ACM Trans. Database Syst. 15(4), 558–598 (Dec 1990). https://doi.org/10.1145/99935.99944, http://doi.acm.org/10.1145/99935. 99944

work page doi:10.1145/99935.99944 1990
[5]

In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20-24, 2012

Jin, R., Ruan, N., Dey, S., Yu, J.X.: SCARAB: scaling reachability computation on large graphs. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20-24, 2012. pp. 169–180 (2012). https://doi.org/10.1145/2213836.2213856, https://doi.org/ 10.1145/2213836.2213856

work page doi:10.1145/2213836.2213856 2012
[6]

In: Research in Computational Molecular Biology - 22nd Annual International Conference, RECOMB 2018, Paris, France, April 21-24, 2018, Proceedings

Kuosmanen, A., Paavilainen, T., Gagie, T., Chikhi, R., Tomescu, A.I., M¨ akinen, V.: Using minimum path cover to boost dynamic programming on dags: Co- linear chaining extended. In: Research in Computational Molecular Biology - 22nd Annual International Conference, RECOMB 2018, Paris, France, April 21-24, 2018, Proceedings. pp. 105–121 (2018). https://doi...

work page doi:10.1007/978-3-319-89929- 2018
[7]

World Wide Web 20(4), 677–696 (2017)

Li, L., Hua, W., Zhou, X.: HD-GDD: high dimensional graph dominance drawing approach for reachability query. World Wide Web 20(4), 677–696 (2017). https://doi.org/10.1007/s11280-016-0407-z, https://doi.org/10.1007/ s11280-016-0407-z

work page doi:10.1007/s11280-016-0407-z 2017
[8]

In: Symposium on Theory of Com- puting Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013

Orlin, J.B.: Max ﬂows in O(nm) time, or better. In: Symposium on Theory of Com- puting Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013. pp. 765–774 (2013). https://doi.org/10.1145/2488608.2488705, http://doi.acm.org/10.1145/ 2488608.2488705

work page doi:10.1145/2488608.2488705 2013
[9]

In: International Symposium on Graph Drawing and Network Visualization

Ortali, G., Tollis, I.G.: Algorithms and bounds for drawing directed graphs. In: International Symposium on Graph Drawing and Network Visualization. pp. 579–

work page
[10]

Graph cube: On warehousing and OLAP multidimensional networks

van Schaik, S.J., de Moor, O.: A memory eﬃcient reachability data structure through bit vector compression. In: Proceedings of the ACM SIGMOD Inter- national Conference on Management of Data, SIGMOD 2011, Athens, Greece, June 12-16, 2011. pp. 913–924 (2011). https://doi.org/10.1145/1989323.1989419, https://doi.org/10.1145/1989323.1989419

work page doi:10.1145/1989323.1989419 2011
[11]

Schnorr, C.: An algorithm for transitive closure with linear expected time. SIAM J. Comput. 7(2), 127–133 (1978). https://doi.org/10.1137/0207011, https://doi. org/10.1137/0207011

work page doi:10.1137/0207011 1978
[12]

IEEE Transactions on Systems, Man, and Cybernetics 11(2), 109–125 (1981)

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierar- chical system structures. IEEE Transactions on Systems, Man, and Cybernetics 11(2), 109–125 (1981)

work page 1981
[13]

In: Proceed- ings of the 17th International Conference on Extending Database Technol- ogy, EDBT 2014, Athens, Greece, March 24-28, 2014

Veloso, R.R., Cerf, L., Jr., W.M., Zaki, M.J.: Reachability queries in very large graphs: A fast reﬁned online search approach. In: Proceed- ings of the 17th International Conference on Extending Database Technol- ogy, EDBT 2014, Athens, Greece, March 24-28, 2014. pp. 511–522 (2014). 14 https://doi.org/10.5441/002/edbt.2014.46, https://doi.org/10.5441/002...

work page doi:10.5441/002/edbt.2014.46 2014
[14]

Yildirim, H., Chaoji, V., Zaki, M.J.: GRAIL: a scalable index for reach- ability queries in very large graphs. VLDB J. 21(4), 509–534 (2012). https://doi.org/10.1007/s00778-011-0256-4, https://doi.org/10.1007/ s00778-011-0256-4 15 Appendix 6 Algorithm PB-Draw The following algorithm and theorems and lemmas are from [9] Theorem 2. LetG be a DAG and letSp b...

work page doi:10.1007/s00778-011-0256-4 2012
[15]

assign to every vertex v∈ V belonging to the decomposition path Pi an x- coordinate X(v) = 2i and an y-coordinate Y (v) =Tv

work page
[16]

2: If the straight line drawing of e intersects some vertex w∈V diﬀerent from u orv in Γ , introduce a bend on e in the position (Xb,Y b), where Yb =Y (v)− 1 and:

draw every edge e = (u,v )∈E straight line. 2: If the straight line drawing of e intersects some vertex w∈V diﬀerent from u orv in Γ , introduce a bend on e in the position (Xb,Y b), where Yb =Y (v)− 1 and:

work page
[17]

If X(u)<X (v): Xb =X(u) + 1

work page
[18]

The following Lemmas and Theorem are proved in [9]

Else, if X(u)≥X(v): X(be) =X(u)− 1 Let Γ be a drawing computed by PB-Draw. The following Lemmas and Theorem are proved in [9]. Lemma 1. Any edge e = (u,v ) does not intersect a vertex diﬀerent from u and v in Γ . The following lemma shows how Algorithm PB-Draw bundles the edges. We apply this technique of bundling in every variant of PB-Draw that we intro...

work page

[1] [1]

Tom Sawyer Software, www.tomsawyer.com

work page

[2] [2]

IEEE Trans

Gansner, E.R., Koutsoﬁos, E., North, S.C., Vo, K.: A technique for draw- ing directed graphs. IEEE Trans. Software Eng. 19(3), 214–230 (1993). https://doi.org/10.1109/32.221135, https://doi.org/10.1109/32.221135

work page doi:10.1109/32.221135 1993

[3] [3]

Hopcroft, J.E., Karp, R.M.: An n 5/2 algorithm for maximum match- ings in bipartite graphs. SIAM J. Comput. 2(4), 225–231 (1973). https://doi.org/10.1137/0202019, https://doi.org/10.1137/0202019

work page doi:10.1137/0202019 1973

[4] [4]

ACM Trans

Jagadish, H.V.: A compression technique to materialize transitive closure. ACM Trans. Database Syst. 15(4), 558–598 (Dec 1990). https://doi.org/10.1145/99935.99944, http://doi.acm.org/10.1145/99935. 99944

work page doi:10.1145/99935.99944 1990

[5] [5]

In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20-24, 2012

Jin, R., Ruan, N., Dey, S., Yu, J.X.: SCARAB: scaling reachability computation on large graphs. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20-24, 2012. pp. 169–180 (2012). https://doi.org/10.1145/2213836.2213856, https://doi.org/ 10.1145/2213836.2213856

work page doi:10.1145/2213836.2213856 2012

[6] [6]

In: Research in Computational Molecular Biology - 22nd Annual International Conference, RECOMB 2018, Paris, France, April 21-24, 2018, Proceedings

Kuosmanen, A., Paavilainen, T., Gagie, T., Chikhi, R., Tomescu, A.I., M¨ akinen, V.: Using minimum path cover to boost dynamic programming on dags: Co- linear chaining extended. In: Research in Computational Molecular Biology - 22nd Annual International Conference, RECOMB 2018, Paris, France, April 21-24, 2018, Proceedings. pp. 105–121 (2018). https://doi...

work page doi:10.1007/978-3-319-89929- 2018

[7] [7]

World Wide Web 20(4), 677–696 (2017)

Li, L., Hua, W., Zhou, X.: HD-GDD: high dimensional graph dominance drawing approach for reachability query. World Wide Web 20(4), 677–696 (2017). https://doi.org/10.1007/s11280-016-0407-z, https://doi.org/10.1007/ s11280-016-0407-z

work page doi:10.1007/s11280-016-0407-z 2017

[8] [8]

In: Symposium on Theory of Com- puting Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013

Orlin, J.B.: Max ﬂows in O(nm) time, or better. In: Symposium on Theory of Com- puting Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013. pp. 765–774 (2013). https://doi.org/10.1145/2488608.2488705, http://doi.acm.org/10.1145/ 2488608.2488705

work page doi:10.1145/2488608.2488705 2013

[9] [9]

In: International Symposium on Graph Drawing and Network Visualization

Ortali, G., Tollis, I.G.: Algorithms and bounds for drawing directed graphs. In: International Symposium on Graph Drawing and Network Visualization. pp. 579–

work page

[10] [10]

Graph cube: On warehousing and OLAP multidimensional networks

van Schaik, S.J., de Moor, O.: A memory eﬃcient reachability data structure through bit vector compression. In: Proceedings of the ACM SIGMOD Inter- national Conference on Management of Data, SIGMOD 2011, Athens, Greece, June 12-16, 2011. pp. 913–924 (2011). https://doi.org/10.1145/1989323.1989419, https://doi.org/10.1145/1989323.1989419

work page doi:10.1145/1989323.1989419 2011

[11] [11]

Schnorr, C.: An algorithm for transitive closure with linear expected time. SIAM J. Comput. 7(2), 127–133 (1978). https://doi.org/10.1137/0207011, https://doi. org/10.1137/0207011

work page doi:10.1137/0207011 1978

[12] [12]

IEEE Transactions on Systems, Man, and Cybernetics 11(2), 109–125 (1981)

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierar- chical system structures. IEEE Transactions on Systems, Man, and Cybernetics 11(2), 109–125 (1981)

work page 1981

[13] [13]

In: Proceed- ings of the 17th International Conference on Extending Database Technol- ogy, EDBT 2014, Athens, Greece, March 24-28, 2014

Veloso, R.R., Cerf, L., Jr., W.M., Zaki, M.J.: Reachability queries in very large graphs: A fast reﬁned online search approach. In: Proceed- ings of the 17th International Conference on Extending Database Technol- ogy, EDBT 2014, Athens, Greece, March 24-28, 2014. pp. 511–522 (2014). 14 https://doi.org/10.5441/002/edbt.2014.46, https://doi.org/10.5441/002...

work page doi:10.5441/002/edbt.2014.46 2014

[14] [14]

Yildirim, H., Chaoji, V., Zaki, M.J.: GRAIL: a scalable index for reach- ability queries in very large graphs. VLDB J. 21(4), 509–534 (2012). https://doi.org/10.1007/s00778-011-0256-4, https://doi.org/10.1007/ s00778-011-0256-4 15 Appendix 6 Algorithm PB-Draw The following algorithm and theorems and lemmas are from [9] Theorem 2. LetG be a DAG and letSp b...

work page doi:10.1007/s00778-011-0256-4 2012

[15] [15]

assign to every vertex v∈ V belonging to the decomposition path Pi an x- coordinate X(v) = 2i and an y-coordinate Y (v) =Tv

work page

[16] [16]

2: If the straight line drawing of e intersects some vertex w∈V diﬀerent from u orv in Γ , introduce a bend on e in the position (Xb,Y b), where Yb =Y (v)− 1 and:

draw every edge e = (u,v )∈E straight line. 2: If the straight line drawing of e intersects some vertex w∈V diﬀerent from u orv in Γ , introduce a bend on e in the position (Xb,Y b), where Yb =Y (v)− 1 and:

work page

[17] [17]

If X(u)<X (v): Xb =X(u) + 1

work page

[18] [18]

The following Lemmas and Theorem are proved in [9]

Else, if X(u)≥X(v): X(be) =X(u)− 1 Let Γ be a drawing computed by PB-Draw. The following Lemmas and Theorem are proved in [9]. Lemma 1. Any edge e = (u,v ) does not intersect a vertex diﬀerent from u and v in Γ . The following lemma shows how Algorithm PB-Draw bundles the edges. We apply this technique of bundling in every variant of PB-Draw that we intro...

work page