arxiv: 2604.21589 · v2 · submitted 2026-04-23 · 🧮 math.CO

Recognition: unknown

Extremal 1-planar graphs without k-cliques

Fengming Dong, Licheng Zhang, Yuanqiu Huang

Authors on Pith no claims yet

Pith reviewed 2026-05-09 21:29 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C1005C35

keywords 1-planar graphsextremal graph theoryTurán-type problemsK_r-free graphsedge boundsplanarization

0 comments

The pith

K3-free 1-planar graphs on n vertices have at most 3n-8 edges, with sharpened bounds also for K4-free and K5-free cases.

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

This paper strengthens upper bounds on the number of edges in 1-planar graphs that contain no small cliques. It shows that a K3-free 1-planar graph on n at least 4 vertices has no more than 3n-8 edges, improving on the earlier 3n-6 limit, and that the new bound is achieved by explicit constructions when n is even and at least 8. Parallel results give a floor(7n/2)-7 edge limit for K4-free 1-planar graphs on n at least 3 and a 4n-8 limit for K5-free ones, both tight for large enough n. These limits matter because 1-planar graphs are the simplest graphs that can be drawn with a bounded number of crossings, so knowing how clique-free substructures reduce their density clarifies the trade-off between planarity and local density.

Core claim

Every K3-free 1-planar graph on n greater than or equal to 4 vertices has at most 3n-8 edges, tight for even n at least 8. Every K4-free 1-planar graph on n at least 3 vertices has at most floor(7n/2)-7 edges, tight for all n at least 9. Every K5-free 1-planar graph on n at least 3 vertices has at most 4n-8 edges, tight for n equals 8 and for all n at least 10. These strengthen earlier bounds obtained by Bekos et al. for the K3-free case.

What carries the argument

1-planar drawings in which every edge is crossed at most once, together with counting arguments on the crossings and faces after planarization to bound edges under the K_r-free condition.

If this is right

General 1-planar graphs can reach 4n-8 edges, so forbidding even a triangle reduces the maximum density.
Explicit constructions achieve equality in each bound for infinitely many vertex counts, confirming sharpness.
The results apply directly to all n meeting the stated lower thresholds.
The bounds are obtained by refining crossing-count and discharging techniques on the planarized drawing.

Where Pith is reading between the lines

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

The same counting methods could be tried on 1-planar graphs that avoid other small subgraphs beyond cliques.
Knowing these exact densities may help bound the running time of recognition algorithms that search for dense substructures.
Extending the same style of argument to 2-planar or other bounded-crossing graphs is a natural next question.

Load-bearing premise

The graphs are simple and admit a drawing in which each edge is crossed at most once, with K_r-freeness defined by the absence of a clique subgraph in the usual sense.

What would settle it

A simple 1-planar K3-free graph on 8 vertices that has 17 edges would falsify the 3n-8 bound.

Figures

Figures reproduced from arXiv: 2604.21589 by Fengming Dong, Licheng Zhang, Yuanqiu Huang.

**Figure 1.** Figure 1: Incidence multiplicities of the vertex u with faces F 0 , F 1 , F 2 , F 3 For any subset Γ of F (G), let η(u, Γ) := P F∈Γ η(u, F). That is, η(u, Γ) is the sum of the incidence multiplicities of u with the faces in Γ. Observation 3.1. Let G be a plane graph and u be a vertex of G. Then η(u, F (G)) = dG(u), and 0 ≤ η(u, F) ≤ dG(u) for each face F ∈ F (G). Let G be a 1-plane graph with the planarization G × .… view at source ↗

