PaperlayerView exact revision on arXiv

Source-linked AI summary

Smallest Cubic Non-1-Planar Graphs

Sergey Pupyrev

arXiv:2609.27168v1math.COcs.CGcs.DM

TL;DR

The paper asks for the smallest cubic graph that is not 1-planar, a difficult recognition problem even for sparse graphs. It strengthens a SAT solver and uses graph reductions to establish the exact threshold: 30 vertices. The Tutte-Coxeter and Byte graphs are non-1-planar examples at that order, while every smaller subcubic graph is 1-planar.

  • Problem

    The smallest cubic non-1-planar graph is unknown, and recognizing 1-planarity is NP-complete even under strong restrictions.

    Source: §1 · p. 1

  • Method

    The paper strengthens a SAT-based solver with separating-cycle propagation and automorphism-based case splitting, and uses cycle reductions to prove smaller graphs 1-planar.

    Source: §3.1 · p. 6, §3.2 · p. 6, §4.1 · p. 10

  • Results

    The minimum order is 30: the Tutte-Coxeter and Byte graphs are non-1-planar, and every cubic graph with at most 28 vertices is 1-planar.

    Source: §1 · p. 2, §3.2 · p. 7, §4 · p. 8

  • Takeaways & Limitations

    Every subcubic graph with fewer than 30 vertices is 1-planar, so the smallest subcubic non-1-planar graphs are cubic and have order 30.

    Source: §1 · p. 2

    The paper verifies all 546 connected cubic graphs of order 30 and girth at least seven, but classifying all cubic graphs of order 30 remains challenging.

    Source: §5 · p. 19

Abstract

from arXiv · show

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.

1 Introduction

The paper resolves the search for the smallest cubic non-1-planar graph: the minimum order is 30, while every subcubic graph below that order is 1-planar. It combines SAT-based methods for proving non-1-planarity with reductions that avoid testing every smaller graph directly.

1 Introduction

  • The general 1-planar density bound does not establish non-1-planarity for cubic graphs, motivating the search for a smallest example.A cubic graph has 3n/2 edges, below the general density bound of 4n − 8.Source: §1 · p. 1
  • Earlier computations covered about 150 million graphs but remained far from finding the smallest non-1-planar instance.Proving non-1-planarity is difficult because it requires ruling out every crossing pattern; highly symmetric instances create especially large families of equivalent patterns.Source: §1 · p. 2
  • The cube-connected-cycles construction gives a 2048-vertex non-1-planar graph, but little information about the smallest possible order.Its crossing-number lower bound is 1549, exceeding the 1536 crossings possible in a 1-planar drawing of that graph.Source: §1 · p. 2
  • 30 vertices is the minimum order of a cubic non-1-planar graph; every subcubic graph with fewer than 30 vertices is 1-planar.The Tutte-Coxeter and Byte graphs provide non-1-planar examples at order 30.Source: §1 · p. 2
  • Separating-cycle propagation and graph-automorphism symmetry breaking strengthen OOPS to prove the two 30-vertex examples non-1-planar.The propagator learns clauses from detected conflicts, while automorphisms let equivalent crossing-pattern cases be avoided.Source: §1 · p. 2
  • k-flexibility and cycle reduction rules replace exhaustive testing of all cubic graphs with computations on smaller graph families.The rules address 3-, 4-, and 5-cycles and reconstruct drawings while specified edges remain uncrossed.Source: §1 · p. 3

2 Preliminaries

The preliminaries define the graph-drawing terms and outline OOPS’s SAT encoding. The encoding represents crossings through edge merges and enforces planarity using a two-page stack layout.

2 Preliminaries

  • The paper defines graph order as vertex count, cubic graphs as degree-three at every vertex, subcubic graphs as maximum degree three, and girth as shortest-cycle length.Biconnected means a connected graph with no cut vertex.Source: §2 · p. 3
  • A graph is 1-planar when it has a plane drawing in which each edge is crossed at most once; a crossing pattern pairs independent edges without reusing an edge.The planarization replaces each crossed pair with a new vertex, and edges avoided by the pattern remain uncrossed in the resulting drawing.Source: §2 · p. 3
  • OOPS builds a Boolean formula satisfiable exactly when the input graph is 1-planar; a satisfying assignment yields a drawing, and unsatisfiability proves none exists.The paper uses OOPS, an exact SAT-based solver.Source: §2 · p. 3
  • The encoding represents candidate crossings by merging subdivided-edge vertices, then uses spine-order variables and two-page layout constraints to enforce planarity.The graph is planar if and only if it admits the specified two-page stack layout; the encoding forbids alternating endpoints for edges on the same page.Source: §2 · pp. 3–4
  • Figure 1 depicts the two cubic non-1-planar graphs of order 30.OOPS uses MapleGlucose; multi-core computations run on up to 48 cores.Source: Figure 1 · p. 4, §2 · p. 4

3 Two Cubic Graphs of Order 30 Are Non-1-Planar

The section proves computationally that the Tutte-Coxeter and Byte graphs are non-1-planar using separating-cycle propagation and graph-automorphism case splitting.

