Projective Planar Cartesian Products of Graphs

Nicholas Abell, Elizabeth McDermott, Christian Millichap · 2025

Read Projective Planar Cartesian Products of Graphs by Nicholas Abell, Elizabeth McDermott, Christian Millichap (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-2509-10261.txt.

Introduction

Nicholas Abell, Elizabeth McDermott, and Christian Millichap classify a family of graph products in this 2025 paper. A Cartesian product combines two graphs in a grid-like way. The question is which such products can be drawn on a projective plane. That surface has a twist, and it resists ordinary flat drawing.

The authors work out the smallest products that fail to fit. They gather the traits of those failures as constraints. Then they build explicit embeddings for every product that meets the constraints. One neat outcome follows. Of the thirty-five known forbidden minors for the projective plane, only six are ever needed here. The result gives a complete yes-or-no test for a broad family of graphs.

Catalog record

CREATORNicholas Abell, Elizabeth McDermott, Christian Millichap
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-10261

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Projective Planar Cartesian Products of Graphs Nicholas Abell, Elizabeth McDermott, Christian Millichap Abstract . In this paper, we provide a complete classification of Cartesian products of graphs that embed in the projective plane. Our work requires us to determine minimal Cartesian products that are nonprojective planar, organize their essential properties to be used as constraints for projective planar embeddings, and explicitly construct projective planar embeddings for Cartesian products that satisfy these constraints. A corollary of our work shows that only six of the 35 forbidden minors for the projective plane are sufficient to classify projective planar Cartesian products. 1. Introduction A graph G^{\prime} is a minor of G if G^{\prime} can be obtained by a sequence of vertex deletions, edge deletions, and edge contractions on G . The Graph Minor Theorem of Robertson and Seymour [ 10 ] shows that any minor closed graph property \mathcal{P} exhibits a finite list of forbidden minimal minors. This means there is a finite minimal set of graphs \Forb(\mathcal{P}) such that a graph G has property \mathcal{P} if and only if G has no minor in \Forb(\mathcal{P}) . Furthermore, minimality here means that every G\in\Forb(\mathcal{P}) does not have \mathcal{P} while every proper minor of G does have \mathcal{P} ; see [ 7 ] for an introduction to minor closed properties. One such minor closed property is whether a graph G embeds on a fixed compact connected surface S , that is, whether G can be drawn on a surface S where edges of G don’t cross each other. More formally, an embedding is constructed via a continuous and one-to-one function f:|G|\rightarrow S , where |G| represents a geometric realization of G ; see [ 4 ] and [ 8 ] for further background on graph embeddings on surfaces. As a result of the Graph Minor Theorem, the set \Forb(S) of forbidden minimal minors for embedding on S must be finite. In this context, the Kuratowski-Wagner Theorem [ 6 ] , [ 11 ] can be restated as \Forb(S^{2})=\{K_{5},K_{3,3}\} , where S^{2} denotes the 2 -sphere. The only other surface with a known list of forbidden minors is the projective plane, N_{1} , where \Forb(N_{1}) consists of 35 elements and the completeness of this set was determined by Archdeacon in [ 1 ] . We refer the reader to Appendix A and Section 6.5 in Mohar and Thomassen [ 8 ] for this set of graphs. In this paper, we will represent the projective plane as an identification space constructed by identifying antipodal points on the boundary of a disk. Beyond the 2 -sphere and the projective plane, there currently isn’t a complete list of \Forb(S) for any other surface S . Since the sets \Forb(S^{2}) and \Forb(N_{1}) are explicitly determined, it is natural to classify when certain subclasses of graphs are either planar (embed in the plane or S^{2} ) or projective planar (embed in the projective plane or N_{1} ). Here, we are interested in the Cartesian product of two graphs G and H , denoted G\boxempty H , which is defined to have vertex set V(G)\times V(H) and a pair of vertices (u,v),(u^{\prime},v^{\prime})\in V(G)\times V(H) determine an edge in G\boxempty H if and only if u=u^{\prime} and vv^{\prime}\in E(H) or uu^{\prime}\in E(G) and v=v^{\prime} . Such graphs admit a fiber structure that is frequently helpful for constructing embeddings and minors. A complete classification of planar Cartesian products was given by Behzad and Mahmoodian [ 2 ] and a proof can be found in [ 5 , Section 4.1] . Let P_{m} represent a path on m vertices and let C_{n} represent a cycle on n\geq 3 vertices. Then their work shows that G\boxempty H is planar if and only if G\boxempty H is either a P_{m}\boxempty P_{n} , P_{m}\boxempty C_{n} , or G\boxempty P_{2} , where G is outerplanar , meaning there exists an embedding of G in the plane where all of the vertices of G lie on the boundary of a single face. The straightforward classification of planar Cartesian products and the fact that \Forb(N_{1}) is complete motivates the need for a classification of Cartesian products of graphs that are projective planar. Our main theorem, which is stated below, provides such a classification. For visuals of graphs B_{m} , Q_{m} , W_{m} , and X_{m} , see Figure 1 . We assume all graphs under consideration for this classification and the remainder of this paper are finite, simple, connected, and non-trivial (in the sense of being nonempty and not a single vertex), unless otherwise noted. Theorem 1.1 . The Cartesian product G\boxempty H is projective planar if and only if either (1) G\boxempty H is planar, (2) G\boxempty H=K_{1,3}\boxempty K_{1,3} , (3) G\boxempty H=G\boxempty P_{3} where G is a minor of B_{m} or Q_{m} for some m\in\mathbb{N} , or (4) G\boxempty H=G\boxempty C_{3} where G is a minor of W_{m} or X_{m} for some m\in\mathbb{N} . Our work requires a careful analysis of when G\boxempty H is projective planar for low complexity H . In Section 2 , we consider when H=P_{2} and quickly see that G\boxempty P_{2} is projective planar exactly when G\boxempty P_{2} is planar. Most of our work goes into the cases where |V(H)|=3 , which are covered in Section 3 . In these scenarios, there are infinite classes of G\boxempty H that are projective planar and nonplanar. This work first requires us to determine minimal Cartesian products that are nonprojective planar and organize their essential properties. Then, we show that any G\boxempty H that doesn’t have these properties must meet the qualifications of (3) and (4) from Theorem 1.1 , and we construct projective planar embeddings for such graphs. A similar but less complicated analysis goes into Section 4 , where we consider G\boxempty H where each factor has at least four vertices. In this scenario, K_{1,3}\boxempty K_{1,3} is the only projective planar Cartesian product that is nonplanar. The proof of Theorem 1.1 also provides explicit lists of sufficient forbidden minors for when a Cartesian product of graphs embeds in the projective plane. One list consists of the six graphs from the list of 35 forbidden minors in \Forb(N_{1}) that are sufficient for our classification; see Corollary 5.1 and Appendix A . The other set consists of nine Cartesian products that serve as a sufficient set of forbidden minors to classify projective planar Cartesian products; see Corollary 5.4 . Throughout the upcoming sections of the paper, we will reference the six graphs of \Forb(N_{1}) used in our work via the labels given in Appendix A , which correspond with the labels given in [ 8 ] . As noted above, our work requires several explicit constructions of embeddings and minors of Cartesian products of graphs. For these constructions, it frequently helps to use the fiber decomposition of G\boxempty H=(G\times V(H))\cup(V(G)\times H) where G\times V(H)=\bigcup_{h\in V(H)}(G\times\{h\}) and every G\times\{h\} is called a G-fiber . Likewise, V(G)\times H is a union of H-fibers. This characterization says that a Cartesian product of G and H is the union of its G-fibers and H-fibers. Furthermore, any two distinct G-fibers are disjoint, and similarly for H-fibers. While this characterization is not a disjoint union, it is easy to see that the

Read the complete text