Menu
We identified, via a computer search, 143 excluded minors of the spindle surface, the space formed by the identification of two points of the sphere. Per our search, any additional excluded minors must have at least 12 vertices and 28 edges. We also identified 847 topological obstructions for the spindle surface. We conjecture that our lists of excluded minors and topological obstructions are complete.
We say a surface is a compact, connected \(2\)-manifold without boundary, and a pseudosurface is the result after performing a finite number of point identifications (of finitely many points) of one or more surfaces if the resulting space is also connected. The points that have been identified with other points we call the pinchpoints of the pseudosurface. The spindle surface, or pinched sphere, is the pseudosurface, with one pinchpoint, obtained from identifying two points on a sphere. Every surface is also a pseudosurface (with zero pinchpoints).
We say that a graph \(G\) can be embedded in a pseudosurface \(P\) if \(G\) can be drawn in \(P\) such that, if we think of \(G\) as a \(1\)-complex, no two points in \(G\) occupy the same point in \(P\). We say a graph is pinched-planar if it can be embedded in the spindle surface.
We assume basic familiarity with graph theory terminology as found in [1]. If a graph \(H\) can be obtained from \(G\) by deleting edges or vertices, or by suppressing vertices of degree two, we say that \(H\) is a topological minor of \(G\). We say \(H\) is a minor of \(G\) if \(H\) can be obtained from \(G\) by deleting edges or vertices, or by contracting edges. Hence, topological minors are also minors.
If \(G\) embeds in a pseudosurface \(P\), then so does every topological minor of \(G\). We say a pseudosurface \(P\) is minor-closed if for every graph \(G\) that embeds in \(P\), it follows that every minor of \(G\) also embeds in \(P\). It’s easy to see that the spindle surface is minor-closed, but not all pseudosurfaces are. In particular the bananas surface \(B_2\), the pseudosurface created by identifying two spheres at their respective north and south poles, is not minor-closed [2].
We call a graph \(G\) a topological obstruction of a pseudosurface \(P\) if \(G\) does not embed in \(P\) but every proper topological minor of \(G\) does. We say \(G\) is an excluded minor of a minor-closed pseudosurface \(P\) if \(G\) does not embed in \(P\) but every proper minor of \(G\) does. Note that every excluded minor is also a topological obstruction. In fact, each topological obstruction of a minor-closed pseudosurface can be contracted to an excluded minor.
The collection of excluded minors for any minor-closed pseudosurface must be finite by the Robertson-Seymour Theorem [3]. However, the complete collection of excluded minors is known only for two surfaces, the sphere and the projective plane. The set \(\{K_5, K_{3,3}\}\) is the complete collection of both topological obstructions [4] and excluded minors [5] for the sphere. A list of 35 excluded minors and 103 topological obstructions for the projective plane was identified by Glover, Huneke, and Wang [6], and Archdeacon proved their list was complete in [7]. The collection of excluded minors for the torus is not known, but Myrvold and Woodcock have identified 17,535 excluded minors and 250,815 topological obstructions [8]. Mohar and S̆koda have investigated the excluded minors of the torus and Klein bottle of low connectivity [9, 10]. Note that the spindle surface can also be obtained by identifying all points on a given meridian of a torus, from which it follows that any graph that can be embedded on the spindle surface can also be embedded on the torus [11]. Similarly, it can be shown that if a graph embeds in the spindle surface, then it can be embedded in the Klein bottle. (While the spindle surface is a pseudosurface, these manners of constructing it are not done with a finite number of point identifications.)
Research on excluded minors and topological obstructions for pseudosurfaces that are not surfaces has also been conducted. Archdeacon and Bonnington in [12] found the complete list of the \(21\) cubic topological obstructions of the spindle surface. S̆irán̆ and Gvozdiak showed that \(B_2\) has infinitely many topological obstructions [13], and with Bodendiek, Gvozdjak and Širáň they identified the 82 which have connectivity at most two [14]. In [15], Boza, Dávila, Fedriani, and Moyano demonstrated an infinite family of pseudosurfaces, each with infinitely many topological obstructions. A graph \(G\) is outer-embeddable in a pseudosurface \(P\) if there is an embedding of \(G\) in \(P\) with all vertices on the boundary of a single face. Boza, Fedriani, and Núñez in [16] showed that, in general, the problem of a graph’s outer-embeddability in a pseudosurface is NP-complete. In [17], they showed that the set of outer-embeddable graphs in \(B_2\) is minor-closed, and they produced a complete list of the \(38\) minor-minimal graphs that are not outer embeddable in \(B_2\). In [18], the same authors explore a weakened notion of outer-embeddabilty in pseudosurfaces arising from three spheres.
Types of embeddings and embeddability of graphs in pseudosurfaces from algebraic perspectives have also received interest [19, 20, 21].
A graph \(G\) is apex if deleting some vertex makes it planar, or if \(G\) is itself planar. If a graph is embedded in the spindle surface, then deleting the vertex (if any) at the pinchpoint gives a plane graph. So pinched-planar graphs are apex. Apex graphs have received considerable attention, for example [22, 23], but their list of excluded minors is still unknown. We find pinched-planar graphs to be an interesting minor-closed subclass of apex graphs that are embeddable in both the torus and the Klein bottle for which the problem of finding the excluded minors appears tractable.
Our contribution is the following: through a computer search, we have identified 143 excluded minors and 847 topological obstructions for the spindle surface. We conjecture that the list of excluded minors is complete. If correct, our conjecture would answer a question of Archdeacon [24 Problem 6.5]. Our results may be of interest to researchers interested in excluded minors for classes of graphs that are close to being planar [25, 26].
From now on, we will work exclusively with the following reformulation of embeddability in the spindle surface.
Proposition 1. Any planar graph is pinched-planar. A non-planar graph is pinched-planar if and only if it can be obtained by identifying two vertices of a planar graph.
Sketch of Proof:. The vertex created by the identification of the two selected vertices of a graph embedded in the sphere is embedded at the pinchpoint of the spindle surface. ◻
We make essential use of [11 Theorem 2], which we rephrase for our purposes.
Theorem 1. [11 Theorem 2]A graph is a topological obstruction of the spindle surface if and only if the following three conditions hold:
\(G\) is not pinched-planar,
the minimum degree of \(G\) is at least three, and
the graph \(G-e\) is pinched-planar for each edge \(e\) of \(G\).
We call a graph Kuratowski if it is a subdivision of \(K_5\) or \(K_{3,3}\). We denote the disjoint union of graphs \(G\) and \(H\) by \(G\ \dot{\cup}\ H\). Identifying a vertex of \(G\) with that of \(H\) gives a \(1\)-sum of \(G\) and \(H\). If \(G\) and \(H\) are vertex-transitive, they have a unique \(1\)-sum, up to isomorphism, which we denote by \(G \bigoplus_1 H\).
It is easy to give a complete description of topological obstructions and excluded minors of connectivity less than two. In fact, these are the same as for the torus [8 Figure 7].
Theorem 2. There are three disconnected excluded minors for the spindle surface: \(K_5 \dot{\cup} K_5\), \(K_5 \dot{\cup} K_{3,3}\), and \(K_{3,3} \dot{\cup} K_{3,3}\).
Proof. That these three graphs are excluded minors is easily checked. Let \(G\) be a disconnected excluded minor for the spindle surface. If some component of \(G\) were planar, then deleting it would give a pinched-planar graph with an embedding in the spindle surface containing a face in which the planar component could itself be embedded. So every component of \(G\) is nonplanar and hence has either a \(K_5\)– or \(K_{3,3}\)-minor. By minimality in the minor order, \(G\) must have exactly two components and must be either \(K_5 \dot{\cup} K_5\), \(K_5 \dot{\cup} K_{3,3}\), or \(K_{3,3} \dot{\cup} K_{3,3}\). ◻
By considering blocks and vertex identifications instead of components and disjoint unions, one can show the following result.
Theorem 3. There are three excluded minors of connectivity one for the spindle surface: \(K_5 \bigoplus_1 K_5\), \(K_5 \bigoplus_1 K_{3,3}\), and \(K_{3,3} \bigoplus_1 K_{3,3}\).
There are no more disconnected topological obstructions, but seven additional topological obstructions are obtained by performing \(1\)-sum operations on Kuratowski graphs.
We write \(V(G)\) for the vertex-set of a graph \(G\) and \(E(G)\) for the edge-set. For \(v\in V(G)\), we write \(d(v)\) for the degree of \(v\), and \(N(v)\) for the neighborhood of \(v\). To facilitate our use of Proposition 1, we introduce a definition.
Definition 1. Given a simple graph \(G\) with vertex \(v\) and a subset \(S\) of \(N(v)\), we define the split of \(G\) on \(v\) by \(S\), denoted \(G_{v|S}\), as the graph that results from the following steps:
add a new vertex, say \(w\), to \(G\), and
for each \(x\in S\), delete edge \(vx\) but add edge \(wx\).
So a graph \(G\) is pinched-planar if and only if some split \(G_{v|S}\) is planar. A naive algorithm for testing embeddability for the spindle surface is to test every split \(G_{v|S}\) for planarity.
We optimized this naive algorithm somewhat although ours still has exponential running time. We give pseudocode for our algorithm in Algorithm 1. First note that if \(|S| = 0\), then \(G_{v|S}\) is obtained from \(G\) by adding an isolated vertex. So in this case, \(G\) is planar if and only if \(G_{v|S}\) is. Next, notice that if \(|S|=1\), then \(G_{v|S}\) is obtained from \(G\) by deleting an edge \(e\) incident to \(v\), then adding a vertex of degree one adjacent to the other vertex incident to \(e\). In this case, \(G_{v|S}\) is planar if and only if \(G-e\) is planar. Finally, notice that, by symmetry, a split \(G_{v|S}\) is isomorphic to \(G_{v|N(v)-S}\), so we need only test the splits corresponding to half the subsets \(S\) of \(N(v)\) for planarity.
To test if a graph \(G\) is
pinched-planar we first test \(G\) for
planarity using the Boyer-Myrvold test [27], as implemented in nauty
version 2.7r1 [28]. If
\(G\) is planar, it is also
pinched-planar. If \(G\) is non-planar,
then we request a Kuratowski subgraph, say \(K\), of \(G\). We need only test splits on vertices
in \(V(K)\) for planarity since \(K\) is a subgraph of any split \(G_{x|S}\), where \(x \not\in V(K)\). Likewise, we need only
test deletions \(G-e\), where \(e \in E(K)\), for planarity.
Algorithm 1 Testing a graph G for embeddability in the spindle surface
if \(G\) is planar
return True
else
\(K\) \(\gets\) a Kuratowski subgraph of \(G\)
for each \(e \in E(K)\)
if \(G-e\) is planar
return True
end if
end for
for each \(v \in V(K)\)
for each \(S \subseteq N(v)\) with \(2 \le |S| \le d(v)-2\), where \(G_{v|N(v)-S}\) has not been tested
if \(G_{v|S}\) is planar
return True
end if
end for
end for
return False
end if
The planarg program from nauty* either indicates that a graph is
planar or, if not, produces a Kuratowsi subgraph. Using
planarg as a starting point, we implemented our algorithm
in the C programming language. Our source code is available at [29].
Testing whether a graph is a topological obstruction for the spindle surface is straightforward, and we optimized slightly by suppressing vertices of degree two after deleting an edge. Testing whether a graph is an excluded minor is also straightforward, but we did optimize slightly by deleting any multiple edges that arose from contracting an edge.
Given our observations above, to search exhaustively for topological obstructions on \(n\) vertices and \(m\) edges, we need search only the \(2\)-connected graphs with minimum degree at least three.
To search exhaustively for excluded minors on \(n\) vertices and \(m\) edges, we need only search the topological obstructions we previously found. Moreover, we can narrow the search space by considering that pinched-planar graphs are sparse in that the number of edges is linear in terms of the number of vertices. More specifically, since a simple planar graph on \(n \ge 3\) vertices has at most \(3n-6\) edges, a simple pinched-planar graph on \(n \ge 2\) vertices has at most \(3n-3\) edges. So any topological obstruction for the spindle surface on \(n\) vertices has at most \(3n-2\) edges. Since the minimum degree of a topological obstruction must be at least three, a topological obstruction on \(n\) vertices must have between \(\lceil 3n/2 \rceil\) and \(3n-2\) edges. For example, any topological obstruction for the spindle surface on 11 vertices must have between 17 and 31 edges.
The geng program of nauty can be used to
generate all non-isomorphic graphs on a small number of vertices and
edges, perhaps subject to additional constraints such as connectivity or
minimum degree. We used geng to generate all \(2\)-connected graphs with minimum degree at
least three on \(n \le 11\) vertices or
with \(m \le 27\) edges. We also
generated all such graphs with 12 vertices and 28 edges. (These totaled
roughly 50 billion graphs.) We then used our algorithm to check whether
each generated graph was a topological obstruction, and, finally, we
checked which topological obstructions were excluded minors. We used GNU
Parallel [31] to
parallelize the search. Our computations took roughly two months using
four multi-core computers.
We found 143 excluded minors and 847 topological obstructions. See Tables 1 and 2 and Appendices 1 and 2. We summarize our results in the following theorems.
| \(n\backslash m\) | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | total | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 6 | 1 | 1 | ||||||||||||||
| 7 | 2 | 2 | ||||||||||||||
| 8 | 3 | 1 | 2 | 1 | 7 | |||||||||||
| 9 | 1 | 2 | 5 | 4 | 7 | 4 | 1 | 24 | ||||||||
| 10 | 1 | 4 | 7 | 18 | 21 | 4 | 2 | 1 | 58 | |||||||
| 11 | 5 | 17 | 5 | 8 | 1 | 1 | 37 | |||||||||
| 12 | 3 | 2 | 2 | 4 | 1 | 1 | \(\ge{13}\) | |||||||||
| 13 | 1 | \(\ge{1}\) | ||||||||||||||
| total | 8 | 0 | 6 | 20 | 42 | 35 | 23 | 6 | 2 | 1 | 0 | 0 | 0 | \(\ge{143}\) |
| \(n\backslash m\) | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | total |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 6 | 1 | 1 | ||||||||||||
| 7 | 2 | 2 | ||||||||||||
| 8 | 3 | 2 | 1 | 2 | 1 | 9 | ||||||||
| 9 | 1 | 4 | 3 | 5 | 4 | 12 | 4 | 1 | 34 | |||||
| 10 | 1 | 1 | 13 | 16 | 35 | 29 | 30 | 3 | 1 | 129 | ||||
| 11 | 1 | 28 | 52 | 81 | 38 | 18 | 1 | 1 | 220 | |||||
| 12 | 4 | 50 | 84 | 58 | 21 | 10 | 2 | 1 | \(\ge 230\) | |||||
| 13 | 27 | 60 | 21 | 13 | 1 | 2 | \(1\) | \(\ge 125\) | ||||||
| 14 | 10 | 46 | 3 | 8 | 1 | \(\ge 68\) | ||||||||
| 15 | 19 | 1 | 3 | \(\ge 23\) | ||||||||||
| 16 | 6 | \(\ge 6\) | ||||||||||||
| total | 8 | 7 | 17 | 53 | 142 | 233 | 202 | 111 | 46 | 19 | 6 | 2 | \(1\) | \(\ge 847\) |
Theorem 4. The 143 graphs in Appendix 1 are excluded minors for the spindle surface. No excluded minor has fewer than 15 edges. Any additional excluded minors must have at least 12 vertices and at least 28 edges.
Theorem 5. The 847 graphs in Appendix 2 are topological obstructions for the spindle surface. No topological obstruction has fewer than 15 edges. Any additional topological obstructions must have at least 12 vertices and 28 edges.
Recall that there are three disconnected excluded minors and three of connectivity one. Our computer search found six excluded minors of connectivity two, 117 of connectivity three, 12 of connectivity four, and two of connectivity five. That we found no excluded minors of higher connectivity is perhaps not surprising since Lipton et al. showed that an excluded minor for the class of apex graphs has connectivity at most five [32].
As a sanity check, we also searched all cubic graphs on \(n \le 24\) vertices and found precisely the topological obstructions in [12]. We point out that 125 of the 143 excluded minors and 701 of the 847 topological obstructions we found are apex graphs. We note that \(K_6\), the Petersen graph, and the five other members of the Petersen family are excluded minors for the spindle surface.
Based on the fact that there are no excluded minors with \(25\), \(26\), or \(27\) edges, we conjecture that our list of excluded minors is complete.
Finally, we performed an additional computation that shows that if our list of excluded minors is complete, then our list of topological obstructions must also be complete. Given an excluded minor \(G\) of the spindle surface, we describe how to find the set of topological obstructions that contract to \(G\). Note that if \(H\) is a topological obstruction with a set of edges, say \(E\), that contracts to \(G\), then contracting any subset of \(E\) from \(H\) also yields a topological obstruction. Let us call a graph \(G'\) an inverse-contraction of \(G\) if contracting some single edge of \(G'\) gives \(G\). Note that, using the terminology of our Definition 1, any inverse-contraction of \(G\) may be obtained by adding edge \(vw\) to some split \(G_{v|S}\). (Contracting \(vw\) gives \(G\).) The set of all topological obstructions that contract to \(G\) can be found by finding all inverse-contractions of \(G\), discarding any graphs which are not topological obstructions, then finding all inverse-contractions of the remaining graphs, again discarding any graphs which are not themselves topological obstructions, and repeating this process. Since the minimum degree of a topological obstruction is at least three, this procedure must eventually terminate. Performing this procedure on each of our 143 excluded minors resulted precisely in our set of 847 topological obstructions.
We thank the anonymous referees for their helpful comments.