Pith. sign in

REVIEW 2 major objections 4 minor 21 references

The minimum size of maximal bipartite IC-plane graphs with given connectivity

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper proves tight lower bounds on the size of maximal bipartite IC-plane graphs: at least 3n/2−2 edges for connectivity 2 and 2n−3 edges for connectivity 3.

desk verdict A solid subfield advance: tight minimum-size bounds for 2- and 3-connected maximal bipartite IC-plane graphs, with a heavy but believable face classification and one small counting slip that does not threaten the theorems. read the letter →

arxiv 2506.00878 v1 pith:SOCFTDY3 submitted 2025-06-01 math.CO

Guiping Wang , Yuanqiu Huang , Zhangdong Ouyang , Licheng Zhang This is my paper
classification math.CO MSC 05C1005C62
keywords minimumsizemaximalbipartiteIC-planegraphIC-planargraphsconnectivityedgedensity1-planarquadrangulation
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 determines the sparsest possible maximal bipartite IC-plane graphs at fixed connectivity. It proves that every $n$-vertex maximal bipartite IC-plane graph with vertex-connectivity at least 2 has at least $\frac{3}{2}n - 2$ edges, and that this bound is tight for all $n = 4k$. For connectivity at least 3, it proves a lower bound of $2n - 3$ edges, tight for all even $n \ge 6$. These results settle the minimum-size problem for connectivities 2 and 3, while the 4-connected case remains open with a conjectured bound of $\frac{13}{6}n - \frac{14}{3}$ supported by an infinite construction.

What carries the argument

The load-bearing object is the face-boundary classification in Proposition 16: in a 2-connected maximal bipartite IC-plane graph, every face boundary is one of nine configurations, with at most five true vertices and at most two false vertices, where a false vertex marks a crossing. This classification is built from the fact that the true vertices on a face induce a complete bipartite graph $K_{\ell_b,\ell_w}$ that must be outer 1-planar and therefore cannot contain $K_{3,3}$. The classification turns edge counting into a finite face inventory; ties ($K_{2,2}$ drawings with one crossing), clean versus bad ties, and the fact that for 3-connected graphs the associated plane graph becomes a quadrangulation carry the rest of the proof.

What would settle it

Look for a 2-connected maximal bipartite IC-plane graph on $n$ vertices whose drawing contains a face boundary with six or more true vertices, or construct one with fewer than $\frac{3}{2}n - 2$ edges; either outcome would refute the face classification and the theorem. A systematic computer search over small vertex sets enforcing the IC-plane and maximality conditions could settle whether Proposition 16 is exhaustive.

Watch

Extended reading notes

Core claim

The central discovery is a pair of tight lower bounds on the number of edges in maximal bipartite IC-plane graphs. For $\kappa(G) \ge 2$, the paper proves $e(G) \ge \frac{3}{2}n - 2$; for $\kappa(G) \ge 3$, it proves $e(G) \ge 2n - 3$. The $2$-connected bound is attained by a family $H_k$ on $4k$ vertices built by repeatedly inserting local configurations into a false 3-face, and the $3$-connected bound is attained by a pseudo double wheel with one added crossing edge, giving $2k$ vertices. The proof proceeds through a structural classification of face boundaries, the associated plane graph, Euler's formula, and induction by cutting along clean 4-cycles or ties. The paper also constructs an infinite 4-connected family with $\frac{13}{6}n - \frac{14}{3}$ edges and conjectures this is the exact lower bound.

Load-bearing premise

The whole lower-bound derivation rests on the claim that every face boundary in a 2-connected maximal bipartite IC-plane graph is one of the nine listed configurations, with at most five true vertices; if a face with six or more true vertices could exist, the counting and the induction would no longer go through.

Editorial extensions

