pith. sign in

arxiv: 2512.11535 · v3 · submitted 2025-12-12 · 🧮 math.CO

A note on optimal 2-planar graphs

Licheng Zhang , Yuanqiu Huang , Zhangdong Ouyang This is my paper

Pith reviewed 2026-05-16 23:14 UTC · model grok-4.3

classification 🧮 math.CO
keywords optimal 2-planar graphsHamiltonian-connected4-connected graphs3-connected graphsnon-Hamiltonian graphsgraph embeddingscrossings
0
0 comments X

The pith

Every 4-connected optimal 2-planar graph is Hamiltonian-connected.

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

This paper proves that optimal 2-planar graphs become Hamiltonian-connected once they reach 4-connectivity, so that any two vertices are joined by a path visiting all vertices exactly once. A sympathetic reader cares because the result lifts known Hamiltonicity theorems from planar graphs into the setting of drawings with at most two crossings per edge. The authors further establish sharpness by exhibiting an infinite family of 3-connected optimal 2-planar graphs that contain no Hamiltonian cycle at all. The distinction isolates connectivity as the precise threshold separating the two behaviors in this class of near-planar graphs.

Core claim

We prove that every 4-connected optimal 2-planar graph is Hamiltonian-connected. Furthermore, we show that the 4-connectedness condition is sharp by constructing infinitely many 3-connected optimal 2-planar graphs that are non-Hamiltonian.

What carries the argument

4-connectivity applied to optimal 2-planar graphs (drawings with at most two crossings per edge) to force a Hamiltonian path between every pair of vertices.

If this is right

  • Such graphs contain a Hamiltonian path between every pair of vertices.
  • Hamiltonicity fails for some 3-connected optimal 2-planar graphs.
  • There exist infinitely many non-Hamiltonian 3-connected optimal 2-planar graphs.

Where Pith is reading between the lines

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

  • The same connectivity threshold might separate Hamiltonian-connectedness from mere Hamiltonicity in other bounded-crossing graph classes.
  • Algorithms that search for long paths in near-planar networks could exploit 4-connectivity as a sufficient test.
  • It remains open whether 4-connected optimal 2-planar graphs satisfy stronger properties such as being 1-Hamiltonian.

Load-bearing premise

Standard definitions of optimal 2-planarity and 4-connectivity suffice to guarantee the Hamiltonian-connected property without further restrictions on the embedding or crossings.

What would settle it

A single 4-connected optimal 2-planar graph containing two vertices with no Hamiltonian path between them, or a Hamiltonian cycle appearing in one of the constructed 3-connected examples.

Figures

Figures reproduced from arXiv: 2512.11535 by Licheng Zhang, Yuanqiu Huang, Zhangdong Ouyang.

