2025/06/17 by Laure Morelle, Morelle, Laure, Evangelos Protopapas +5
Engineering · #Architecture and Computational Design
paper · pdf · doi:10.48550/arxiv.2506.14421
The pinched sphere is the pseudo-surface \mathbbS∘0 obtained by identifying two distinct points of the sphere. We provide a structural characterization of graphs excluding an \mathbbS∘0-embeddable graph as a minor. Given a graph G and a vertex set X, the bidimensionality of X in G is the maximum k such that G contains the (k× k)-grid as an X-rooted minor, i.e., there exists a minor model of the (k × k)-grid in~G such that every branchset of this model contains a vertex of X. We prove that there is a function~f such that, if a graph G excludes an \mathbbS∘0-embeddable graph H as a minor, G has a tree decomposition where each torso Gt contains some set of vertices X, whose bidimensionality in Gt is at most f(k) such that Gt can be reduced to a graph embeddable in the projective plane by identifying vertices from X. This result is optimal in the sense that every graph admitting such a tree decomposition must exclude some \mathbbS∘0-embeddable graph as a minor. An alternative interpretation of this result can be obtained by the fact that edge-apex graphs, i.e., graphs that can be made planar by removing an edge, are graphs embeddable in the pinched sphere. Several consequences and variants of this min-max duality are discussed.