If this is right

  • Every 2-connected maximal bipartite IC-plane graph has at least $\frac{3}{2}n - 2$ edges, and infinitely many graphs attain the bound at $n = 4k$.
  • Every 3-connected maximal bipartite IC-plane graph has at least $2n - 3$ edges, attained for every even $n \ge 6$.
  • For 3-connected members, removing one edge from each crossing pair yields a quadrangulation, so the lower bound follows from Euler's formula once at least one crossing is known to exist.
  • The gap between the known $\frac{9}{4}n - 4$ upper bound and these lower bounds is genuine: sparse maximal members exist even within the bipartite IC-planar class.
  • The 4-connected minimum remains open; the paper supplies an infinite family with $\frac{13}{6}n - \frac{14}{3}$ edges and conjectures optimality.

Reading between the lines

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

  • The nine-face classification suggests a finite-state grammar for face types in maximal bipartite IC-plane graphs, and similar classifications may transfer to other beyond-planar bipartite classes with bounded crossings per edge.
  • The two extremal constructions work by local insertions that preserve maximality and connectivity, so the minimum-size function for higher connectivity could be generated by an insertion grammar rather than by ad hoc constructions.
  • If the conjectured 4-connected bound holds, the minimum size rises with connectivity from $\frac{3}{2}n - 2$ to $2n - 3$ to about $\frac{13}{6}n - \frac{14}{3}$, a pattern worth testing against general $k$-connected maximal 1-planar graphs.
  • The tightness conditions are modular ($n = 4k$ and even $n$), so finding insertion variants that reach other residue classes would show whether each bound is sharp for all sufficiently large $n$.
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

2 major / 4 minor

Summary. The paper studies the minimum number of edges in maximal bipartite IC-plane graphs (MBICP-graphs) as a function of order and connectivity. The main results are Theorem 3, which gives a lower bound of (3/2)n - 2 for every n-vertex 2-connected MBICP-graph with tightness for n = 4k, and Theorem 4, which gives a lower bound of 2n - 3 for every 3-connected MBICP-graph with tightness for n = 2k. The proofs proceed by classifying the possible face boundaries of 2-connected MBICP-graphs (Proposition 16), deriving incidence relations between ties and face types (Proposition 18), and then using Euler-formula counting together with an inductive splitting argument. For 3-connected graphs the plane graph obtained by deleting one edge from each crossing pair is shown to be a quadrangulation, yielding the stronger bound. The paper also constructs an infinite family of 4-connected MBICP-graphs with (13/6)n - 14/3 edges and conjectures that this is optimal.

Significance. If the main theorems are correct, they solve the minimum-size problem for maximal bipartite IC-plane graphs with connectivity 2 and 3, a natural counterpart to existing density results for 1-planar and IC-planar graphs. The strength of the paper lies in its concrete structural framework: the face-type taxonomy, the tie/face incidence lemmas, and the explicit extremal constructions for both connectivity levels. The lower-bound arguments are not fitted to data; they are derived from stated structural lemmas and Euler's formula. The 4-connected construction and the accompanying conjecture extend the problem in a meaningful way, although the 4-connected lower bound is left open.

major comments (2)
  1. [§5.1, Claim 5 and Subcase 2.2] Claim 5 states the equality |F5| + 2|F6| = 2c + k, but its proof establishes only the inequality |F5| + 2|F6| ≤ 2c + k, because |D6| + |E6| ≤ c - k is one-sided and the displayed chain ends with an upper bound. The subsequent Euler/handshaking computation in Subcase 2.2 substitutes this as an equality and concludes e(D) = 2n - 4 - k. As written, this is internally inconsistent. The theorem can be repaired locally: replacing the equality by '≥' in the algebra yields e(D) ≥ 2n - 4 - k ≥ 2n - 4 - c, and the remainder of the proof is unchanged. The authors should restate Claim 5 as an inequality and adjust the derivation accordingly.
  2. [§3.1, Proposition 16] The face-type classification is the load-bearing structural input for both main theorems, but the proof for the cases ℓt = 4, ℓf = 2 with two distinct crossings and for ℓt = 5 is compressed: the possible cyclic orders of true and false vertices are not enumerated, and Figure 5 is the only witness for the exclusion of the remaining patterns. I checked these cases and did not find a missing face type: for ℓt = 4, ℓf = 2, the two cyclic patterns with non-adjacent false vertices force either the coloring of Figure 5(6) or a violation of IC-planarity via Lemma 12; for ℓt = 5, ℓf = 2, a second crossing would need two true vertices on the boundary outside the four vertices forced by Lemma 12, which do not exist. Because the entire counting depends on this classification, the proof should spell out these two cases explicitly rather than relying on the figure.