**Figure 2.** Figure 2: A fake vertex z incident with exactly two opposite 3-faces. Lemma 3.4. Let G ∈ ForbP1,n(K3), where n ≥ 4. Then A ≥ 0, where equality holds if and only if every fake vertex z in G× is incident with exactly two 3-faces, and these two 3-faces are opposite, shown in [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** Figure 3: Possible types of 4-faces and almost alternating 5-face [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

**Figure 4.** Figure 4: Local configuration of u of degree two where x and y are fake vertices Lemma 4.3. For any G ∈ ForbP1,n(K3), if u is an alternating vertex of G, then dG(u) ≥ 4. Proof. Suppose that u is an alternating vertex in a graph G of ForbP1,n(K3). By Lemma 4.2, dG(u) ≥ 3. Suppose that NG(u) = {x, y, z}. As u is an alternating 3-vertex, the local structure around u is as shown in [PITH_FULL_IMAGE:figures/full_fig_p01… view at source ↗

**Figure 5.** Figure 5: The local structure of an alternating 3-vertex [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗

**Figure 6.** Figure 6: F1 and F2 We are now going to complete the proof by establishing the following claims. Claim 5.1. ∂(F1) and ∂(F2) have at most one edge in common. Proof. Suppose the claim fails, and ∂(F1) and ∂(F2) have at least two edges in common. Then, they share exactly two edges, as shown in [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗

**Figure 7.** Figure 7: F1 and F2 have two edges in common on their boundary Claim 5.2. ∂(F1) and ∂(F2) have no edge in common. Proof. Suppose the claim fails. By Claim 5.1, ∂(F1) and ∂(F2) have exactly one edge in common. We first show that ∂(F1) and ∂(F2) cannot share one true edge. Otherwise, the structure formed by edges on ∂(F1) ∪ ∂(F2) is as shown in [PITH_FULL_IMAGE:figures/full_fig_p015_7.png] view at source ↗

**Figure 8.** Figure 8: F1 and F2 have exactly one edge in common on their boundary By Claim 5.2, ∂(F1) and ∂(F2) have no edge in common. Since a(c) = 2 and uvcwu is a 4-face, by Lemma 3.3, ws and vt are true edges in G × , and both wscw and vtcv bound fake 3-faces. Since the boundaries of faces F1 and F2 share no common edge, uw is incident with a fake 3-face wuc2w, and uv is incident with a fake 3-face uvc1u. Consequently, the … view at source ↗

**Figure 9.** Figure 9: The local structure around F1 Let H := C(G). Claim 5.3. Either dH×(w) ≥ 3 or dH×(v) ≥ 3. Proof. Suppose that dH×(w) ≤ 2 and dH×(v) ≤ 2. Since c, c2 ∈ NH×(w) and c, c1 ∈ NH×(v), we have NH×(w) = {c, c2} and NH×(v) = {c, c1}. It follows that both ws and vt are incident with one fake 3-face only, implying that both of them are incident with F2. Thus, both ws and vt are the only true edges on ∂(F2). However, t… view at source ↗

**Figure 10.** Figure 10: Graphs in ForbP1,8(K4) and ForbP1,9(K5), respectively 17 [PITH_FULL_IMAGE:figures/full_fig_p017_10.png] view at source ↗

**Figure 11.** Figure 11: Graphs Hk , G9, and G10. For i = 1, 2, let Qi denote the 1-plane graph obtained from G8+i by removing all edges in the set {a1a2, b1b2, ub2, va1}. Then, Qi has a true 6-face Fi whose boundary is the cycle ua1b1vb2a2u, i.e., the shaded region in [PITH_FULL_IMAGE:figures/full_fig_p018_11.png] view at source ↗

**Figure 12.** Figure 12: Graphs G2ℓ+1 and G2ℓ+2 for ℓ ≥ 5 Similarly, for any n = 2ℓ + 2, where ℓ ≥ 5, let Gn be the 1-plane graph obtained from Q2 and H′ ℓ−2 := Hℓ−2 − {ua1, a1b1, b1v, vbℓ−2, bℓ−2aℓ−2, aℓ−2u} by inserting H′ ℓ−2 into the face F2 of Q2 such that the six vertices u, a1, b1, v, bℓ−2 and aℓ−2 in H′ ℓ−2 are identified with the six vertices u, a1, b1, v, b2 and a2 in Q2, respectively, as shown in [PITH_FULL_IMAGE:figu… view at source ↗

**Figure 13.** Figure 13: Gn ∈ ForbP1,n(K5) for n = 8, 10, 11, and 13. Now we are going to apply the Q4-addition introduced in [26] to create graphs in ForbP1,n(K5) from graphs in ForbP1,n−4(K5) for n = 12 and n ≥ 14. Let G be a 1-plane graph. We say G ′ is obtained from G by a Q4-addition if G contains a clique {u1, u2, u3, u4} such that edges u1u3 and u2u4 cross each other in G, and G ′ is obtained by the following operations: (… view at source ↗

**Figure 14.** Figure 14: A new 1-plane graph obtained by a Q4-addition Proof. (i) follows from the definition directly. (ii). It suffices to show that G ′ is K5-free. Suppose that W is a 5-clique in G ′ . Since G ∈ ForbP1,n(K5), W ∩ {v1, v2, v3, v4} , ∅. Since NG′({v1, v2, v3, v4}) = {u1, u2, u3, u4}, W is a subset of {v1, v2, v3, v4} ∪ {u1, u2, u3, u4}. Assume that W = U′ ∪ V ′ , where U′ = W ∩ {u1, u2, u3, u4} and V ′ = W ∩ {v1… view at source ↗

**Figure 15.** Figure 15: A non-bipartite graph in ForbP1,n(K3) with size 3n − 10 for n = 10. More generally, it would be interesting to further investigate upper bounds on the number of edges in 1-planar graphs forbidding other subgraphs. For example, as mentioned by Bekos et al. [2], for Ck with k ≥ 4, can one obtain (tight) upper bounds? It is interesting to study the Turan problems on 1-planar graphs forbidding ´ paths, theta … view at source ↗

read the original abstract

In 2016, Dowden initiated the study of planar Tur\'an-type problems, which has since attracted considerable attention. Recently, Bekos et al. proved that every $K_3$-free $1$-planar graph on $n\ge 4$ vertices has at most $3n-6$ edges. In this paper, we strengthen this bound to $3n - 8$, which is tight for all even $n \ge 8$. Furthermore, we show that every $K_4$-free $1$-planar graph on $n \ge 3$ vertices has at most $\bigl\lfloor \tfrac{7n}{2} \bigr\rfloor - 7$ edges, and this bound is tight for all integers $n \ge 9$. We also prove that every $K_5$-free $1$-planar graph on $n \ge 3$ vertices has at most $4n - 8$ edges, which is tight for $n = 8$ and for all integers $n \ge 10$.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note private letter to a colleague

This paper tightens the edge upper bounds for K3-free, K4-free, and K5-free 1-planar graphs and gives matching constructions for large n.

read the letter

The main things to know are that the authors improve the K3-free bound from 3n-6 to 3n-8 (tight for even n at least 8) and add new bounds of floor(7n/2)-7 for K4-free graphs (tight for n at least 9) and 4n-8 for K5-free graphs (tight for n=8 and n at least 10). These sit in the line of planar Turán-type problems started by Dowden and extended to 1-planar graphs by Bekos et al. The abstract states the results cleanly with explicit tightness conditions, which is the right format for this kind of extremal work. The constructions are the part that stands out; without them the upper bounds would be less convincing. The paper does a straightforward job of extending the existing approach to the next two clique sizes without obvious overreach. Soft spots are limited. The K4-free bound looks a little messier because of the floor and the -7 offset, which probably comes from handling small cases or the specific constructions, but that is common in these problems and not a red flag. Since I only have the abstract and the stress-test note, I cannot inspect the discharging arguments or the verification that the constructions are indeed 1-planar and clique-free, so any referee would need to check those steps carefully. Nothing in the stated claims suggests circular reasoning or non-standard definitions. This is for people already working on extremal functions for 1-planar or beyond-planar graphs. A reader who follows Turán-type results in sparse graph classes would pick up the new numbers and the constructions quickly. It is narrow but the improvements are concrete and the tightness is addressed, so it deserves a serious referee rather than a desk reject. I would send it out for review; the claims are precise enough that a couple of referees can verify the proofs and constructions without much trouble.

Referee Report

0 major / 2 minor

Summary. The manuscript strengthens known bounds on the maximum number of edges in K_r-free 1-planar graphs. It proves that every K_3-free 1-planar graph on n≥4 vertices has at most 3n−8 edges (tight for even n≥8), every K_4-free 1-planar graph on n≥3 vertices has at most ⌊7n/2⌋−7 edges (tight for n≥9), and every K_5-free 1-planar graph on n≥3 vertices has at most 4n−8 edges (tight for n=8 and n≥10). These results improve the prior 3n−6 bound for the K_3-free case and include matching constructions.

Significance. If the derivations and constructions hold, the paper advances extremal graph theory for 1-planar graphs by supplying tighter, tight bounds for small forbidden cliques together with explicit extremal examples for large n. The work fits the growing literature on planar Turán-type problems and provides concrete, falsifiable statements that can guide further research on 1-planar density.

minor comments (2)

§1 (Introduction): the statement of the main theorems could be numbered and cross-referenced explicitly in the text to improve navigation between the abstract claims and their proofs.
The tightness constructions (mentioned for even n≥8, n≥9, and n=8/n≥10) would benefit from a dedicated subsection or figure showing the edge counts explicitly for the smallest cases to allow immediate verification.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation for minor revision. The report accurately summarizes our strengthened extremal bounds for K_3-free, K_4-free, and K_5-free 1-planar graphs along with the matching constructions.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives three explicit upper bounds on the maximum number of edges in K_r-free 1-planar graphs (3n-8 for K3-free, floor(7n/2)-7 for K4-free, and 4n-8 for K5-free) together with matching constructions that establish tightness for sufficiently large n. These strengthen a prior 3n-6 bound from Bekos et al. (external citation) and are presented as consequences of standard 1-planarity and clique-freeness definitions. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the derivation chain consists of independent structural arguments and extremal constructions that remain falsifiable against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard combinatorial definitions rather than new parameters or entities.

axioms (1)

domain assumption Standard definitions of 1-planar graphs and K_r-free graphs from graph theory
The results assume the usual notions of 1-planarity (at most one crossing per edge) and subgraph-freeness.

pith-pipeline@v0.9.0 · 5488 in / 1275 out tokens · 35287 ms · 2026-05-09T21:29:28.440835+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

30 extracted references · 24 canonical work pages

[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 22

work page doi:10.1016/j.comgeo.2019.101574 2019
[2]

M. A. Bekos, P . Bose, A. B¨ungener, V . Dujmovi´c, M. Hoffmann, M. Kaufmann, P . Morin, S. Odak, and A. Weinberger,On k-planar graphs without short cycles, J. Graph Algorithms Appl.29(2025), 1–22, DOI 10.7155/jgaa.v29i3.3003

work page doi:10.7155/jgaa.v29i3.3003 2025
[3]

Bodendiek, H

R. Bodendiek, H. Schumacher, and K. Wagner,Bemerkungen zu einem Sechsfarbenproblem von G. Ringel, Abh. Math. Sem. Univ. Hamburg53(1983), 41–52, DOI 10.1007/BF02941309 (German). MR0732806

work page doi:10.1007/bf02941309 1983
[4]

F. J. Brandenburg, D. Eppstein, A. Gleißner, M. T. Goodrich, K. Hanauer, and J. Reislhuber,On the density of maximal 1-planar graphs, Graph drawing, Lecture Notes in Comput. Sci., vol. 7704, Springer, Heidelberg, 2013, pp. 327–338, DOI 10.1007/978-3-642-36763-2 29. MR3067240

work page doi:10.1007/978-3-642-36763-2 2013
[5]

Czap and D

J. Czap and D. Hud ´ak,1-planarity of complete multipartite graphs, Discrete Appl. Math.160(2012), no. 4-5, 505–512, DOI 10.1016/j.dam.2011.11.014. MR2876333

work page doi:10.1016/j.dam.2011.11.014 2012
[6]

Czap and D

J. Czap and D. Hud ´ak,On drawings and decompositions of 1-planar graphs, Electron. J. Combin.20 (2013), no. 2, Paper 54, 8, DOI 10.37236/2392. MR3084596

work page doi:10.37236/2392 2013
[7]

Diestel,Graph theory, 6th ed., Graduate Texts in Mathematics, vol

R. Diestel,Graph theory, 6th ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin, [2025] ©2025. MR4874150

2025
[8]

Dowden,Extremal C 4-free/C5-free planar graphs, J

C. Dowden,Extremal C 4-free/C5-free planar graphs, J. Graph Theory83(2016), no. 3, 213–230, DOI 10.1002/jgt.21991. MR3549506

work page doi:10.1002/jgt.21991 2016
[9]

On the structure of linear graphs , JOURNAL =

P . Erd˝os and A. H. Stone,On the structure of linear graphs, Bull. Amer. Math. Soc.52(1946), 1087–1091, DOI 10.1090/S0002-9904-1946-08715-7. MR0018807

work page doi:10.1090/s0002-9904-1946-08715-7 1946
[10]

Fabrici and T

I. Fabrici and T. Madaras,The structure of 1-planar graphs, Discrete Math.307(2007), no. 7-8, 854–865, DOI 10.1016/j.disc.2005.11.056. MR2297168

work page doi:10.1016/j.disc.2005.11.056 2007
[11]

Gerbner and C

D. Gerbner and C. Palmer,Survey of Generalized Tur´ an Problems — Counting Subgraphs, Electron. J. Combin.DS27(2026), Paper No. DS27, DOI 10.37236/14563. MR5037331

work page doi:10.37236/14563 2026
[12]

J. L. Gross and T. W. Tucker,Topological graph theory, Wiley-Interscience Series in Discrete Math- ematics and Optimization, John Wiley & Sons, Inc., New York, 1987. A Wiley-Interscience Pub- lication. MR0898434

1987
[13]

Ghosh, E

D. Ghosh, E. Gy ˝ori, R. R. Martin, A. Paulos, and C. Xiao,Planar Tur´ an number of the 6-cycle, SIAM J. Discrete Math.36(2022), no. 3, 2028–2050, DOI 10.1137/21M140657X. MR4474377

work page doi:10.1137/21m140657x 2022
[14]

Gy ˝ori, A

E. Gy ˝ori, A. Li, and R. Zhou,The planar Tur´ an number of the seven-cycle, arXiv preprint (2023), available at arXiv:2307.06909

work page arXiv 2023
[15]

Hud ´ak and T

D. Hud ´ak and T. Madaras,On local properties of 1-planar graphs with high minimum degree, Ars Math. Contemp.4(2011), no. 2, 245–254, DOI 10.26493/1855-3974.131.91c. MR2802062

work page doi:10.26493/1855-3974.131.91c 2011
[16]

D. V . Karpov,An upper bound on the number of edges in an almost planar bipartite graph, J. Math. Sci. (New York)196(2014), no. 6, 737–746, DOI 10.1007/s10958-014-1690-9

work page doi:10.1007/s10958-014-1690-9 2014
[17]

Kaufmann, B

M. Kaufmann, B. Klemz, K. Knorr, M. M. Reddy, F. Schr¨oder, and T. Ueckerdt,The density formula: one lemma to bound them all, 32nd International Symposium on Graph Drawing and Network Visualization, LIPIcs. Leibniz Int. Proc. Inform., vol. 320, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2024, pp. Art. No. 7, 17, DOI 10.4230/lipics.gd.2024.7. MR4821240

work page doi:10.4230/lipics.gd.2024.7 2024
[18]

Keevash,Hypergraph Tur´ an problems, Surveys in combinatorics 2011, London Math

P . Keevash,Hypergraph Tur´ an problems, Surveys in combinatorics 2011, London Math. Soc. Lecture Note Ser., vol. 392, Cambridge Univ. Press, Cambridge, 2011, pp. 83–139. MR2866732

2011
[19]

Y. Lan, Y. Shi, and Z.-X. Song,Extremal theta-free planar graphs, Discrete Math.342(2019), no. 12, 111610, 8, DOI 10.1016/j.disc.2019.111610. MR3990020

work page doi:10.1016/j.disc.2019.111610 2019
[20]

Y. Lan, Y. Shi, and Z.-X. Song,Planar Tur´ an number and planar anti-Ramsey number of graphs, Oper. Res. Trans.25(2021), no. 3, 200–216 (English). MR4357025

2021
[21]

Nakamoto, K

A. Nakamoto, K. Noguchi, and K. Ozeki,Cyclic 4-colorings of graphs on surfaces, J. Graph Theory 82(2016), no. 3, 265–278, DOI 10.1002/jgt.21900. MR3502764 23

work page doi:10.1002/jgt.21900 2016
[22]

Pach and G

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

work page doi:10.1007/bf01215922 1997
[23]

Schaefer,Crossing numbers of graphs, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2018

M. Schaefer,Crossing numbers of graphs, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2018. MR3751397

2018
[24]

R. Shi, Z. Walsh, and X. Yu,Dense circuit graphs and the planar Tur´ an number of a cycle, J. Graph Theory108(2025), no. 1, 27–38, DOI 10.1002/jgt.23165. MR4828036

work page doi:10.1002/jgt.23165 2025
[25]

R. Shi, Z. Walsh, and X. Yu,Planar Tur´ an number of the 7-cycle, European J. Combin.126(2025), Paper No. 104134, 24, DOI 10.1016/j.ejc.2025.104134. MR4866462

work page doi:10.1016/j.ejc.2025.104134 2025
[26]

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

work page doi:10.1137/090746835 2010
[27]

Suzuki,1-planar graphs, Beyond planar graphs—communications of NII Shonan meetings, Springer, Singapore, [2020]©2020, pp

Y. Suzuki,1-planar graphs, Beyond planar graphs—communications of NII Shonan meetings, Springer, Singapore, [2020]©2020, pp. 47–68, DOI 10.1007/978-981-15-6533-5 4. MR4305146

work page doi:10.1007/978-981-15-6533-5 2020
[28]

Tur´an,Eine Extremalaufgabe aus der Graphentheorie, Mat

P . Tur´an,Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok48(1941), 436–452 (Hun- garian, with German summary). MR0018405

1941
[29]

Xu and A

W. Xu and A. Chang,The spectral radius of1-planar graphs without complete subgraphs, arXiv preprint (2025), available at arXiv:2512.12909

work page arXiv 2025
[30]

Zhang and Y

X. Zhang and Y. Li,Dynamic list coloring of 1-planar graphs, Discrete Math.344(2021), no. 5, Paper No. 112333, 8, DOI 10.1016/j.disc.2021.112333. MR4218488 24

work page doi:10.1016/j.disc.2021.112333 2021