Pith. sign in

REVIEW 4 major objections 6 minor 47 references

Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity

T0 review · 4 major / 6 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 The paper establishes exact if-and-only-if characterizations for complete and complete bipartite graphs in beyond-planarity classes by exhaustively generating all non-isomorphic topological drawings.

desk verdict A genuinely useful enumeration technique with several new tight bounds, but the negative results are computational claims that need certificates or a pinned implementation before they can be taken as theorems. read the letter →

arxiv 1908.03042 v2 pith:HW64PC7K submitted 2019-08-08 cs.DS cs.DMmath.CO

Patrizio Angelini , Michael A. Bekos , Michael Kaufmann , Thomas Schneck This is my paper · ORCID
classification cs.DScs.DMmath.CO MSC 05C1005C6268R10
keywords beyond-planaritytopologicalgraphdrawingk-planargraphsfan-planargap-planarquasiplanarcompletebipartiteenumeration
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

The paper confronts the question of which complete and complete bipartite graphs admit drawings that respect given beyond-planarity restrictions, such as every edge being crossed at most $k$ times, or no edge crossing two adjacent edges. Standard density arguments stop short at graphs like $K_8$ for 2-planarity or $K_{4,6}$ for 3-planarity, so the paper replaces combinatorics with a systematic enumeration: add one vertex at a time, insert its incident edges through every allowed pathway through the crossing structure, and discard drawings that are isomorphic to ones already seen. The headline result is an if-and-only-if statement: for a complete or complete bipartite input, the graph lies in the class exactly when the algorithm produces a valid drawing. Running this procedure yields tight cutoffs—for instance, $K_{a,b}$ with $a\le b$ is 2-planar exactly for $a\le 2$, or $a=3$ and $b\le 10$, or $a=4$ and $b\le 6$—and settles several open cases such as $K_8$ not being 2-planar and $K_{5,5}$ not being fan-planar.

What carries the argument

The mechanism is the half-pathway. In the planarization of a drawing, a half-pathway for a vertex $u$ is a path in the dual graph starting at a face incident to $u$ and ending at a destination face; inserting a new vertex $v$ there and drawing edge $(u,v)$ along that path crosses exactly the edges dual to the pathway. A pathway is the same but with the destination a face incident to an existing vertex, so it inserts an edge between two present vertices. The generation procedure builds every drawing by adding vertices one at a time, computing all valid half-pathways for the first new edge and all valid pathways for the remaining incident edges, while a prohibited-edges list keeps the drawing simple and within the class's crossing constraints. At each level it tests isomorphism via a face-boundary-walking bijection and deletes duplicates; this symmetry reduction is what makes exhaustive enumeration feasible.

What would settle it

Find, by independent exhaustive enumeration or by construction, a simple 2-planar drawing of $K_{4,7}$ or $K_{5,5}$, a fan-planar drawing of $K_{5,5}$, or a 2-planar drawing of $K_8$; any one of these would refute the corresponding characterization, as would a single non-simple drawing of $K_{4,7}$ satisfying 2-planarity.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that for complete and complete bipartite graphs, all topological representations belonging to a beyond-planarity class can be generated, up to isomorphism, by a vertex-by-vertex search. Each insertion is routed through valid half-pathways or pathways in the planarization of the current drawing; the search is pruned by maintaining forbidden crossing lists and by testing isomorphism at every step. Theorem 1 states that this generation is complete: for any such graph $G$ and any beyond-planarity class $C$ of topological graphs, $G$ belongs to $C$ if and only if the algorithm returns a valid drawing. The proof-of-concept applications give new tight characterizations, including that $K_8$ is not 2-planar, $K_9$ is not 3-planar, $K_{a,b}$ with $a\le b$ is 3-planar if and only if $a\le 2$, or $a=3$ and $b\le 14$, or $a=4$ and $b\le 9$, or $a=5$ and $b\le 6$, and $K_{5,5}$ is not fan-planar. The paper also provides a combinatorial proof that $K_{a,b}$ is fan-crossing free if and only if $a\le 2$ or ($a\le 4$ and $b\le 6$).

Load-bearing premise

The load-bearing premise is that restricting to simple drawings is without loss of generality for every class considered and that the unverified implementation exhaustively enumerates every simple drawing; if a non-simple drawing belongs to a class, or the search misses one, the if-and-only-if characterizations collapse.

Editorial extensions