minor comments (4)
  1. [§5.1, Case 1] The line 'e(Dp) = 2n(Dp) = 2n - 4' should read 'e(Dp) = 2n(Dp) - 4 = 2n - 4'; as printed the first equality is false for quadrangulations.
  2. [§6 and Theorem 24] The acronym 'MBIC-graphs' is used in the title of Theorem 24 and in the concluding discussion, but the paper's definition is 'MBICP-graphs'; the notation should be made consistent.
  3. [Lemma 23] The proof that Gn is maximal is asserted with 'it is not difficult to see' and no argument is given; since the tightness of Theorem 4 depends on this, a short justification of maximality should be added.
  4. [Figure 1 caption] The caption contains the typo 'biparite'; it should be 'bipartite'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lower bounds are derived from Euler's formula, the handshaking lemma, and face-structure lemmas proved in-paper; the cited external results are independent, and the group's own citations are contextual only.

full rationale

No circularity was found. Theorems 3 and 4 are proved from within the paper: Theorem 3 runs an induction whose base cases n = 4, 5 are checked directly (e(K2,2) = 4 and e(K2,3) = 6) and whose induction step splits the drawing into proper 2-connected MBICP subgraphs D1 and D2 with n(D1) + n(D2) = n + 4 and e(D1) + e(D2) = e + 4, so the claimed 3n/2 - 2 never enters as an assumption. In the remaining subcase the count is a purely Euler/handshaking derivation on the associated plane graph D× using the in-paper classification |F3| = 2c - k and the incidence bounds of Proposition 18, together with the external crossing bound cr(D) ≤ n/4 of Lemma 5. Theorem 4 is one line from Proposition 19(iv) (Gp is a quadrangulation, so e(Dp) = 2n - 4), the in-paper Corollary 21 (a 3-connected MBICP-graph has a crossing), and e(G) = e(Dp) + cr(D). The central structural results (Lemmas 11-15, Proposition 16's nine-face classification, Propositions 18-19) are argued from the definitions of IC-planarity, Lemma 9's maximality consequence, and connectivity; they are not imported from anywhere. The two external inputs - Lemma 5 (Zhang-Liu crossing-number bound on IC-plane graphs) and Lemma 6 (Auer et al., outer 1-planar graphs are planar, used only to rule out K3,3 on a face) - are genuine outside theorems, not restatements of the target lower bounds. The authors' own prior work appears only in the introduction as context ([14], [16], [17], [18]) and is not invoked in the proofs. Two rigor slips are worth noting but neither is circular: Claim 5 states |F5| + 2|F6| = 2c + k while its proof yields only ≤ (the subsequent inequality e(D) ≥ 2n - 4 - k is exactly the direction the argument needs, so the theorem survives), and the proof of Proposition 16 delegates some cyclic-order case checks to Figure 5 - a verification-completeness risk, not a reduction of the conclusion to the input. No quantity is fitted to data, no prediction is a renamed fit, and no load-bearing equation equals its own input by construction.

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

The lower-bound proofs rest on standard plane-graph counting (Euler's formula, handshaking lemma), on the defining independence condition of IC-planar drawings, and on the known inclusion of outer 1-planar graphs in planar graphs. No free parameters are fitted. The paper introduces no new entities; the 'tie', 'clean tie', and 'bad tie' are internal configurations. The major structural assumption is Proposition 16's classification of faces, which is derived from the previous lemmas, not imposed.

assumptions (4)
  • standard math Euler's formula and the handshaking lemma apply to the associated plane graph and to the plane graph Gp.
    Used in Section 5.1 and 5.2 to transform face counts into edge counts.
  • domain assumption Outer 1-planar graphs are planar (Lemma 6, from Auer et al.).
    Used to rule out large complete bipartite induced subgraphs on face boundaries via Lemma 7.
  • domain assumption In a good IC-plane drawing, each crossing involves four distinct vertices and each vertex is incident to at most one crossing, giving cr(D) <= n/4 (Lemma 5, from Zhang-Liu).
    Used in Subcase 2.2 to convert a bound in terms of crossings into one in terms of n.
  • standard math Jordan curve theorem: a simple closed curve separates the plane in such a way that a 2-connected drawing cannot repeat a true vertex on a face boundary (Lemma 8).
    Used to justify counting true vertices without multiplicity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The minimum size of maximal bipartite IC-plane graphs with given connectivity." pith.science (2026). https://pith.science/paper/SOCFTDY3

@misc{pith2026250600878,
  author       = {Pith},
  title        = {Pith review of: The minimum size of maximal bipartite IC-plane graphs with given connectivity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SOCFTDY3}},
  note         = {Machine review of arXiv:2506.00878}
}
read the original abstract

Recently, the problem of establishing bounds on the edge density of 1-planar graphs, including their subclass IC-planar graphs, has received considerable attention. In 2018, Angelini et al. showed that any n-vertex bipartite IC-planar graph has at most 2.25n-4 edges, which implies that bipartite IC-planar graphs have vertex-connectivity at most 4. In this paper, we prove that any n-vertex maximal bipartite IC-plane graph with connectivity 2 has at least 3/2n-2 edges, and those with connectivity 3 has at least 2n-3 edges. All the above lower bounds are tight. For 4-connected maximal bipartite IC-planar graphs, the question of determining a non-trivial lower bound on the size remains open.

Figures

Figures reproduced from arXiv: 2506.00878 by the authors.

Figure 1
Figure 1. A biparite 1-plane graph with six crossings, where [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. A tie For convenience, we denote a tie by T(α), where α is the crossing of the tie, as shown in [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. (1) R3 is an unbounded region in T(α); (2) R3 is a bounded region in T(α) We observe that any pair of crossed edges in a MBICP-graph forms a tie, as stated in the following lemma. Lemma 10. Let G be a MBICP-graph. Let ab and cd be two edges in G that cross at a point α, where {a,c} ∈ X and {b, d} ∈ Y . Then G[{a, b,c, d}] ∼= T(α). Furthermore, edges ad and cb are clean in G. 5 [PITH_FULL_IMAGE:figures/full_fig_p005… view at source ↗
Figures from the paper (12 more)
Figure 4
Figure 4. Figure 4: The face F with ℓb = 2 and ℓw = 4 Lemma 15 provides a foundation for obtaining more precise structural characterizations of the faces in G. Proposition 16. Let F be a face of G. Then F belongs to one of the nine configurations shown in [PITH_FULL_IMAGE:figures/full_fi…
Figure 5
Figure 5. Figure 5: All possible faces F (colored in purple in the electronic version) in G Based on Proposition 16, we can classify the set of faces in G according to their sizes and structural char￾acteristics. Throughout the rest of this paper, we denote by Fk the set of k-faces in G. …
Figure 6
Figure 6. Figure 6: A graph G with three ties Proof. Prove (i) and (ii). Let ab and cd be two edges in G that cross at a point α, and let T(α) be a tie of G, where {a,c} ⊆ X and {b, d} ⊆ Y . Assume that T(α) is bad in G. By the definition of a bad tie, T(α) is incident to a false 3-face (…
Figure 7
Figure 7. Figure 7: Proof. Let s and t denote the sizes of the bipartition sets of G, where s ≤ t. For s = 1, the star graph K1,n−1 trivially constitutes a class of MBICP-graphs without crossings, as its good drawing is unique, in which no edges crossed each other, as illustrated in [PIT…
Figure 8
Figure 8. Figure 8: Two adjacent 4-faces F1 and F2 in G whose boundaries share exactly one common edge By Claim 1, let F1 = u0u1u2u3u0 and F2 = u1u4u5u2u1 be two adjacent 4-faces in G whose boundaries share exactly one common edge u1u2 , where {u1 , u3 , u5 } ∈ X and {u0 , u2 , u4 } ∈ Y .…
Figure 9
Figure 9. Figure 9: A false 6-face that is contained in a true 4-cycle of [PITH_FULL_IMAGE:figures/full_fig_p014_9.png]
Figure 10
Figure 10. Figure 10: Graph D and its subgraphs D1 and D2 For a crossing α in D, let R(α) denote the set of regions partitioned by T(α), clearly, |R(α)| = 3. Let r(α) denote the number of regions in R(α) that are not faces in D. Obviously, r(α) = 1 if T(α) is a bad tie. Case 2. There exist…
Figure 11
Figure 11. Figure 11: The graph D and its subgraphs D1 and D2 Proof. By Proposition 18 (i) and (ii), we have |F3 | = k + 2(c − k) = 2c − k and |B6 | = k. Now, we consider a bipartite graph H = (X, Y ), where X is the set of bad ties in D and Y is the face set of F5 ∪A6 . By Proposition 18 …
Figure 12
Figure 12. Figure 12: The construction of extremal graphs with [PITH_FULL_IMAGE:figures/full_fig_p019_12.png]
Figure 13
Figure 13. Figure 13: The extremal graph Gn with 2n − 3 edges. 19 [PITH_FULL_IMAGE:figures/full_fig_p019_13.png]
Figure 14
Figure 14. Figure 14: Graph G1 and the construction of graph Gk [PITH_FULL_IMAGE:figures/full_fig_p021_14.png]
Figure 15
Figure 15. Figure 15: The graph G2 References [1] J. A. Bondy and U. S. R. Murty. Graph Theory, GTM 244, Springer, New York, 2008. [2] X. Zhang and G. Z. Liu. The structure of plane graphs with independent crossings and its applications to coloring problems. Cent. Eur. J. Math., 11(2):308–…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    J. A. Bondy and U. S. R. Murty . Graph Theory , GTM 244, Springer, New York, 2008

    work page 2008

  2. [2]

    Zhang and G

    X. Zhang and G. Z. Liu. The structure of plane graphs with independent crossings and its applications to coloring problems. Cent. Eur. J. Math., 11(2):308–321, 2013

    work page 2013

  3. [3]

    Angelini, M.A

    P . Angelini, M.A. Bekos, M. Kaufmann, M. Pfister, and T . Ueckerdt. Beyond-planarity: Turán-type results for non-planar bipartite graphs. In Proc. 29th Annu. Internat. Sympos. Algorithms Comput. , volume 123 of LIPIcs, pages 28:1–28:13. Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2018

    work page 2018

  4. [4]

    Bodendiek, H

    R. Bodendiek, H. Schumacher, and K. Wagner. Über 1-optimale Graphen. Math. Nachr., 117:323-339, 1984

    work page 1984

  5. [5]

    Fabrici and T

    I. Fabrici and T . Madaras. The structure of 1-planar graphs.Discrete Math., 307(7-8):854-865, 2007

    work page 2007

  6. [6]

    Pach and G

    J. Pach and G. Tóth. Graphs drawn with few crossings per edge.Combinatorica, 17(3):427-439, 1997

    work page 1997

  7. [7]

    F . J. Brandenburg, D. Eppstein, A. Gleißner, M.T . Goodrich, K. Hanauer, and J. Reislhuber. On the density of maximal 1-planar graphs. In: Didimo, W ., Patrignani, M. (eds.), Graph Grawing, GD 2012, Lecture Notes in Computer Science, vol. 7704, pp. 327–338. Springer, Berlin (2013) 21

    work page 2013

  8. [8]

    F . J. Brandenburg. Recognizing IC-planar and NIC-planar graphs. J. Graph Algorithms Appl. , 22(2):239–271, 2018

    work page 2018

Show all 21 references
  1. [9]

    F . J. Brandenburg, W . Didimo, W .S. Evans, P . Kindermann, G. Liotta, and F . Montecchiani. Recognizing and drawing IC-planar graphs. Theor. Comput. Sci., 636:1-16, 2016

    2016

  2. [10]

    Barát and G

    J. Barát and G. Tóth. Improvements on the density of maximal 1-planar. J. Graph Theory, 88:101-109, 2018

    2018

  3. [11]

    D. V . Karpov. An upper bound on the number of edges in an almost planar bipartite graphs.J. Math. Sci., 196:737-746, 2014

    2014

  4. [12]

    Bachmaier, F

    C. Bachmaier, F . J. Brandenburg, K. Hanauer, D. Neuwirth, and J. Reislhuber. NIC-planar graphs.Discret. Appl. Math., 232:23-40, 2017

    2017

  5. [13]

    M. A. Bekos, P . Bose, A. Büngener, V . Dujmovi´c, M. Hoffmann, M. Kaufmann, P . Morin, S. Odak, and A. Weinberger. On k-planar graphs without short cycles. arXiv:2408.16085, 2024

    2024 arXiv

  6. [14]

    Y. Q. Huang, Z. D. Ouyang, and F .M. Dong. On the sizes of bipartite 1-planar graphs.Electron. J. Comb., 28(2):2.22, 2021

    2021

  7. [15]

    Hoffmann and M.M

    M. Hoffmann and M.M. Reddy . The number of edges in maximal 2-planar graphs. arXiv:2303.08726, 2023

    2023 arXiv

  8. [16]

    Y. Q. Huang, Z. D. Ouyang, L. C. Zhang, and F .M. Dong. Determining the minimum size of maximal 1-plane graphs. arXiv:2502.11696, 2025

    2025 arXiv

  9. [17]

    Z. P . Ding, Y. Q. Huang, and S. X. Lv. The density of maximal IC-plane graphs. preprint

  10. [18]

    Z. D. Ouyang, Y. Q. Huang, L. C. Zhang, and F .M. Dong. The minimum crossing number and minimum size of maximal 1-plane graphs with given connectivity . arXiv:2504.21558, 2025

    2025 arXiv

  11. [19]

    C. Auer, C. Bachmaier, F . J. Brandenburg, A. Gleißner, K. Hanauer, D. Neuwirth, and J. Reislhuber. Outer 1-planar graphs. Algorithmica, 74(4):1293-1320, 2016

    2016

  12. [20]

    Král’ and L

    D. Král’ and L. Stacho. Coloring plane graphs with independent crossings. J. Graph Theory, 64(3):184- 205, 2010. Appendix I In the following, we prove thatκ(Gk) = 4 in Theorem 24. Two base cycles Ci and Cj of Gk are called adjacent if e(V (Ci), V (Cj))> 0. Two subgraphs H1 and...

    2010

  13. [21]

    Thus, graph Gk[(V (Ci−1)∪ V (Ci)∪ V (Ci+1))\ S] is connected

    Since every vertex on Ci is a direct join-vertex, each remaining component of Gk[V (Ci)\ S] is linked to at least one adjacent base cycle of Ci. Thus, graph Gk[(V (Ci−1)∪ V (Ci)∪ V (Ci+1))\ S] is connected. Furthermore, graphs Gk[V (C1)∪ V (C2)∪···∪ V (Ci−1)] and Gk[V (Ci+1)∪ ...

Pith tools

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