3.1 Separating-Cycle Propagation

  • For each candidate separating cycle, edge-disjoint paths requiring crossings must not outnumber available cycle edges; violations generate conflict clauses.Source: §3.1 · p. 5
  • The propagator learns conflict clauses for reuse and checks multiple bounded-length candidate cycles because forced-path counts depend on cycle choice.Source: §3.1 · p. 6

3.2 Symmetry Breaking

  • Input-graph automorphisms group equivalent crossing patterns; iterative orbit-based cases preserve prior constraints and cover drawings up to relabeling.Source: §3.2 · pp. 6–7

3 Two Cubic Graphs of Order 30 Are Non-1-Planar

  • Every final SAT case was proved unsatisfiable, establishing that the 30-vertex Tutte-Coxeter and Byte graphs are non-1-planar.Source: §3.2 · p. 7

3.2 Symmetry Breaking

  • Cases run independently in parallel, with up to 48 solver processes; timed-out cases are split recursively.Source: §3.2 · p. 7
  • Each optimization reduces running times on four additional graphs, but only their combination resolves Tutte-Coxeter and Byte within hours.Source: §3.2 · p. 7

4 All Subcubic Graphs of Order Less Than 30 Are 1-Planar

The section proves that every subcubic graph with fewer than 30 vertices is 1-planar, reducing the problem to smaller cubic graphs and computationally verified flexibility facts.

4 All Subcubic Graphs of Order Less Than 30 Are 1-Planar

  • Theorem 2 establishes that every cubic graph with at most 28 vertices is 1-planar; because cubic graphs have even order, it suffices to consider orders at most 28.Source: §4 · p. 8
  • The reductions replace tests on more than 40 billion graphs with k-flexibility tests on about 18 million smaller instances, for 0 ≤ k ≤ 3.A graph is k-flexible when any set of at most k edges can be kept uncrossed in some 1-planar drawing; 0-flexibility is 1-planarity.Source: §4 · pp. 8–9

4.1 Building Blocks

  • Every smallest subcubic graph that is not k-flexible is biconnected, cubic, and triangle-free, enabling reductions based on its 4- and 5-cycles.Cycle reductions replace a 4-cycle or 5-cycle with a smaller graph and specify uncrossed edges whose status permits reconstruction of a 1-planar drawing.Source: §4.1 · pp. 9–10
  • When H has a 1-planar drawing with ab uncrossed, or with ab and ax1 uncrossed, the reductions give G a 1-planar drawing; the proof concludes every cubic graph of order at most n is k-flexible, Pk(n).Source: §4.1 · pp. 10, 13

4.2 Verification

  • For n ≤22 and girth ≥4, biconnected nonplanar cubic graphs are 3-flexible; at n = 24 and girth ≥5 they are 2-flexible; at n = 26 and girth ≥5 they are 1-flexible.The verification tested relevant graph collections directly or, for Facts 3 and 4, applied 5-cycle reductions before directly testing unresolved instances.Source: §4.2 · p. 15
  • All 181,227 nonplanar cubic graphs of order 26 and girth at least six were directly tested, with each edge found uncrossed in some 1-planar drawing.This established 1-flexibility for the tested graphs.Source: §4.2 · p. 15
  • For the 4,700,649 distinct order-22 cores reduced from girth-five graphs, tests verified every constructed parent that was biconnected, nonplanar, and had girth at least five as 1-flexible.For a few cores whose pattern search timed out, parents were tested directly across 12 cyclic attachment orders up to rotation and reflection.Source: §4.2 · pp. 15–16
  • For order-28, girth-five graphs, reductions assigned 652,157,758 graphs to smaller instances, and direct fallback tests found 1-planar drawings for 1,522,464 graphs.The reductions used double 5-cycle reductions, degree-six or degree-seven quotients, and reduced pairs (H,b); every graph in the input family was thereby shown 1-planar.Source: §4.2 · pp. 16, 18
  • All 4,624,501 biconnected, nonplanar cubic graphs of order 28 and girth at least six were directly verified to be 1-planar.The computation found a 1-planar drawing for every graph in this family.Source: §4.2 · p. 18
  • Every cubic graph of order at most 28 is 1-planar, completing the proof because 0-flexibility is equivalent to 1-planarity.The proof establishes P3(22), P2(24), P1(26), and P0(28) in sequence, using Lemma 5 and the computational facts for orders 26 and 28.Source: §4.2 · pp. 18–19

5 Discussion

Among 546 connected cubic graphs of order 30 and girth at least seven, the Tutte-Coxeter and Byte graphs were the only verified non-1-planar instances. A full order-30 classification remains impractical, and the complexity of recognizing cubic 1-planar graphs remains open.

5 Discussion

  • Only the Tutte-Coxeter and Byte graphs were non-1-planar among the 546 connected cubic graphs of order 30 and girth at least seven that were verified.Extending this classification to all cubic graphs of order 30 remains challenging.Source: §5 · p. 19
  • Approximately 845 billion connected graphs would need direct exhaustive testing for a complete order-30 classification, beyond the practical reach of the tools developed in Section 4.Source: §5 · p. 19
  • Recognizing cubic 1-planar graphs remains an open complexity question, although recognition is NP-complete for graphs of maximum degree 20 [4].The authors suggest their results might provide building blocks for a hardness proof for cubic recognition.Source: §5 · p. 19
Loading 2609.27168v1…