If this is right

  • The characterization of 2-planar complete bipartite graphs is now tight: $K_{a,b}$ is 2-planar exactly for $a\le 2$, or $a=3$ and $b\le 10$, or $a=4$ and $b\le 6$, so $K_{4,7}$ and $K_{5,5}$ are not 2-planar.
  • $K_{5,5}$ is not fan-planar, settling the conjecture that it is not, and since $K_{5,5}$ is gap-planar while $K_{4,9}$ is fan-planar but not gap-planar, the gap-planar and fan-planar classes are incomparable.
  • $K_8$ is not 2-planar and $K_9$ is not 3-planar, so the chromatic number of 3-planar graphs is lower bounded by 8, with analogous lower bounds following for higher values of $k$.
  • The fan-crossing-free complete bipartite characterization is proven both combinatorially and by the implementation: $K_{a,b}$ is fan-crossing free if and only if $a\le 2$ or $a\le 4$ and $b\le 6$.
  • For 4-planar and quasiplanar complete bipartite graphs, full enumeration becomes infeasible—$K_{4,4}$ alone already has tens of thousands of non-isomorphic drawings—so the paper reports only positive certificates obtained with a depth-first variant.

Reading between the lines

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

  • Beyond the paper, the same half-pathway enumeration should apply to any topological class whose forbidden configurations are local crossing constraints expressible on a planarization, so one could read off analogous cutoffs for other classes such as $k$-fan-bundle or crossing-angle constrained drawings.
  • The completeness of the enumeration is only as strong as the simple-drawing restriction; if a class's standard definition permits non-simple drawings, the paper's if-and-only-if characterizations may describe a stricter class, and the search would need to be rerun without that restriction.
  • The reported drawing counts, such as the 35 non-isomorphic 4-planar drawings of $K_9$, could serve as data for studying the typical crossing structure of extremal drawings or for testing conjectures about rotation systems of complete bipartite graphs.
  • A direct testable extension is to run the depth-first variant further on $K_{4,5}$ for the 4-planar and quasiplanar cases: a found certifying drawing would extend the paper's partial positive observations, while a proof of nonexistence would complete those characterizations.
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.

Referee Report

4 major / 6 minor

Summary. The paper proposes a generation technique for enumerating simple topological drawings of complete and complete bipartite graphs that satisfy beyond-planarity restrictions. The algorithm builds drawings vertex by vertex, using half-pathways in the planarization to insert edges and an isomorphism filter based on two sufficient conditions (P.1 and P.2). The authors apply the implementation to several classes and report new tight characterizations, including the claims that K8 is not 2-planar, K4,7 and K5,5 are not 2-planar, K4,10, K5,7 and K6,6 are not 3-planar, K5,5 is not fan-planar, and K4,9 is not gap-planar. For the fan-crossing free class, Appendix E contains a detailed human-checkable combinatorial proof of the characterization of complete bipartite graphs. The paper also reports drawing counts and execution times in Appendix D and makes the Java implementation publicly available.

Significance. If the reported characterizations are correct, the paper settles several open bounds for beyond-planarity classes and provides a new computational tool for generating topological representations. The positive certificates (e.g., 3-planar drawings of K4,9 and K5,6, the 4-planar drawings, and the quasiplanar examples) are concrete and useful. The combinatorial proof in Appendix E for the fan-crossing free case is careful and checkable, and the fact that the implementation reproduces known entries such as K6 being 1-planar and K8 being gap-planar is reassuring. However, most of the advertised new results are negative statements that currently rest on the correctness and exhaustiveness of an unverified implementation, and the paper explicitly restricts to simple drawings without proving this is without loss of generality.

