Pith. sign in

REVIEW 3 major objections 5 minor 51 references

Outer-(ap)RAC Graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The paper proves that every outer-RAC graph is planar and that the class has a tight edge bound of $2.5n-4$.

desk verdict Plausible and interesting results, but the main planarity proof rests on an unproved block-outline lemma; the algorithm sections are the strongest part. read the letter →

arxiv 2411.17565 v1 pith:UVARV5Q2 submitted 2024-11-26 cs.CC

Förster , Julia Katheder , Giacomo Ortali This is my paper · ORCID
classification cs.CC MSC 05C1005C6268R10
keywords outer-RACgraphsright-anglecrossingdrawingsplanarityedgedensityseries-parallelSPQR-treebeyondaxis-parallelRAC
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 studies graphs that can be drawn with all vertices on the outer cell and every crossing at a right angle, the outer-RAC model, plus an axis-parallel variant where crossing edges are horizontal and vertical. Its main claim is that such drawings never force a graph to be non-planar: every outer-RAC graph is planar, so the right-angle condition restricts geometry without expanding topology. The paper also proves that any such graph on $n$ vertices has at most $2.5n-4$ edges and that this density bound is tight, with matching examples even in the axis-parallel case. For low-degree series-parallel graphs it provides linear-time drawing algorithms, and it exhibits planar graphs of small degree that cannot be drawn this way. If correct, the result reframes outer-RAC drawings as a geometric drawing style for a strict subclass of planar graphs rather than a new class of non-planar graphs.

What carries the argument

The argument turns on two devices. First, the crossing graph of a drawing is partitioned into blocks, maximal connected sets of edges that cross each other, and each block is assigned a closed outline $O(B)$ that is assumed to contain exactly that block's edges and to separate them from everything else; the planarity proof copies the interior of the outer cycle to the exterior and removes one of the two perpendicular slope sets in each copy, so those outlines let the crossings disappear. Second, the algorithmic results use the SPQR-tree of a biconnected graph, a tree decomposition by separation pairs, and draw the skeleton of each node inside reserved regions $R(\mu)$ so that a linear-time top-down traversal produces the required outer-(ap)RAC drawing.

What would settle it

Try to draw $K_{3,3}$ with all six vertices on the outer cell and every crossing at a right angle: Theorem 1 predicts this is impossible, so any such drawing would directly refute the planarity claim.

Watch

Extended reading notes

Core claim

The paper's central claim is that right-angle crossings do not make a graph non-planar as long as all vertices lie on the outer cell. Theorem 1 states that every outer-RAC graph is planar; the proof partitions crossing edges into blocks, encloses each block in a closed outline $O(B)$, then copies the interior of the outer cycle to the exterior and deletes one slope set per copy to uncross all edges. The paper further establishes that outer-RAC graphs form a proper subset of planar graphs and have at most $2.5n-4$ edges, a bound that is tight even for the more restricted outer-apRAC class. It provides linear-time algorithms for drawing biconnected series-parallel graphs: outer-apRAC drawings for maximum degree 3 and outer-RAC drawings for maximum degree 4. It also gives non-outer-RAC examples among degree-5 series-parallel graphs and degree-4 triconnected planar graphs.

Load-bearing premise

The planarity proof assumes that each block of crossing edges can be enclosed by a closed outline that contains exactly that block's edges and no others, and that these outlines never cross each other; this geometric fact is stated without proof.

Editorial extensions

If this is right

  • Non-planar graphs such as $K_5$ or $K_{3,3}$ cannot admit outer-RAC drawings, since Theorem 1 forces every outer-RAC graph to be planar.
  • Every outer-RAC graph on $n$ vertices has at most $2.5n-4$ edges, and the bound cannot be improved because there are infinitely many outer-apRAC graphs attaining it.
  • Biconnected series-parallel graphs of maximum degree 3 can be drawn outer-apRAC in linear time, and those of maximum degree 4 can be drawn outer-RAC in linear time.
  • Maximum degree alone is not sufficient for outer-RAC: there is a series-parallel graph of maximum degree 5 and a triconnected planar graph of maximum degree 4 that are not outer-RAC.
  • The $2.5n-4$ density bound distinguishes outer-RAC graphs from circular RAC drawings, which have a tight bound of $2n-2$ when all vertices must lie on a circle.

