Back to Search Start Over

Links in projective planar graphs

Authors :
Foisy, Joel
Galván, Luis Ángel Topete
Knowles, Evan
Nolasco, Uriel Alejandro
Shen, Yuanyuan
Wickham, Lucy
Publication Year :
2022

Abstract

A graph $G$ is nonseparating projective planar if $G$ has a projective planar embedding without a nonsplit link. Nonseparating projective planar graphs are closed under taking minors and are a superclass of projective outerplanar graphs. We partially characterize the minor-minimal separating projective planar graphs by proving that given a minor-minimal nonouter-projective-planar graph $G$, either $G$ is minor-minimal separating projective planar or $G \dot\cup K_{1}$ is minor-minimal weakly separating projective planar, a necessary condition for $G$ to be separating projective planar. One way to generalize separating projective planar graphs is to consider type I 3-links consisting of two cycles and a pair of vertices. A graph is intrinsically projective planar type I 3-linked (IPPI3L) if its every projective planar embedding contains a nonsplit type I 3-link. We partially characterize minor-minimal IPPI3L graphs by classifying all minor-minimal IPPI3L graphs with three or more components, and finding many others with fewer components.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2206.05758
Document Type :
Working Paper