major comments (4)
  1. [Section 4, Table 1, Characterizations 2-7 and Observation 11] The central new results are negative memberhips: e.g., "K8 is not 2-planar" (Characterization 2), "K4,7 and K5,5 are not 2-planar" (Characterization 3), "K4,10, K5,7 and K6,6 are not 3-planar" (Characterization 4), "K5,5 is not fan-planar" (Characterization 7), and "K4,9 is not gap-planar" (Observation 11). In every case the evidence is that the Java implementation in Appendix D failed to find a drawing. Since the implementation is not formally verified and no machine-checkable unsatisfiability certificate is provided, these are computational experiments rather than mathematical theorems. The paper should either supply independent proofs/certificates for each negative entry or explicitly restate these items as computational evidence, separate from the proven characterizations.
  2. [Section 2, Preliminaries] The paper restricts all drawings to simple drawings and states "this assumption is not without loss of generality [3]." This is load-bearing because the stated if-and-only-if characterizations, such as "Ka,b is 3-planar if and only if ..." are claims about the standard beyond-planarity classes. If those classes admit non-simple drawings, the generated set may miss valid drawings and the negative results may be false. The authors must either prove that for complete and complete bipartite graphs the beyond-planarity classes considered here can be witnessed by simple drawings, or qualify every characterization and theorem as applying only to simple drawings.
  3. [Section 3, Theorem 1] Theorem 1 is the formal justification that the algorithm is exhaustive, but no proof is given; the text only says "We summarize the above discussion in the following theorem." A rigorous proof is needed that every valid simple drawing can be obtained by the vertex-by-vertex construction, that the half-pathway rules and prohibited-edge conditions exactly characterize validity for each class C, and that the isomorphism filtering does not discard a representative needed to reach a drawing of G. Without this proof, the "only if" direction of Theorem 1 is an assertion rather than a mathematical statement.
  4. [Section 3, Isomorphism testing] The isomorphism test uses Properties P.1 and P.2, which the authors state are sufficient but not known to be necessary. Consequently, the algorithm may retain isomorphic copies, so the claim that it generates "all non-isomorphic simple drawings" and the "Non-Iso" counts in Tables 2 and 3 are not established. This does not directly invalidate the existence/non-existence characterizations, because retaining extra isomorphic drawings cannot create false negative results, but it is a gap for the enumeration contribution and for any reader who uses the reported counts.
minor comments (6)
  1. [Section 3, Isomorphism testing] In the paragraph describing the recursive face mapping, "faces incident to e1 end e2" appears to be a typo for "e'1 and e'2".
  2. [Appendix G, case for Gamma_6] The sentence "we can directly conclude that the drawing Gamma5 cannot be a subdrawing ..." should refer to Gamma6, not Gamma5.
  3. [Appendix G, Figure 30 discussion] The phrase "the edge (u2,w6) must be crossing-freee" contains a typo: "freee" should be "free".
  4. [Appendix D] For reproducibility, the paper should pin the exact commit hash of the GitHub repository and state the Java version and any non-standard dependencies; the current reference is only to a repository URL.
  5. [Section 4, Observations 5 and 13] The "DFS-like variant" of the algorithm is not described in Section 3; a precise description is needed for reproducibility, even though these observations are only positive certificates.
  6. [Table 1] Some cell formatting is confusing, e.g., the 2-planar complete bipartite row lists "K4,5 K5,5 Char.3 [34]" in a way that mixes membership, non-membership, and references; this should be split into clearly labeled entries.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the enumeration is self-contained and the new characterizations are outputs of an exhaustive search, not fitted predictions.

full rationale

The paper's central mechanism is an exhaustive search over half-pathways in planarizations, with no fitted parameters and no quantity defined in terms of the target characterizations. Theorem 1 asserts the search's completeness; although the completeness proof is informal and the negative results ultimately rest on a non-formally-verified Java implementation, that is a verification/correctness limitation, not circularity. The isomorphism test uses only sufficient conditions, so it cannot discard a genuinely valid drawing (it can only retain duplicates), which means the negative outputs are not biased by the test's incompleteness. The only same-author citations ([6] for K3,b k-planarity and [7] for the fan-planar conjecture) are independent published theorems/conjectures used as inputs, not used to force the new a≥4 or complete-graph results. The admitted restriction to simple drawings and the absence of machine-checked certificates are important limitations, but they do not make the derivation equivalent to its own inputs.

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

The paper introduces no free parameters or new entities. Its results rest on the standard combinatorial framework of simple topological drawings, the completeness of the half-pathway search, and several cited results from the beyond-planarity literature.

assumptions (3)
  • domain assumption All drawings considered are simple: no self-crossing edges, two edges cross at most once, and adjacent edges do not cross (Section 2).
    The authors acknowledge this is not without loss of generality [3]; the characterizations therefore apply to simple drawings only, which may not match classes defined without this restriction.
  • domain assumption Every possible placement of a new vertex and its incident edges corresponds to a valid half-pathway or pathway in the planarization (Section 3).
    This is standard in topological graph theory but is an unproved assumption about completeness of the search; the proof of Theorem 1 rests on it.
  • domain assumption Known results are taken as black boxes, e.g., K3,b is k-planar if and only if b is at most 4k+2 (Angelini et al. [6]) and edge-density bounds for fan-planar bipartite graphs (Angelini et al. [7]).
    These are cited, not proven, and some were authored by the present team; if any are wrong, the derived bounds shift.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity." pith.science (2026). https://pith.science/paper/HW64PC7K