Reading between the lines

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

  • If the proof is right, the outer-RAC model is not a true 'beyond planar' class in the usual topological sense: right-angle crossings add geometric constraints without admitting any non-planar graphs, so future work should focus on which planar graphs admit such drawings.
  • A testable extension is to check whether every extremal outer-RAC graph with exactly $2.5n-4$ edges decomposes into $K_4$ blocks sharing edges, as Theorem 2's tight case suggests, which could lead to a structural characterization of the densest examples.
  • If the outline construction can be made fully rigorous, the same uncrossing idea may generalize to other outer drawing models where each block of crossing edges uses only two perpendicular slopes, potentially transferring the planarity conclusion to those models.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper introduces outer-RAC and outer-apRAC drawings, in which all vertices are incident to the outer cell and all crossings are right-angled, with outer-apRAC additionally requiring all crossing edges to have slopes ±1. The main claim is that every outer-RAC graph is planar (Theorem 1) and has at most 2.5n−4 edges (Theorem 2), with the bound tight even for outer-apRAC graphs via a chain of K4's (Theorem 3). The paper also proves that K2,5 and the octahedral graph are not outer-RAC (Theorems 4 and 5), and gives linear-time algorithms for outer-apRAC drawings of subcubic biconnected series-parallel graphs (Theorem 6) and outer-RAC drawings of subquartic biconnected series-parallel graphs (Theorem 7).

Significance. If the results are correct, the paper establishes a clean structural statement—outer-RAC graphs form a proper subfamily of planar graphs—together with a tight density bound and efficient drawing algorithms for natural bounded-degree series-parallel classes. The algorithmic sections are constructive and detailed, and the explicit lower-bound construction via K4-chains is a strength. However, the central topological claim rests on an unproved geometric lemma about block outlines, and the density proof inherits the same gap. The paper's significance is therefore conditional on repairing that lemma.

major comments (3)
  1. [Section 3, paragraph defining O(B)] The existence of a closed cycle O(B) with the four stated properties is asserted in a single sentence: "there necessarily exists a closed cycle O(B)". The alternating-walk construction that follows is not proved to yield a simple cycle, to contain exactly the edges of B, or even to terminate at v_{i+1}; for blocks whose crossing graph contains a cycle of crossings, self-intersecting or non-enclosing walks are a real possibility. This outline lemma is the foundation of both Theorem 1 and Theorem 2, so it must be stated as a formal lemma and proved.
  2. [Theorem 1] The copy/delete construction assumes that the outer boundary C is a simple cycle through all vertices and that "the interior of C" is well defined. For graphs with cut vertices, the outer face boundary is a closed walk rather than a simple cycle, so copying the interior of C to the outside is undefined. The proof also leaves implicit how edges that belong to no crossing block are treated: after copying, such edges appear twice, and the deletion step only mentions slope sets B1 and B2 of blocks. These points must be addressed explicitly for the planarization argument to be complete.
  3. [Theorem 2 / Appendix A] The density proof in Appendix A inherits the unproved outline machinery. The claim that "we can find a sequence of bounded blocks B0, B1, . . . , Bk" such that each Bi shares a vertex or an edge with the preceding union requires that outlines of distinct blocks are non-crossing and that every block is enclosed by its outline; these are exactly the assertions missing from Section 3. Without a proof of the outline lemma, the decomposition argument and hence the bound m ≤ 2.5n − 4 are not fully justified.
