Linkage problem on optimal 1 1 -planar graphs
Shohei Koizumi, Ryosuke Osaka, Yusuke Suzuki · 2026
Read Linkage problem on optimal 1 1 -planar graphs by Shohei Koizumi, Ryosuke Osaka, Yusuke Suzuki (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-27682.txt.
Description
A linkage problem asks for disjoint paths that join given pairs of vertices in a graph. Shohei Koizumi, Ryosuke Osaka, and Yusuke Suzuki study such problems in 2026 for optimal 1-planar graphs. A 1-planar graph can be drawn with at most one crossing per edge. Optimal ones pack in the maximum possible number of edges. Planar graphs already have a complete linkage characterisation, due to Enami and Maezawa.
The main theorem concerns well-connected cases. Every optimal 1-planar graph with connectivity six is (5,5)-linked. That means disjoint paths can always be found for the paired sets of five vertices each. The authors also study graphs that fail a smaller linkage demand. For an optimal 1-planar graph that is not (2,2,1)-linked, they characterise the blocking vertex sets. The obstruction uses three disjoint sets, two of size two and one of size one, that prevent the required linkage.
Catalog record
| CREATOR | Shohei Koizumi, Ryosuke Osaka, Yusuke Suzuki |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.27682