@misc{pith2026190803042,
  author       = {Pith},
  title        = {Pith review of: Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HW64PC7K}},
  note         = {Machine review of arXiv:1908.03042}
}
read the original abstract

Beyond-planarity focuses on combinatorial properties of classes of non-planar graphs that allow for representations satisfying certain local geometric or topological constraints on their edge crossings. Beside the study of a specific graph class for its maximum edge density, another parameter that is often considered in the literature is the size of the largest complete or complete bipartite graph belonging to it. Overcoming the limitations of standard combinatorial arguments, we present a technique to systematically generate all non-isomorphic topological representations of complete and complete bipartite graphs, taking into account the constraints of the specific class. As a proof of concept, we apply our technique to various beyond-planarity classes and achieve new tight bounds for the aforementioned parameter.

Figures

Figures reproduced from arXiv: 1908.03042 by the authors.

Figure 1
Figure 1. Different forbidden crossing configurations in: (a) 1-planar, (b) 3-quasiplanar, [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. The prohibited edges (blue solid) for a half-pathway (red dashed) that ends in [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Illustration of (a) a 3-planar drawing of [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (31 more)
Figure 4
Figure 4. Figure 4: Illustration of 4-planar drawings of (a) [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: Different drawings of K5: The drawing of (a) is isomorphic neither to the one of (b) nor to the one of (c), while the drawings of (b) and (c) are in fact isomorphic; the colors of the vertices and the gray labels show the vertex and facial correspondences [PITH_FULL_I…
Figure 6
Figure 6. Figure 6: Illustration of a running example. C Omitted Drawings from Section 4 In this section, we provide drawings certifying that certain complete and com￾plete bipartite graphs belongs to specific beyond-planarity graph classes, which were omitted from Section 4 due to space …
Figure 7
Figure 7. Figure 7: A quasiplanar drawing of K5,18. (a) (b) [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]
Figure 8
Figure 8. Figure 8: Illustration of quasiplanar drawings of (a) [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]
Figure 9
Figure 9. Figure 9: If (u2, w1) crosses (u1, w2) and (u1, w1) crosses (u2, w2), then there exists also a fan-crossing [PITH_FULL_IMAGE:figures/full_fig_p023_9.png]
Figure 10
Figure 10. Figure 10: (a) The only drawing of G in which (u1, w2) and (u2, w1) cross each other. (b) Vertex w3 in region R1. Edges (u1, w3) and (u2, w3) (red edges) are crossing-free. (c) Vertex w3 in region R2. Edge (u1, w3) is crossing-free; edge (u2, w3) crosses (u1, w1). – Fig.11a and …
Figure 11
Figure 11. Figure 11: All the cases that preserve the fan-crossing free property, when adding a third [PITH_FULL_IMAGE:figures/full_fig_p025_11.png]
Figure 12
Figure 12. Figure 12: All (topologically distinct) cases that preserve the fan-crossing free property, [PITH_FULL_IMAGE:figures/full_fig_p026_12.png]
Figure 13
Figure 13. Figure 13: (a)–(g) The cases that preserve the fan-crossing free property, when adding a [PITH_FULL_IMAGE:figures/full_fig_p026_13.png]
Figure 14
Figure 14. Figure 14: All (topologically different) cases that preserve the fan-crossing free property, [PITH_FULL_IMAGE:figures/full_fig_p027_14.png]
Figure 15
Figure 15. Figure 15: All drawings that preserve the fan-crossing free property, when adding a fifth [PITH_FULL_IMAGE:figures/full_fig_p028_15.png]
Figure 16
Figure 16. Figure 16: All drawings that preserve the fan-crossing free property, when adding a fifth [PITH_FULL_IMAGE:figures/full_fig_p029_16.png]
Figure 17
Figure 17. Figure 17: All drawings that preserve the fan-crossing free property, when adding a fifth [PITH_FULL_IMAGE:figures/full_fig_p029_17.png]
Figure 18
Figure 18. Figure 18: All drawings that preserve the fan-crossing free property, when adding a fifth [PITH_FULL_IMAGE:figures/full_fig_p030_18.png]
Figure 19
Figure 19. Figure 19: All topologically different drawings of the subgraph [PITH_FULL_IMAGE:figures/full_fig_p030_19.png]
Figure 20
Figure 20. Figure 20: Three observations for placing vertices from the set [PITH_FULL_IMAGE:figures/full_fig_p030_20.png]
Figure 21
Figure 21. Figure 21: The regions in Γ1. The dashed red line represents the edge (u3, w3). edges incident to u1 or at least two edges incident to u2 – a fan-crossing. Also, it cannot cross the edge (u1, w5), as this would also create a fan-crossing. The only option left is to cross the edg…
Figure 22
Figure 22. Figure 22: (a) The regions in Γ2. (b) Node u3 is placed in region R1 and the edge (u3, w3) (dashed red) crosses (u1, w5) and (u2, w4). The dashed dotted blue lines show the edge (u3, w4) that cannot be drawn fan-crossing free in this setting [PITH_FULL_IMAGE:figures/full_fig_p0…
Figure 23
Figure 23. Figure 23: The regions in Γ3. The dashed dotted blue lines indicate the two edges (u3, w4) and (u3, w5) that are not drawable without fan-crossings when adding vertex u3 in R2. u1 u2 w1 w5 w2 R1 R2 R3 w4 w3 R4 R5 R6 R7 [PITH_FULL_IMAGE:figures/full_fig_p033_23.png]
Figure 24
Figure 24. Figure 24: The regions in Γ4. cannot lie in R6, since the edge connecting one of them to w1 would cross both edges (u1, w4) and (u1, w5) (Lemma 3); (iii) vertices u3, u4, u5 cannot lie in R7, since the edges connecting one of them to w1 and w2 would both cross (u1, w3) (Lemma 3)…
Figure 25
Figure 25. Figure 25: The regions in Γ5. and w5 would cross (u1, w3) and (u2, w3), respectively. But then edge (u3, w5) is not allowed to cross (u1, w3) and (u2, w2), and so this edge is not drawable at all. Thus, the only option left is that all the vertices u3, u4, and u5 are in R1. Howe…
Figure 26
Figure 26. Figure 26: The regions in Γ6 [PITH_FULL_IMAGE:figures/full_fig_p034_26.png]
Figure 27
Figure 27. Figure 27: The regions in Γ7. (u2, w4) and (u2, w5). Hence each of such edges must cross either both edges (u1, w2) and (u2, w1), or both edges (u1, w5) and (u2, w4). Since there are three such edges, there must be a fan-crossing. Hence, Γ7 cannot be a subdrawing of a fan-crossi…
Figure 28
Figure 28. Figure 28: (a) u3 is in R1; (u3, w3) crosses (u1, w2) and (u2, w1); (u3, w4) crosses (u1, w5), and (b) w6 is in R 0 6; (u3, w6) crosses (u2, w5); (u1, w6) crosses (u2, w4). introducing a fan-crossing, vertex w6 must be in R0 6 . To avoid introducing any fan-crossing, edge (u3, w…
Figure 29
Figure 29. Figure 29: (a) u3 is in R6; (u3, w1) crosses (u1, w5); (u3, w2) crosses (u2, w5); (u3, w3) crosses (u1, w4), and (b) w6 is in R (1) 6 ; (u2, w6) crosses (u3, w3). (u2, w5), respectively; see Fig 29a. It follows that (u3, w3) crosses either (u1, w4) or (u2, w4). W.l.o.g. assume t…
Figure 30
Figure 30. Figure 30: Vertex w6 is in R5; (u3, w6) crosses (u2, w4); (u1, w6) crosses (u2, w3). a fan-crossing. So, vertex w7 is in R5. In particular, in the presence of the edge (u3, w7), vertex w7 must be in the region denoted by R0 5 (see Fig 29b). However, this implies that the edge (u…
Figure 31
Figure 31. Figure 31: (a) u3 is in R7 of Γ4 and (b) R7 is partitioned into 5 subregions R (1) 7 , . . . R(5) 7 . Finally, we consider the case in which u3 is in R1. By Lemma 3 (for R = R1 [R = R7], wi = w2, wj = w3 and wk = w5 [wk = w4]), it follows that the edge (u3, w2) has to cross the …
Figure 32
Figure 32. Figure 32: Illustration of the cases in which (a) w6 is in R (1) 7 and (b) w6 is in R4 [PITH_FULL_IMAGE:figures/full_fig_p039_32.png]
Figure 33
Figure 33. Figure 33: Illustration of the cases in which (a) u3 is in R1 and (b) w6 is in R1. Hence, vertex u3 can only be in R1. The edge (u3, w3) can be drawn without introducing fan-crossings only if it crosses either both edges (u1, w2) and (u2, w1), or both edges (u1, w5) and (u1, w4)…
Figure 34
Figure 34. Figure 34: w6 is in R5 [PITH_FULL_IMAGE:figures/full_fig_p042_34.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 33 canonical work pages

  1. [3]

    Ackerman, E., Tardos, G.: On the maximum number of edges in quasi-planar graphs. J. Comb. Theory, Ser. A 114(3), 563–571 (2007). https://doi.org/10.1016/j.jcta.2006.08.002

    doi:10.1016/j.jcta.2006.08.002 2007

  2. [1]

    In: EuroCG

    ´Abrego, B.M., Aichholzer, O., Fern´ andez-Merchant, S., Hackl, T., Pammer, J., Pilz, A., Ramos, P., Salazar, G., Vogtenhuber, B.: All good drawings of small complete graphs. In: EuroCG. pp. 57–60 (2015)

    work page 2015

  3. [2]

    CoRR abs/1509.01932 (2015)

    Ackerman, E.: On topological graphs with at most four crossings per edge. CoRR abs/1509.01932 (2015)

    arXiv 2015

  4. [4]

    Combinatorica 17(1), 1–9 (1997)

    Agarwal, P.K., Aronov, B., Pach, J., Pollack, R., Sharir, M.: Quasi-planar graphs have a linear number of edges. Combinatorica 17(1), 1–9 (1997). https://doi.org/10.1007/BF01196127

    doi:10.1007/bf01196127 1997

  5. [5]

    Aigner, M., Ziegler, G.M.: Proofs from THE BOOK (3rd. ed.). Springer (2004)

    work page 2004

  6. [6]

    Angelini, P., Bekos, M.A., Kaufmann, M., Kindermann, P., Schneck, T.: 1- fan-bundle-planar drawings of graphs. Theor. Comput. Sci. 723, 23–50 (2018). https://doi.org/10.1016/j.tcs.2018.03.005

    doi:10.1016/j.tcs.2018.03.005 2018

  7. [7]

    In: ISAAC

    Angelini, P., Bekos, M.A., Kaufmann, M., Pfister, M., Ueckerdt, T.: Beyond-planarity: Tur´ an-type results for non-planar bipartite graphs. In: ISAAC. LIPIcs, vol. 123, pp. 28:1–28:13. Schloss Dagstuhl (2018). https://doi.org/10.4230/LIPIcs.ISAAC.2018.28

    work page doi:10.4230/lipics.isaac.2018.28 2018

  8. [8]

    Arleo, A., Binucci, C., Di Giacomo, E., Evans, W.S., Grilli, L., Liotta, G., Meijer, H., Montecchiani, F., Whitesides, S., Wismath, S.K.: Visibility rep- resentations of boxes in 2.5 dimensions. Comput. Geom. 72, 19–33 (2018). https://doi.org/10.1016/j.comgeo.2018.02.007

    work page doi:10.1016/j.comgeo.2018.02.007 2018

Show all 47 references
  1. [9]

    Gilyonot Lematematika 3, 2–8 (1966)

    Avital, S., Hanani, H.: Graphs. Gilyonot Lematematika 3, 2–8 (1966)

    1966

  2. [10]

    In: Biedl, T.C., Kerren, A

    Bachmaier, C., Rutter, I., Stumpf, P.: 1-gap planarity of complete bipartite graphs. In: Biedl, T.C., Kerren, A. (eds.) Graph Drawing and Network Visualization. LNCS, vol. 11282, pp. 646–648. Springer (2018)

    2018

  3. [11]

    Bae, S.W., Baffier, J., Chun, J., Eades, P., Eickmeyer, K., Grilli, L., Hong, S., Korman, M., Montecchiani, F., Rutter, I., T´ oth, C.D.: Gap-planar graphs. Theor. Comput. Sci. 745, 36–52 (2018). https://doi.org/10.1016/j.tcs.2018.05.029

    2018 doi

  4. [12]

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

    Bekos, M.A., Cornelsen, S., Grilli, L., Hong, S., Kaufmann, M.: On the recognition of fan-planar and maximal outer-fan-planar graphs. Algorithmica 79(2), 401–427 (2017)

    2017

  5. [13]

    Binucci, C., Di Giacomo, E., Didimo, W., Montecchiani, F., Patrignani, M., Symvo- nis, A., Tollis, I.G.: Fan-planarity: Properties and complexity. Theor. Comp. Sci. 589, 76–86 (2015)

    2015

  6. [14]

    In: Graph Drawing

    Brandenburg, F.J.: A simple quasi-planar drawing of K10. In: Graph Drawing. LNCS, vol. 9801, pp. 603–604. Springer (2016)

    2016

  7. [15]

    Brandenburg, F.J.: A first order logic definition of beyond-planar graphs. J. Graph Algorithms Appl. 22(1), 51–66 (2018)

    2018

  8. [16]

    Brandenburg, F.J.: On fan-crossing and fan-crossing free graphs. Inf. Process. Lett. 138, 67–71 (2018). https://doi.org/10.1016/j.ipl.2018.06.006

    2018 doi

  9. [17]

    Bruckdorfer, T., Cornelsen, S., Gutwenger, C., Kaufmann, M., Montecchiani, F., N¨ ollenburg, M., Wolff, A.: Progress on partial edge drawings. J. Graph Algorithms Appl. 21(4), 757–786 (2017). https://doi.org/10.7155/jgaa.00438

    2017 doi

  10. [18]

    JoCG 9(1), 213–246 (2018)

    Cardinal, J., Felsner, S.: Topological drawings of complete bipartite graphs. JoCG 9(1), 213–246 (2018)

    2018

  11. [19]

    Algorithmica 73(4), 673–695 (2015)

    Cheong, O., Har-Peled, S., Kim, H., Kim, H.: On the number of edges of fan-crossing free graphs. Algorithmica 73(4), 673–695 (2015). https://doi.org/10.1007/s00453-014-9935-z

    2015 doi

  12. [20]

    Czap, J., Hud´ ak, D.: 1-planarity of complete multipartite graphs. Disc. App. Math. 160(4-5), 505–512 (2012). https://doi.org/10.1016/j.dam.2011.11.014

    2012 doi

  13. [21]

    Didimo, W., Eades, P., Liotta, G.: A characterization of complete bipartite RAC graphs. Inf. Process. Lett. 110(16), 687–691 (2010)

    2010

  14. [22]

    Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theor. Comp. Sci. 412(39), 5156–5166 (2011)

    2011

  15. [23]

    In: Thirty Essays on Geometric Graph Theory, pp

    Didimo, W., Liotta, G.: The crossing-angle resolution in graph drawing. In: Thirty Essays on Geometric Graph Theory, pp. 167–184. Springer (2013)

    2013

  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 (Feb 2019)

    2019

  17. [25]

    Eades, P., Liotta, G.: Right angle crossing graphs and 1-planarity. Disc. Appl. Math. 161(7–8), 961–969 (2013)

    2013

  18. [26]

    Algorithmica 80(3), 977–994 (2018)

    Eppstein, D., Kindermann, P., Kobourov, S.G., Liotta, G., Lubiw, A., Maig- nan, A., Mondal, D., Vosoughpour, H., Whitesides, S., Wismath, S.K.: On the planar split thickness of graphs. Algorithmica 80(3), 977–994 (2018). https://doi.org/10.1007/s00453-017-0328-y

    2018 doi

  19. [27]

    Garey, M., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA (1979)

    1979

  20. [28]

    Gioan, E.: Complete graph drawings up to triangle mutations. In: WG. LNCS, vol. 3787, pp. 139–150. Springer (2005). https://doi.org/10.1007/11604686 13

    2005 doi

  21. [29]

    Congressus Numerantium 71, 105–114 (1990)

    Gronau, H.D.O., Harborth, H.: Numbers of nonisomorphic drawings for small graphs. Congressus Numerantium 71, 105–114 (1990)

    1990

  22. [30]

    Vierteljschr

    Hadwiger, H.: ¨Uber eine Klassifikation der Streckenkomplexe. Vierteljschr. Natur- forsch. Ges. Z¨ urich88, 133–143 (1943)

    1943

  23. [31]

    Graphs and Combinatorics 1(1), 311–329 (1985)

    Hartsfield, N., Jackson, B., Ringel, G.: The splitting number of the complete graph. Graphs and Combinatorics 1(1), 311–329 (1985). https://doi.org/10.1007/BF02582960

    1985 doi

  24. [32]

    In: PacificVis 2008

    Huang, W., Hong, S., Eades, P.: Effects of crossing angles. In: PacificVis 2008. pp. 41–46. IEEE (2008)

    2008

  25. [33]

    CoRR 1403.6184 (2014)

    Kaufmann, M., Ueckerdt, T.: The density of fan-planar graphs. CoRR 1403.6184 (2014)

    2014 arXiv

  26. [34]

    Kehribar, Z.: K5,5 kann nicht 2-planar gezeichnet werden: Analyse und Beweis (2018), Bachelor Thesis, Universit¨ at T¨ ubingen

    2018

  27. [35]

    Kynˇ cl, J.: Simple realizability of complete abstract topological graphs in P. Disc. & Comp. Geom. 45(3), 383–399 (2011). https://doi.org/10.1007/s00454-010-9320-x

    2011 doi

  28. [36]

    Kynˇ cl, J.: Improved enumeration of simple topological graphs. Disc. & Comp. Geom. 50(3), 727–770 (2013). https://doi.org/10.1007/s00454-013-9535-8

    2013 doi

  29. [37]

    SIAM Journal on Optimization 11(4), 1065–1080 (2001)

    Mutzel, P.: An alternative method to crossing minimization on hierar- chical graphs. SIAM Journal on Optimization 11(4), 1065–1080 (2001). https://doi.org/10.1137/S1052623498334013

    2001 doi

  30. [38]

    Pach, J., Radoiˇ ci´ c, R., Tardos, G., T´ oth, G.: Improving the crossing lemma by finding more crossings in sparse graphs. Disc. Comput. Geom. 36(4), 527–552 (2006)

    2006

  31. [39]

    Combinatorica 17(3), 427–439 (1997)

    Pach, J., T´ oth, G.: Graphs drawn with few crossings per edge. Combinatorica 17(3), 427–439 (1997)

    1997

  32. [40]

    https://doi.org/10.1007/s00493-006-0032-z

    Pach, J., T´ oth, G.: How many ways can one draw a graph? Combinatorica 26(5), 559–576 (2006). https://doi.org/10.1007/s00493-006-0032-z

    2006 doi

  33. [41]

    Rafla, N.H.: The Good Drawings Dn of the Complete Graph Kn. Ph.D. thesis, McGill. University, Montreal, Quebec (1988)

    1988

  34. [42]

    Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Sem. Univ. Hamb. 29, 107–117 (1965)

    1965

  35. [43]

    General”, while the number of the non-isomorphic ones in the column “Non-Iso

    Zarankiewicz, K.: On a problem of P. Tur´ an concerning graphs. Fundamenta Math- ematicae 41, 137–145 (1954) Appendix A Preliminary Notions and Definitions In this paper, we consider graphs containing neither multi-edges nor self-loops. Let G = (V,E ) be a graph. A drawing of G...

    1954

  36. [44]

    Similarly, the edge (u1,w 6) must cross (u2,w 4); see dashed dotted blue edges in Fig

    To avoid introducing any fan-crossing, edge (u3,w 6) must cross (u2,w 3). Similarly, the edge (u1,w 6) must cross (u2,w 4); see dashed dotted blue edges in Fig. 28b. Next, we argue for vertexw7, which cannot lie in R′ 6, since by the arguments above (u3,w 7) would have to cros...

  37. [45]

    In fact, this edge is not allowed to cross any edge incident to u2, or one of the edges (u3,w 3), (u3,w 6) and (u1,w 6), or both edges (u1,w 3), (u1,w 2)

    But then it is easy to see that ( u2,w 7) yields inevitably a fan-crossing. In fact, this edge is not allowed to cross any edge incident to u2, or one of the edges (u3,w 3), (u3,w 6) and (u1,w 6), or both edges (u1,w 3), (u1,w 2). It remains to consider the case in which w6 in...

  38. [46]

    As in the previous case, we next argue for w7, which cannot be in R6 (by the arguments above)

    To see this, observe that ( u1,w 6) can cross neither any edge incident to u1, nor one of the edges ( u3,w 3) and (u3,w 4), nor both edges (u2,w 4) and (u2,w 5), nor both edges ( u2,w 3) and (u2,w 1). As in the previous case, we next argue for w7, which cannot be in R6 (by the...

  39. [47]

    They can cross neither (u3,w 3), nor the pair (u1,w 3) and (u1,w 2), nor the pair (u1,w 4) and (u1,w 5)

    For both edges (u2,w 6) and (u2,w 7) the following holds. They can cross neither (u3,w 3), nor the pair (u1,w 3) and (u1,w 2), nor the pair (u1,w 4) and (u1,w 5). Thus, both have to cross (u3,w 4), yielding a fan-crossing. From the case analysis above, we conclude that in the ...

Pith tools

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