minor comments (5)
  1. [Section 1] In the introduction, "parameterited" should be "parameterized".
  2. [Section 2] In the paragraph on SPQR-trees, "SQPR-tree" should be "SPQR-tree".
  3. [Section 3, Lemma 2] The face-counting argument around Equations (1) and (2) is very dense; a short example illustrating the assignment of triangular faces to a face of length j would significantly improve readability.
  4. [Section 4, Lemma 4] The statement "because T is triangular, it contains no two parallel bounding segments" is cryptic; the intended argument is that a straight segment crossing two different sides of a right triangle cannot cross both at right angles, but this deserves one sentence of explanation.
  5. [Appendix C, Theorem 7] The invariants I.1–I.7 are complex, and the proof that I.3–I.5 are maintained in the S-node boundary cases, especially k = 2, is only sketched; additional detail would help the reader verify the construction.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the theorems are derived from definitions and independent external tools; the unproved outline assertion is a correctness gap, not a circular step.

full rationale

The paper's central claims, Theorem 1 (outer-RAC graphs are planar) and Theorem 2 (edge bound 2.5n-4), are proved by direct geometric construction and counting arguments. The outline O(B) is asserted to exist with properties that are not derived from the desired conclusion; this is a potentially missing lemma, but it is not a case of defining a quantity in terms of the target result or fitting a parameter and calling it a prediction. No equation is shown to equal another by construction, and no fitted input is relabeled as a prediction. The cited external results—outer-1-planar density bounds [8,17,22], the linear-time SPQR-tree construction [31], and the outer-1-planar-to-outer-RAC implication [17]—are independent of the present paper's conclusions. Self-citations such as [2], [3], [27], and [28] appear only for contextual motivation, not as load-bearing support for the main theorems. No uniqueness theorem from prior work by the same authors is invoked to force a choice, and no ansatz is smuggled in via citation. The skeptical observation that the existence and simplicity of block outlines, and the claim that outlines of different blocks do not cross, are unproved is a legitimate correctness risk, but it does not make the derivation circular: the argument does not assume the planarity of G or the density bound it aims to establish. Therefore the appropriate circularity score is 0.

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

No fitted parameters appear. The central claims rest on standard methods (SPQR-trees, Euler and triangulation counting) plus one unproved geometric assertion about block outlines.

assumptions (3)
  • standard math SPQR-tree decomposition of a biconnected graph exists and is computable in linear time.
    Used in Section 5 to decompose series-parallel graphs; cited to Gutwenger and Mutzel [31].
  • domain assumption In a straight-line graph drawing, the outer cell is bounded by a simple closed curve passing through all vertices.
    The paper defines outer-RAC drawings this way; the proofs, such as block outlines and copying interior to exterior, assume this boundary behaves like a Jordan curve.
  • ad hoc to paper Existence of non-crossing block outlines O(B) for every block B of crossing edges in an outer-RAC drawing.
    Asserted in Section 3 before Theorem 1 without proof; it is the key geometric tool for proving planarity. No independent evidence is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Outer-(ap)RAC Graphs." pith.science (2026). https://pith.science/paper/UVARV5Q2

@misc{pith2026241117565,
  author       = {Pith},
  title        = {Pith review of: Outer-(ap)RAC Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UVARV5Q2}},
  note         = {Machine review of arXiv:2411.17565}
}
abstract

An \emph{outer-RAC drawing} of a graph is a straight-line drawing where all vertices are incident to the outer cell and all edge crossings occur at a right angle. If additionally, all crossing edges are either horizontal or vertical, we call the drawing \emph{outer-apRAC} (\emph{ap} for \emph{axis-parallel)}. A graph is outer-(ap)RAC if it admits an outer-(ap)RAC drawing. We investigate the class of outer-(ap)RAC graphs. We show that the outer-RAC graphs are a proper subset of~the planar graphs with at most $2.5n-4$ edges where $n$ is the number of vertices. This density bound is tight, even for outer-apRAC graphs. Moreover, we provide an SPQR-tree based linear-time algorithm which computes an outer-RAC drawing for every given series-parallel graph of maximum degree four. As a complementing result, we present planar graphs of maximum degree four and series-parallel graphs of maximum degree five that are not outer-RAC. Finally, for series-parallel graphs of maximum degree three we show how to compute an outer-apRAC drawing in linear time.

Figures

Figures reproduced from arXiv: 2411.17565 by the authors.

Figure 1
Figure 1. (a) An outer RAC graph with its crossing edges being decomposed into [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Illustrations for the proof of (a) Theorem 3 (b) Lemma 3 and (c) Lemma 4. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. (a) Invariants I.1 and I.2. (b) and (c) initialization of Theorem 6. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: (a - c) Treatment of P-nodes in the algorithm in the proof of Theorem 6. (d) Treatment of S-nodes in the algorithm in the proof of Theorem 6. R(µ) is well defined. Further, I.2 guarantees that there is no overlap between different parts of the drawing, as the skeleton …
Figure 5
Figure 5. Figure 5: (a) Graph L9 ∈ L. (b) Outer-RAC drawing of L9. (c) Drawing of a 9-cycle as described in the proof of Theorem 8. (d) Outer-apRAC drawing of L9. (e) An outer-apRAC SP-graph with maximum degree 6. On the other hand, if we require an outer-apRAC drawing, σk may be non￾plan…
Figure 6
Figure 6. Figure 6: (a) Illustration for R(µ) in Theorem 7. (b) For child node ν, we have R(ν) ⊂ R(µ). C Outer-RAC Drawings of Subquartic SP-Graphs Theorem 7. Let G be a biconnected SP-graph with maximum degree 4. An outer-RAC drawing of G can be computed in O(n) time. Proof. Let G be a s…
Figure 7
Figure 7. Figure 7: Illustration for E(µ) in the case where E(µ) is (a) triangle-shaped and (b) trapezoid-shaped. (a) also shows I.3 and I.4 and (b) shows I.5. requirements on the slopes of rs(µ) and rt(µ) or on H1(µ) and H2(µ) aside from the fact that R(µ) must contain a segment of the b…
Figure 8
Figure 8. Figure 8: Initialization of the algorithm of Theorem 7. [PITH_FULL_IMAGE:figures/full_fig_p023_8.png]
Figure 9
Figure 9. Figure 9: Treatment of P-nodes in the algorithm in the proof of Theorem 7. µ. Further, let es = (sµ, s′ µ ) and et = (tµ, t′ µ ) be the edges in skel(ν1) incident to the vertices coinciding with the poles of µ. We partially draw skel(ν1), by placing s ′ µ and t ′ µ . Then, we re…
Figure 10
Figure 10. Figure 10: Treatment of S-nodes in the algorithm in the proof of Theorem 7. tµ (a) sµ sπ (b) sµ tµ E(µ) sπ tπ (c) [PITH_FULL_IMAGE:figures/full_fig_p025_10.png]
Figure 11
Figure 11. Figure 11: Treatment of S-nodes in the algorithm in the proof of Theorem 7. µ is a P-node with three S-node children. Let ν1, ν2, ν3 be the three S-node children of µ. Since G is subquartic, all virtual edges in skel(ν1), skel(ν2) and skel(ν3) which are incident to the poles of …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 31 canonical work pages

  1. [1]

    Angelini, P., Bekos, M.A., F¨ orster, H., Kaufmann, M.: On RAC draw- ings of graphs with one bend per edge. Theor. Comput. Sci. 828-829, 42– 54 (2020). https://doi.org/10.1016/J.TCS.2020.04.018, https://doi.org/10. 1016/j.tcs.2020.04.018

    work page doi:10.1016/j.tcs.2020.04.018 2020

  2. [2]

    In: Szeider, S., Ganian, R., Silva, A

    Angelini, P., Bekos, M.A., Katheder, J., Kaufmann, M., Pfister, M.: RAC draw- ings of graphs with low degree. In: Szeider, S., Ganian, R., Silva, A. (eds.) 47th Int. Symp. on Mathematical Foundations of Computer Science, MFCS 2022. LIPIcs, vol. 241, pp. 11:1–11:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur In- formatik (2022). https://doi.org/10.4230/LIPIC...

    work page doi:10.4230/lipics.mfcs.2022.11 2022

  3. [3]

    In: Gørtz, I.L., Farach-Colton, M., Puglisi, S.J., Herman, G

    Angelini, P., Bekos, M.A., Katheder, J., Kaufmann, M., Pfister, M., Ueckerdt, T.: Axis-parallel right angle crossing graphs. In: Gørtz, I.L., Farach-Colton, M., Puglisi, S.J., Herman, G. (eds.) 31st Annual European Symposium on Algorithms, ESA 2023. LIPIcs, vol. 274, pp. 9:1–9:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik (2023). https://doi.org...

    work page doi:10.4230/lipics.esa.2023.9 2023

  4. [4]

    IEEE Trans

    Angori, L., Didimo, W., Montecchiani, F., Pagliuca, D., Tappini, A.: Hybrid graph visualizations with chordlink: Algorithms, experiments, and applications. IEEE Trans. Vis. Comput. Graph. 28(2), 1288–1300 (2022). https://doi.org/10.1109/ TVCG.2020.3016055, https://doi.org/10.1109/TVCG.2020.3016055

    arXiv 2022

  5. [5]

    Argyriou, E.N., Bekos, M.A., Kaufmann, M., Symvonis, A.: Geometric RAC si- multaneous drawings of graphs. J. Graph Algorithms Appl. 17(1), 11–34 (2013). https://doi.org/10.7155/JGAA.00282, https://doi.org/10.7155/jgaa.00282

    doi:10.7155/jgaa.00282 2013

  6. [6]

    Argyriou, E.N., Bekos, M.A., Symvonis, A.: The straight-line RAC drawing problem is NP-hard. J. Graph Algorithms Appl. 16(2), 569–597 (2012). https://doi.org/ 10.7155/JGAA.00274, https://doi.org/10.7155/jgaa.00274

    work page doi:10.7155/jgaa.00274 2012

  7. [7]

    Arikushi, K., Fulek, R., Keszegh, B., Moric, F., T´ oth, C.D.: Graphs that admit right angle crossing drawings. Comput. Geom. 45(4), 169–177 (2012). https:// doi.org/10.1016/J.COMGEO.2011.11.008, https://doi.org/10.1016/j.comgeo. 2011.11.008

    work page doi:10.1016/j.comgeo.2011.11.008 2012

  8. [8]

    Algorithmica 74(4), 1293– 1320 (2016)

    Auer, C., Bachmaier, C., Brandenburg, F.J., Gleißner, A., Hanauer, K., Neuwirth, D., Reislhuber, J.: Outer 1-planar graphs. Algorithmica 74(4), 1293– 1320 (2016). https://doi.org/10.1007/S00453-015-0002-1 , https://doi.org/ 10.1007/s00453-015-0002-1

    doi:10.1007/s00453-015-0002-1 2016

Show all 51 references
  1. [9]

    Algorithmica 79(2), 401– 427 (2017)

    Bekos, M.A., Cornelsen, S., Grilli, L., Hong, S., Kaufmann, M.: On the recogni- tion of fan-planar and maximal outer-fan-planar graphs. Algorithmica 79(2), 401– 427 (2017). https://doi.org/10.1007/S00453-016-0200-5 , https://doi.org/ 10.1007/s00453-016-0200-5

    2017 doi

  2. [10]

    Bekos, M.A., Didimo, W., Liotta, G., Mehrabi, S., Montecchiani, F.: On RAC draw- ings of 1-planar graphs. Theor. Comput. Sci. 689, 48–57 (2017). https://doi.org/ 10.1016/J.TCS.2017.05.039, https://doi.org/10.1016/j.tcs.2017.05.039

    2017 doi

  3. [11]

    Bekos, M.A., van Dijk, T.C., Kindermann, P., Wolff, A.: Simultaneous drawing of planar graphs with right-angle crossings and few bends. J. Graph Algorithms Appl. 20(1), 133–158 (2016). https://doi.org/10.7155/JGAA.00388, https:// doi.org/10.7155/jgaa.00388

    2016 doi

  4. [12]

    Biedl, T.: Drawing outer-1-planar graphs revisited. J. Graph Algorithms Appl. 26(1), 59–73 (2022). https://doi.org/10.7155/JGAA.00581, https://doi.org/ 10.7155/jgaa.00581 14 H. F¨ orster, J. Katheder, G. Ortali

    2022 doi

  5. [13]

    Binucci, C., Di Giacomo, E., Didimo, W., Montecchiani, F., Patrignani, M., Symvonis, A., Tollis, I.G.: Fan-planarity: Properties and complexity. Theor. Comput. Sci. 589, 76–86 (2015). https://doi.org/10.1016/J.TCS.2015.04.020, https://doi.org/10.1016/j.tcs.2015.04.020

    2015 doi

  6. [14]

    In: Bekos, M.A., Chimani, M

    Brand, C., Ganian, R., R¨ oder, S., Schager, F.: Fixed-parameter algorithms for computing RAC drawings of graphs. In: Bekos, M.A., Chimani, M. (eds.) 31st Int. Symp. on Graph Drawing and Network Visualization, GD 2023. Lecture Notes in Computer Science, vol. 14466, pp. 66–81. ...

    2023 doi

  7. [15]

    In: Albers, S

    Chaplick, S., F¨ orster, H., Kryven, M., Wolff, A.: Drawing graphs with circular arcs and right-angle crossings. In: Albers, S. (ed.) 17th Scandinavian Symposium and Workshops on Algorithm Theory, SW AT 2020. LIPIcs, vol. 162, pp. 21:1–21:14. Schloss Dagstuhl - Leibniz-Zentrum...

    2020 doi

  8. [16]

    Chaplick, S., Lipp, F., Wolff, A., Zink, J.: Compact drawings of 1-planar graphs with right-angle crossings and few bends. Comput. Geom. 84, 50–68 (2019). https://doi.org/10.1016/J.COMGEO.2019.07.006, https://doi.org/10. 1016/j.comgeo.2019.07.006

    2019 doi

  9. [17]

    Dehkordi, H.R., Eades, P.: Every outer-1-plane graph has a right angle crossing drawing. Int. J. Comput. Geom. Appl. 22(6), 543–558 (2012). https://doi.org/ 10.1142/S021819591250015X, https://doi.org/10.1142/S021819591250015X

    2012 doi

  10. [18]

    Dehkordi, H.R., Eades, P., Hong, S., Nguyen, Q.H.: Circular right-angle crossing drawings in linear time. Theor. Comput. Sci. 639, 26–41 (2016). https://doi.org/ 10.1016/J.TCS.2016.05.017, https://doi.org/10.1016/j.tcs.2016.05.017

    2016 doi

  11. [19]

    Algorithmica 15(4), 302–318 (1996)

    Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302–318 (1996). https://doi.org/10.1007/ BF01961541, https://doi.org/10.1007/BF01961541

    1996 doi

  12. [20]

    Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956–997 (1996). https://doi.org/10.1137/S0097539794280736, https: //doi.org/10.1137/S0097539794280736

    1996 doi

  13. [21]

    Algorithmica 68(4), 954–997 (2014)

    Di Giacomo, E., Didimo, W., Eades, P., Liotta, G.: 2-layer right angle cross- ing drawings. Algorithmica 68(4), 954–997 (2014). https://doi.org/10.1007/ S00453-012-9706-7 , https://doi.org/10.1007/s00453-012-9706-7

    2014 doi

  14. [22]

    Didimo, W.: Density of straight-line 1-planar graph drawings. Inf. Process. Lett. 113(7), 236–240 (2013). https://doi.org/10.1016/J.IPL.2013.01.013, https: //doi.org/10.1016/j.ipl.2013.01.013

    2013 doi

  15. [23]

    Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theor. Comput. Sci. 412(39), 5156–5166 (2011). https://doi.org/10.1016/J.TCS.2011. 05.025, https://doi.org/10.1016/j.tcs.2011.05.025

    2011 doi

  16. [24]

    ACM Comput

    Didimo, W., Liotta, G., Montecchiani, F.: A survey on graph drawing beyond planarity. ACM Comput. Surv. 52(1), 4:1–4:37 (2019). https://doi.org/10.1145/ 3301281, https://doi.org/10.1145/3301281

    2019 doi

  17. [25]

    Diestel, R.: Graph Theory, 5th Edition, Graduate texts in mathematics, vol. 173. Springer (2012)

    2012

  18. [26]

    Eppstein, D.: Parallel recognition of series-parallel graphs. Inf. Comput. 98(1), 41– 55 (1992). https://doi.org/10.1016/0890-5401(92)90041-D , https://doi.org/ 10.1016/0890-5401(92)90041-D

    1992 doi

  19. [27]

    F¨ orster, H., Ganian, R., Klute, F., N¨ ollenburg, M.: On strict (outer-)confluent graphs. J. Graph Algorithms Appl. 25(1), 481–512 (2021). https://doi.org/10. 7155/JGAA.00568, https://doi.org/10.7155/jgaa.00568 Outer-(ap)RAC Graphs 15

    2021 doi

  20. [28]

    In: Grandoni, F., Herman, G., Sanders, P

    F¨ orster, H., Kaufmann, M.: On compact RAC drawings. In: Grandoni, F., Herman, G., Sanders, P. (eds.) 28th Annual European Symposium on Algorithms, ESA

  21. [29]

    Physics Reports 486(3), 75–174 (2010)

    Fortunato, S.: Community detection in graphs. Physics Reports 486(3), 75–174 (2010). https://doi.org/https://doi.org/10.1016/j.physrep.2009.11.002, https://www.sciencedirect.com/science/article/pii/S0370157309002841

    2010 doi

  22. [30]

    Proceedings of the National Academy of Sciences 99(12), 7821–7826 (2002)

    Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99(12), 7821–7826 (2002). https: //doi.org/10.1073/pnas.122653799, https://www.pnas.org/doi/abs/10.1073/ pnas.122653799

    2002 doi

  23. [31]

    In: Marks, J

    Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Marks, J. (ed.) 8th Int. Symp. on Graph Drawing, GD 2000. Lecture Notes in Com- puter Science, vol. 1984, pp. 77–90. Springer (2000). https://doi.org/10.1007/ 3-540-44541-2_8 , https://doi.org/10.1007/3...

    2000 doi

  24. [32]

    IEEE Trans

    Henry, N., Fekete, J., McGuffin, M.J.: Nodetrix: a hybrid visualization of social networks. IEEE Trans. Vis. Comput. Graph.13(6), 1302–1309 (2007). https://doi. org/10.1109/TVCG.2007.70582, https://doi.org/10.1109/TVCG.2007.70582

    2007

  25. [33]

    Algorithmica 72(4), 1033– 1054 (2015)

    Hong, S., Eades, P., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear-time algorithm for testing outer-1-planarity. Algorithmica 72(4), 1033– 1054 (2015). https://doi.org/10.1007/S00453-014-9890-8 , https://doi.org/ 10.1007/s00453-014-9890-8

    2015 doi

  26. [34]

    In: Mayr, E.W

    Hong, S., Nagamochi, H.: Testing full outer-2-planarity in linear time. In: Mayr, E.W. (ed.) 41st Int. Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015. Lecture Notes in Computer Science, vol. 9224, pp. 406–421. Springer (2015). https://doi.org/10.1007/978-3-6...

    2015 doi

  27. [35]

    (eds.): Beyond Planar Graphs, Communica- tions of NII Shonan Meetings

    Hong, S., Tokuyama, T. (eds.): Beyond Planar Graphs, Communica- tions of NII Shonan Meetings. Springer (2020). https://doi.org/10.1007/ 978-981-15-6533-5 , https://doi.org/10.1007/978-981-15-6533-5

    2020 doi

  28. [36]

    In: Hong, S., Ma, K

    Huang, W.: Using eye tracking to investigate graph layout effects. In: Hong, S., Ma, K. (eds.) APVIS 2007, 6th International Asia-Pacific Symposium on Visualization

    2007

  29. [37]

    Huang, W., Eades, P., Hong, S.: Larger crossing angles make graphs easier to read. J. Vis. Lang. Comput. 25(4), 452–465 (2014). https://doi.org/10.1016/J.JVLC. 2014.03.001, https://doi.org/10.1016/j.jvlc.2014.03.001

    2014 doi

  30. [38]

    In: IEEE VGTC Pacific Visualization Symposium 2008, PacificVis 2008

    Huang, W., Hong, S., Eades, P.: Effects of crossing angles. In: IEEE VGTC Pacific Visualization Symposium 2008, PacificVis 2008. pp. 41–46. IEEE Computer Society (2008). https://doi.org/10.1109/PACIFICVIS.2008.4475457, https://doi.org/ 10.1109/PACIFICVIS.2008.4475457

    2008

  31. [39]

    CoRR abs/2311.06193 (2023)

    Kaufmann, M., Klemz, B., Knorr, K., Reddy, M.M., Schr¨ oder, F., Ueck- erdt, T.: The density formula: One lemma to bound them all. CoRR abs/2311.06193 (2023). https://doi.org/10.48550/ARXIV.2311.06193, https: //doi.org/10.48550/arXiv.2311.06193

    2023 doi arXiv

  32. [40]

    Interact

    Purchase, H.C.: Effective information visualisation: a study of graph drawing aesthetics and algorithms. Interact. Comput. 13(2), 147–162 (2000). https://doi.org/10.1016/S0953-5438(00)00032-1 , https://doi.org/ 10.1016/S0953-5438(00)00032-1 16 H. F¨ orster, J. Katheder, G. Ortali

    2000 doi

  33. [41]

    Rahmati, Z., Emami, F.: RAC drawings in subcubic area. Inf. Process. Lett. 159-160, 105945 (2020). https://doi.org/10.1016/J.IPL.2020.105945, https: //doi.org/10.1016/j.ipl.2020.105945

    2020

  34. [42]

    Schaefer, M.: RAC-drawability is ∃R-complete and related results. J. Graph Al- gorithms Appl. 27(9), 803–841 (2023). https://doi.org/10.7155/JGAA.00646, https://doi.org/10.7155/jgaa.00646

    2023 doi

  35. [43]

    (ed.): Handbook on Graph Drawing and Visualiza- tion

    Tamassia, R. (ed.): Handbook on Graph Drawing and Visualiza- tion. Chapman and Hall/CRC (2013), https://www.crcpress.com/ Handbook-of-Graph-Drawing-and-Visualization/Tamassia/9781584884125

    2013

  36. [44]

    In: Bekos, M.A., Chimani, M

    T´ oth, C.D.: On RAC drawings of graphs with two bends per edge. In: Bekos, M.A., Chimani, M. (eds.) 31st Int. Symp. on Graph Drawing and Network Visualization, GD 2023. Lecture Notes in Computer Science, vol. 14465, pp. 69–77. Springer (2023). https://doi.org/10.1007/978-3-03...

    2023 doi

  37. [47]

    If Bi is degenerate, it shares a single vertex with Gi−1, m′ i = 1 = n′ i < 2n′ i + 1

  38. [48]

    If Bi is trivial and shares a single vertex with Gi−1, m′ i = 3 = 3 2 n′ i < 2n′ i + 1

  39. [49]

    If Bi is trivial and shares a single edge with Gi−1, m′ i = 2 = 2n′ i < 2n′ i + 1. 18 H. F¨ orster, J. Katheder, G. Ortali

  40. [50]

    If Bi is proper and shares a single vertex with Gi−1, m′ i ≤ 2(n′ i + 1) − 2 = 2n′ i < 2n′ i + 1

  41. [51]

    Let kp denote the number of times we insert a proper block and let kt denote the number of times we insert a trivial or degenerate block

    If Bi is proper and shares a single edge with Gi−1, m′ i ≤ 2(n′ i +2) −3 = 2n′ i +1. Let kp denote the number of times we insert a proper block and let kt denote the number of times we insert a trivial or degenerate block. Let np i and mp i denote the number of vertices and ed...

  42. [2007]

    pp. 97–100. IEEE Computer Society (2007). https://doi.org/10.1109/ APVIS.2007.329282, https://doi.org/10.1109/APVIS.2007.329282

    2007

  43. [2020]

    LIPIcs, vol. 173, pp. 53:1–53:21. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik (2020). https://doi.org/10.4230/LIPICS.ESA.2020.53, https://doi. org/10.4230/LIPIcs.ESA.2020.53

    2020 doi

Pith tools

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