The minimal nonplanar strong digraphs
Stephen Bartell · 2025
Read The minimal nonplanar strong digraphs by Stephen Bartell (2025) 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-2503-06718.txt.
Introduction
Stephen Bartell and co-authors extend a famous theorem about drawings of networks to arrows, in this 2025 paper. Kuratowski's theorem says that any network that cannot be drawn on paper without crossings contains, deep inside, one of two forbidden patterns. Directed graphs, where every edge is a one-way arrow, need their own version of that story.
The authors study strongly connected directed graphs, those where travel along arrows can reach any point from any other, and ask which minimal ones refuse to lie flat. Minimal means the failure is exact: every proper part of the graph is planar, yet the whole is not. They identify those minimal offenders. Two related drawing styles get the same treatment: outerplanar drawings, where all points sit on the boundary, and series-parallel layouts. The work completes a Kuratowski-style classification for the directed world.
Catalog record
| CREATOR | Stephen Bartell |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-06718
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The minimal nonplanar strong digraphs Thanks: Supported by AFOSR grant FA9550-22-1-0234, and NSF grant DMS-2154169. Stephen Bartell Abstract Kuratowski’s theorem says that the minimal (under subgraph containment) graphs that are not planar are the subdivisions of K 5 K_{5} and of K 3 , 3 K_{3,3} . 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. 1 Introduction What are the minimal digraphs (under subdigraph containment) that are strong and nonplanar? (“Strong” means strongly-connected.) We will prove that for every such digraph, its underlying graph is a subdivision of a graph of one of the seven types shown in Figures 1 and 2 . (We will define these types more precisely later.) Figure 1: A Möbius chain and a double wheel. Figure 2: A conch, a mussel, a scallop, a clam and a whelk. Remarkably, the question reduces, almost exactly, to a question about undirected graphs. Say a nonplanar graph G is almost-planar if G is 3-connected and F is the edge-set of a forest, where F is the set of edges e such that G\setminus e is nonplanar. If G is a digraph that is minimal strong and nonplanar, and not the directed subdivision of a smaller digraph, then it is an orientation of an almost-planar graph; and we will find explicitly all the almost-planar graphs. (These are the graphs of the two figures.) Thus we have: 1.1 A strong digraph is planar if and only if no subdigraph is a directed subdivision of a strong orientation of either a Möbius chain, a double wheel, a conch, a scallop, a mussel, a clam, or a whelk. Let us say a fan in G is a pair (P,v) where P is a path of G with length at least two, and v\in V(G)\setminus V(P) is adjacent to every vertex of the interior of P (and possibly also adjacent to its ends), and each vertex in the interior of v has degree three in G . If \{v,x,y\} is a triangle of a graph, let us subdivide the edge xy , replacing it by a path P , and make v adjacent to all the new vertices introduced (and possibly delete the edges vx,vy ). Then (P,v) is a fan of the new graph, and we call this process opening a fan . All the five types of graphs shown in Figure 2 can be obtained from graphs of bounded size (in most cases, from K_{5} ) by opening a fan at most three times, and so in some sense they are “essentially” of bounded size; but this is not so for the types of Figure 1 . 1.1 does not quite answer the question of what the minimal strong nonplanar digraphs are. The seven different types of graphs in the figures all give rise to infinitely many instances of minimal strong nonplanar digraphs, but not every graph of these types can be appropriately oriented, and some can be oriented in many ways. This is a non-trivial issue, that we discuss in the final section. This work grew out of the senior thesis [ 1 ] of one of the authors, and a much easier question: what are the minimal digraphs that are strong and not outerplanar? ( Outerplanar means it can be drawn in a plane with all vertices incident with the infinite region,) For that problem we can list all such digraphs explicitly. Similarly we can find explicitly all minimal digraphs that are strong and not series-parallel (we say a digraph is series-parallel if it is an orientation of a graph that contains no subdivision of K_{4} as a subgraph). All graphs and digraphs in this paper are assumed to be finite, and to have no loops or parallel edges, and digraphs have no directed cycles of length two. If G is a digraph and uv\in E(G) , subdividing uv means making a new digraph by deleting the edge uv and adding a directed path from u to v of new vertices (except for u,v ), and we call a digraph obtained from G by iterating this process a directed subdivision of G . Figure 3: Obstructions for outerplanar. In Figure 3 we show four digraphs. Any directed subdivision of the first is a strong theta , and any directed subdivision of the second is a reinforced theta . The third is called the strong directed K_{4} , and the fourth represents a class of digraphs; this one is an 8-diwheel . In general, if k\geq 2 is an integer, a 2k -diwheel is a digraph obtained from a cycle of length 2k by adding a new vertex adjacent with every vertex of the cycle, and then directing the edges in such a way that all the triangles become cyclic triangles. We will show: 1.2 A strong digraph is outerplanar if and only if no subdigraph is a directed subdivision of one of the digraphs in Figure 3 ; that is, no subdigraph is a strong theta, or a reinforced theta, or a directed subdivision of the strong directed K_{4} , or a directed subdivision of a 2k -wheel for some k\geq 2 . We remark that we could forbid subdividing the rightmost, vertical edge of the second digraph in the figure, because when this is subdivided, the digraph contains a strong theta. Similarly we could forbid subdividing three edges of the strong directed K_{4} , and we could forbid subdividing the edges of the diwheel incident with the “central” vertex, for the same reason. If we do that, then we have the list of all the minimal digraphs that are strong and not outerplanar. For series-parallel, the list is the same except we omit the two theta-digraphs. We will show: 1.3 A strong digraph is series-parallel if and only if no subdigraph is a directed subdivision of the strong directed K_{4} or of a 2k -wheel for some k\geq 2 . The paper is organized as follows. In the next section we prove 1.2 and 1.3 , which are both easy. Then we identify all the almost-planar graphs, and this is broken into several steps. First, in section 3 we show that every almost-planar graph that contains a subdivision of the four-rung Möbius ladder V_{8} is a Möbius chain. Then in section 4 we introduce two more eight-vertex graphs U_{8} and W_{8} ; and show that: • the only almost-planar graph not containing a subdivision of K_{3,3} is K_{5} ; • every almost-planar graph that contains a subdivision of K_{3,3} and not of U_{8},V_{8} or W_{8} is either a Möbius chain, scallop or clam; • every almost-planar graph that contains a subdivision of W_{8} and not of V_{8} is a double wheel; • every almost-planar graph that contains a subdivision of U_{8} and not of V_{8} is either a double wheel, conch, whelk or mussel. This completes the description of all almost-planar graphs. Finally, in section 6 we discuss how to direct the edges of an almost-planar graph to make a minimal strong nonplanar digraph. 2 The outerplanar and series-parallel theorems We will often speak of the paths and