Smallest Cubic Non-1-Planar Graphs

Abstract

A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have $30$ vertices. Two such graphs are the Tutte-Coxeter graph of girth eight and a graph of girth seven that we call the Byte graph. Every subcubic graph with fewer than $30$ vertices is 1-planar. Our proof is computer-assisted, but directly testing all relevant graphs is impractical. To establish non-1-planarity of the two graphs, we extend a SAT-based solver with a custom clause propagator based on separating cycles and a case split based on graph automorphisms, allowing independent cases to be solved in parallel. To show that all smaller subcubic graphs are 1-planar, we introduce the concept of k-flexibility: every set of at most k prescribed edges can remain uncrossed in some 1-planar drawing. We use this property to reconstruct 1-planar drawings of larger graphs from drawings of smaller k-flexible graphs. This replaces exhaustive testing of more than forty billion cubic graphs with computations on far fewer graphs of smaller order.

The integrability of sesqui-regular graphs with smallest eigenvalue at least −3
Qianqian Yang, Ruo-Lan Ding
arXiv23 Sep 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
Resolving a Problem of Lv and Koolen on the Smallest Eigenvalue of Distance-Regular Graphs
Zhen-Mu Hong, Fu-Tao Hu, Chenhui Lv
arXiv27 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
A counterexample to vertex interpolation by planar C¹ cubic splines
Junkai Qiu
arXiv6 Sep 2026PreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
v-numbers of powers of edge ideals of cubic circulant graphs
Guangjun Zhu, Jiaxin Li, Yulin Hu
arXiv24 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
Least energy sign-changing solutions for asymptotically cubic Kirchhoff equations on locally finite graphs
Shuai An, Junping Xie, Xingyong Zhang
arXiv11 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{pupyrev2026smallest,
  title = {{Smallest Cubic Non-1-Planar Graphs}},
  author = {Sergey Pupyrev},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.27168},
  eprint = {2609.27168},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.27168},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Smallest Cubic Non-1-Planar Graphs
AU  - Sergey Pupyrev
PY  - 2026
DA  - 2026/09/23
PB  - arXiv
DO  - 10.48550/arxiv.2609.27168
UR  - https://arxiv.org/abs/2609.27168
AB  - A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have $30$ vertices. Two such graphs are the Tutte-Coxeter graph of girth eight and a graph of girth seven that we call the Byte graph. Every subcubic graph with fewer than $30$ vertices is 1-planar. Our proof is computer-assisted, but directly testing all relevant graphs is impractical. To establish non-1-planarity of the two graphs, we extend a SAT-based solver with a custom clause propagator based on separating cycles and a case split based on graph automorphisms, allowing independent cases to be solved in parallel. To show that all smaller subcubic graphs are 1-planar, we introduce the concept of k-flexibility: every set of at most k prescribed edges can remain uncrossed in some 1-planar drawing. We use this property to reconstruct 1-planar drawings of larger graphs from drawings of smaller k-flexible graphs. This replaces exhaustive testing of more than forty billion cubic graphs with computations on far fewer graphs of smaller order.
ER  -

Abstract

Related

Cite