Figure 1
Figure 1. Figure 1: An optimal 2-planar graph with order 20 The following is a result of Thomassen, which is a key step in the proof of Theorem 1.1. Lemma 2.3 (Thomassen, [25]). Let G be a planar graph. If κ(G) ≥ 4, then G is Hamiltonian-connected. 3 Face-stellation of a 2-connected plane graph This section mainly serves as a preparation for proving Theorem 1.1. Let G be a 2-connected plane graph. For each face of G, insert a… view at source ↗
Figure 2
Figure 2. Figure 2: A plane graph H where all faces except the outer triangular face are pentagons Proof of Theorem 1.2. First, a plane graph H needed for our construction is shown in [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: F An anonymous person once asked us whether a similar result holds for non-simple 4-connected optimal 2-planar graphs. We leave this question open for future investiga￾tion. Another interesting direction is to replace “optimal” with “maximal” in Theorem 1.1, leading to the following problem regarding maximal 2-planar graphs. Problem 5.2. Is every 4-connected maximal 2-planar graph Hamiltonian? We note that… view at source ↗
Figure 4
Figure 4. Figure 4: A saturated 2-planar drawing of K4,6 Inspired by Tutte’s theorem and the well-known open problem of whether every 6- connected 1-planar graph is Hamiltonian, it is natural to ask how far this phenomenon extends to k-planar graphs. Within the class of k-planar graphs, any such connectivity threshold ℓ must necessarily be bounded as a function of k (for instance, the bound discussed above should be understoo… view at source ↗
read the original abstract

In this note, we prove that every 4-connected optimal 2-planar graph is Hamiltonian-connected. Furthermore, we show that the 4-connectedness condition is sharp by constructing infinitely many 3-connected optimal 2-planar graphs that are non-Hamiltonian.

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.

Referee Report

0 major / 3 minor

Summary. The paper proves that every 4-connected optimal 2-planar graph is Hamiltonian-connected. It further establishes sharpness of the 4-connectedness hypothesis by exhibiting an infinite family of 3-connected optimal 2-planar graphs that fail to be Hamiltonian.

Significance. If the proof is correct, the result adds a clean structural theorem to the literature on Hamiltonian properties of graphs with a linear number of crossings. The explicit infinite family of counterexamples for 3-connectivity supplies a useful sharpness statement that can be referenced in future work on connectivity thresholds for Hamiltonicity in near-planar graphs.

minor comments (3)
  1. The abstract and introduction should explicitly recall the precise definition of an optimal 2-planar graph (maximum number of edges for a given number of vertices under at most two crossings per edge) rather than assuming the reader recalls it verbatim.
  2. In the construction section, label the vertices and edges of the base graph used to generate the infinite family so that the non-Hamiltonian property can be verified by direct inspection without additional diagrams.
  3. Add a short remark after the main theorem stating whether the proof relies on any special embedding properties beyond the standard definition of optimal 2-planarity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, accurate summary of the main results, and recommendation for minor revision. We appreciate the recognition that the theorem provides a clean structural result on Hamiltonian-connectedness in optimal 2-planar graphs and that the infinite family of counterexamples usefully demonstrates sharpness of the 4-connectedness hypothesis.

Circularity Check

0 steps flagged

No circularity; direct combinatorial proof with independent construction

full rationale

The manuscript proves that every 4-connected optimal 2-planar graph is Hamiltonian-connected and exhibits sharpness via an explicit infinite family of 3-connected counterexamples. No equations, fitted parameters, or self-referential reductions appear. The argument proceeds from standard definitions of optimal 2-planarity and connectivity using combinatorial case analysis and constructions that do not invoke prior results by the same authors in a load-bearing manner. The claim is therefore self-contained and does not reduce to its inputs by definition or by self-citation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard graph-theoretic definitions of 2-planarity, optimality, connectivity, and Hamiltonian-connectedness with no free parameters or new entities introduced.

axioms (1)
  • standard math Standard definitions and basic properties of planar and 2-planar graphs hold
    The paper invokes established combinatorial graph theory concepts without re-deriving them.

pith-pipeline@v0.9.0 · 5323 in / 1068 out tokens · 28979 ms · 2026-05-16T23:14:04.094474+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Ackerman,On topological graphs with at most four crossings per edge, Comput

    E. Ackerman,On topological graphs with at most four crossings per edge, Comput. Geom.85 (2019), 101574, 31, DOI 10.1016/j.comgeo.2019.101574. MR4010251↑8

    work page doi:10.1016/j.comgeo.2019.101574 2019

  2. [2]

    Ball and O

    S. Ball and O. Serra,A course in combinatorics and graphs, Compact Textbooks in Mathematics, Birkh¨ auser/Springer, Cham, [2024]©2024. MR4769863↑5

    work page 2024

  3. [3]

    Baybars,Onk-path Hamiltonian maximal planar graphs, Discrete Math.40(1982), no

    I. Baybars,Onk-path Hamiltonian maximal planar graphs, Discrete Math.40(1982), no. 1, 119–121, DOI 10.1016/0012-365X(82)90193-5. MR0676717↑6

    work page doi:10.1016/0012-365x(82)90193-5 1982

  4. [4]

    M. A. Bekos, E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani, and C. Raftopoulou,Edge partitions of optimal 2-plane and 3-plane graphs, Discrete Math.342(2019), no. 4, 1038–1047, DOI 10.1016/j.disc.2018.12.002. MR3895013↑2, 4

    work page doi:10.1016/j.disc.2018.12.002 2019

  5. [5]

    M. A. Bekos, M. Kaufmann, and C. N. Raftopoulou,On optimal 2- and 3-planar graphs, 33rd International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., vol. 77, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, pp. Art. No. 16, 16. MR3685688↑2, 4 9

    work page 2017

  6. [6]

    Biedl,Are highly connected 1-planar graphs Hamiltonian(2019), available at arXiv:1911.02153

    T. Biedl,Are highly connected 1-planar graphs Hamiltonian(2019), available at arXiv:1911.02153. Preprint.↑3

    work page arXiv 2019

  7. [7]

    Binucci, A

    C. Binucci, A. B¨ ungener, G. Di Battista, W. Didimo, V. Dujmovi´ c, S.-H. Hong, M. Kaufmann, G. Liotta, P. Morin, and A. Tappini,Min-k-planar drawings of graphs, J. Graph Algorithms Appl. 28(2024), no. 2, 1–35. MR4763192↑2

    work page 2024

  8. [8]

    J. A. Bondy and U. S. R. Murty,Graph theory, Graduate Texts in Mathematics, vol. 244, Springer, New York, 2008. MR2368647↑7

    work page 2008

  9. [9]

    F. J. Brandenburg,Recognizing optimal 1-planar graphs in linear time, Algorithmica80(2018), no. 1, 1–28, DOI 10.1007/s00453-016-0226-8. MR3741533↑2

    work page doi:10.1007/s00453-016-0226-8 2018

  10. [10]

    F¨ orster, M

    H. F¨ orster, M. Kaufmann, and C. N. Raftopoulou,Recognizing and embedding simple opti- mal 2-planar graphs, Graph drawing and network visualization, Lecture Notes in Comput. Sci., vol. 12868, Springer, Cham, [2021]©2021, pp. 87–100, DOI 10.1007/978-3-030-92931-2 6. MR4424763↑2

    work page doi:10.1007/978-3-030-92931-2 2021

  11. [11]

    Fujisawa, K

    J. Fujisawa, K. Segawa, and Y. Suzuki,The matching extendability of optimal 1-planar graphs, Graphs Combin.34(2018), no. 5, 1089–1099, DOI 10.1007/s00373-018-1932-6. MR3846896↑3

    work page doi:10.1007/s00373-018-1932-6 2018

  12. [12]

    Fabrici, J

    I. Fabrici, J. Harant, T. Madaras, S. Mohr, R. Sot´ ak, and C. T. Zamfirescu,Long cycles and spanning subgraphs of locally maximal 1-planar graphs, J. Graph Theory95(2020), no. 1, 125– 137, DOI 10.1002/jgt.22542. MR4130388↑3

    work page doi:10.1002/jgt.22542 2020

  13. [13]

    13 Petr Hliněný and Csenge Lili Ködmön

    A. Grigoriev and H. L. Bodlaender,Algorithms for graphs embeddable with few crossings per edge, Algorithmica49(2007), no. 1, 1–11, DOI 10.1007/s00453-007-0010-x. MR2344391↑2

    work page doi:10.1007/s00453-007-0010-x 2007

  14. [14]

    Hopcroft and R

    J. Hopcroft and R. Tarjan,Efficient planarity testing, J. Assoc. Comput. Mach.21(1974), 549– 568, DOI 10.1145/321850.321852. MR0359387↑2

    work page doi:10.1145/321850.321852 1974

  15. [15]

    Hud´ ak, T

    D. Hud´ ak, T. Madaras, and Y. Suzuki,On properties of maximal 1-planar graphs, Discuss. Math. Graph Theory32(2012), no. 4, 737–747, DOI 10.7151/dmgt.1639. MR2993519↑2, 3, 7

    work page doi:10.7151/dmgt.1639 2012

  16. [16]

    Kawarabayashi and K

    K.-i. Kawarabayashi and K. Ozeki,4-connected projective-planar graphs are Hamiltonian- connected, J. Combin. Theory Ser. B112(2015), 36–69, DOI 10.1016/j.jctb.2014.11.006. MR3323033↑2

    work page doi:10.1016/j.jctb.2014.11.006 2015

  17. [17]

    Kabenyuk,The minimal partition of a triangle into pentagons, 2023

    M. Kabenyuk,The minimal partition of a triangle into pentagons, 2023. Math StackExchange, Question 4644257.↑7

    work page 2023

  18. [18]

    arXiv:2412.09161v1 [math.CO], 12 Dec 2024

    ,Minimal pentagulations ofn-gons, 2024. arXiv:2412.09161v1 [math.CO], 12 Dec 2024. ↑7

    work page arXiv 2024

  19. [19]

    Noguchi and Y

    K. Noguchi and Y. Suzuki,Relationship among triangulations, quadrangulations and optimal 1-planar graphs, Graphs Combin.31(2015), no. 6, 1965–1972, DOI 10.1007/s00373-015-1568-8. MR3417207↑

    work page doi:10.1007/s00373-015-1568-8 2015

  20. [20]

    Ozeki, N

    K. Ozeki, N. Van Cleemput, and C. T. Zamfirescu,Hamiltonian properties of polyhedra with few 3-cuts—a survey, Discrete Math.341(2018), no. 9, 2646–2660, DOI 10.1016/j.disc.2018.06.015. MR3828776↑2

    work page doi:10.1016/j.disc.2018.06.015 2018

  21. [21]

    Ozeki and C

    K. Ozeki and C. T. Zamfirescu,Every 4-connected graph with crossing number 2 is Hamiltonian, SIAM J. Discrete Math.32(2018), no. 4, 2783–2794, DOI 10.1137/17M1138443. MR3882945↑2

    work page doi:10.1137/17m1138443 2018

  22. [22]

    Graphs drawn with few crossings per edge

    J. Pach and G. T´ oth,Graphs drawn with few crossings per edge, Combinatorica17(1997), no. 3, 427–439, DOI 10.1007/BF01215922. MR1606052↑2

    work page doi:10.1007/bf01215922 1997

  23. [23]

    Suzuki,Re-embeddings of maximum 1-planar graphs, SIAM J

    Y. Suzuki,Re-embeddings of maximum 1-planar graphs, SIAM J. Discrete Math.24(2010), no. 4, 1527–1540, DOI 10.1137/090746835. MR2746706↑3, 4

    work page doi:10.1137/090746835 2010

  24. [24]

    Thomas and X

    R. Thomas and X. Yu, 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B62(1994), no. 1, 114–132, DOI 10.1006/jctb.1994.1058. MR1290634↑2

    work page doi:10.1006/jctb.1994.1058 1994

  25. [25]

    Thomassen,A theorem on paths in planar graphs, J

    C. Thomassen,A theorem on paths in planar graphs, J. Graph Theory7(1983), no. 2, 169–176, DOI 10.1002/jgt.3190070205. MR0698698↑2, 3, 5 10

    work page doi:10.1002/jgt.3190070205 1983

  26. [26]

    W. T. Tutte,A theorem on planar graphs, Trans. Amer. Math. Soc.82(1956), 99–116, DOI 10.2307/1992980. MR0081471↑2

    work page doi:10.2307/1992980 1956

  27. [27]

    J. C. Urschel and J. Wellens,Testing gapk-planarity is NP-complete, Inform. Process. Lett.169 (2021), Paper No. 106083, 8, DOI 10.1016/j.ipl.2020.106083. MR4212057↑2

    work page doi:10.1016/j.ipl.2020.106083 2021

  28. [28]

    Whitney,A theorem on graphs, Ann

    H. Whitney,A theorem on graphs, Ann. of Math. (2)32(1931), no. 2, 378–390, DOI 10.2307/1968197. MR1503003↑2

    work page doi:10.2307/1968197 1931

  29. [29]

    M. C. Wigal and X. Yu,Tutte paths and long cycles in circuit graphs, J. Combin. Theory Ser. B 158(2023), 313–330, DOI 10.1016/j.jctb.2022.07.006. MR4513827↑2

    work page doi:10.1016/j.jctb.2022.07.006 2023

  30. [30]

    C. T. Zamfirescu,On the hamiltonicity of a planar graph and its vertex-deleted subgraphs, J. Graph Theory102(2023), no. 1, 180–193, DOI 10.1002/jgt.22864. MR4520067↑2

    work page doi:10.1002/jgt.22864 2023

  31. [31]

    Zhang, Y

    L. Zhang, Y. Huang, S. Lv, and F. Dong,4-connected 1-planar chordal graphs are Hamiltonian- connected, Journal of Graph Theory110(2025), 72-81, DOI https://doi.org/10.1002/jgt.23250. ↑3 11

    work page doi:10.1002/jgt.23250 2025