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

CREATORShohei Koizumi, Ryosuke Osaka, Yusuke Suzuki
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.27682

Browse the full library · About the Tower of Babel