Journal of Graph Theory Discrete Mathematics and Combinatorics

The Minimal Nonplanar Strong Digraphs

Stephen Bartell, Paul Seymour
Wiley · 2026-10-01 · DOI 10.1002/jgt.70142

Abstract

ABSTRACT Kuratowski's theorem says that the minimal (under subgraph containment) graphs that are not planar are the subdivisions of and of . Here we study the minimal (under subdigraph containment) strongly‐connected digraphs that are not planar. We also find the minimal strongly‐connected non‐outerplanar digraphs and the minimal strongly‐connected non‐series‐parallel digraphs.

Read at publisher →