The bend-number of K_{4,5} is three

The bend-number b(G) of a graph G is the least k such that G is the edge-intersectiongraph of paths in a rectangular grid, each with at most k bends. Heldt, Knauer and Ueckerdt(2014) proved b(Km,m) = ⌈m/2⌉ and gave bounds for Km,n. For m = 4 these results giveb(K4,4) = 2 and b(K4,n) = 3 for 6 ≤ n ≤ 8, but they leave the case K4,5 open. We show thatK4,5 has no 2-bend representation, so b(K4,5) = 3 and K4,n is a 2-bend graph exactly whenn ≤ 4. The proof reduces the question to a 27 × 27 grid by an order-preserving compression ofcoordinates. It then refutes a SAT encoding of the finite question, and an independent checkerverifies the solver’s LRAT proof. Cross-checks with a second, independently written encodingare in progress. As a by-product, the open MIPLIB 2017 instance neos-3603137-hoteo, whichasks for a 2-bend representation of K4,5 on an 8 × 8 grid, is infeasible. All programs, formulasand verification logs are released with this note.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-20
DOI
https://doi.org/10.5281/zenodo.24390485
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The bend-number of K_{4,5} is three

Stylianos Iordanis
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

The bend-number of K_{4,5} is three

Stylianos Iordanis
preprint en

Abstract

The bend-number b(G) of a graph G is the least k such that G is the edge-intersectiongraph of paths in a rectangular grid, each with at most k bends. Heldt, Knauer and Ueckerdt(2014) proved b(Km,m) = ⌈m/2⌉ and gave bounds for Km,n. For m = 4 these results giveb(K4,4) = 2 and b(K4,n) = 3 for 6 ≤ n ≤ 8, but they leave the case K4,5 open. We show thatK4,5 has no 2-bend representation, so b(K4,5) = 3 and K4,n is a 2-bend graph exactly whenn ≤ 4. The proof reduces the question to a 27 × 27 grid by an order-preserving compression ofcoordinates. It then refutes a SAT encoding of the finite question, and an independent checkerverifies the solver’s LRAT proof. Cross-checks with a second, independently written encodingare in progress. As a by-product, the open MIPLIB 2017 instance neos-3603137-hoteo, whichasks for a 2-bend representation of K4,5 on an 8 × 8 grid, is infeasible. All programs, formulasand verification logs are released with this note.

Zenodo (CERN European Organization for Nuclear Research)
National Technical University of Athens (GR)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon