Contents

  1. 1. Introduction
  2. 2. Additional Background
  3. 3. Computer Search
  4. Acknowledgments

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

Some Excluded Minors for the Spindle Surface

Thomas J. Savitsky1, Steven A. Schluchter2
1Unaffiliated Reading, PA 19606
2Department of Mathematical Sciences George Mason University 4400 University Drive MS 3F2, Fairfax, VA
  • Received: 11/01/2021
  • Accepted: 16/08/2021
  • Published: 31/03/2024

Abstract

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.

Keywords: excluded minor, topological obstruction, spindle surface, pseudosurface

1. Introduction

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 B2, 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 {K5,K3,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 B2 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 B2 is minor-closed, and they produced a complete list of the 38 minor-minimal graphs that are not outer embeddable in B2. 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].

2. Additional Background

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:

  1. G is not pinched-planar,

  2. the minimum degree of G is at least three, and

  3. the graph G−e is pinched-planar for each edge e of G.

We call a graph Kuratowski if it is a subdivision of K5 or K3,3. We denote the disjoint union of graphs G and H by G ∪˙ 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⨁1H.

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: K5∪˙K5, K5∪˙K3,3, and K3,3∪˙K3,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 K5– or K3,3-minor. By minimality in the minor order, G must have exactly two components and must be either K5∪˙K5, K5∪˙K3,3, or K3,3∪˙K3,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: K5⨁1K5, K5⨁1K3,3, and K3,3⨁1K3,3.

There are no more disconnected topological obstructions, but seven additional topological obstructions are obtained by performing 1-sum operations on Kuratowski graphs.

3. Computer Search

We write V(G) for the vertex-set of a graph G and E(G) for the edge-set. For v∈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 Gv|S, as the graph that results from the following steps:

  1. add a new vertex, say w, to G, and

  2. for each x∈S, delete edge vx but add edge wx.

So a graph G is pinched-planar if and only if some split Gv|S is planar. A naive algorithm for testing embeddability for the spindle surface is to test every split Gv|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 Gv|S is obtained from G by adding an isolated vertex. So in this case, G is planar if and only if Gv|S is. Next, notice that if |S|=1, then Gv|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, Gv|S is planar if and only if G−e is planar. Finally, notice that, by symmetry, a split Gv|S is isomorphic to Gv|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 Gx|S, where x∉V(K). Likewise, we need only test deletions G−e, where e∈E(K), for planarity.

Algorithm 1 Testing a graph G for embeddability in the spindle surface

if G is planar

return True

else

K ← a Kuratowski subgraph of G

for each e∈E(K)

if G−e is planar

return True

end if

end for

for each v∈V(K)

for each S⊆N(v) with 2≤|S|≤d(v)−2, where Gv|N(v)−S has not been tested

if Gv|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≥3 vertices has at most 3n−6 edges, a simple pinched-planar graph on n≥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 ⌈3n/2⌉ 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≤11 vertices or with m≤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.

Table 1: The number of excluded minors for the spindle surface with N vertices and M edges. A Blank entry in the table should be interpreted as a 0. There are no excluded minors with fewer than 15 edges
n∖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 ≥13
13 1 ≥1
total 8 0 6 20 42 35 23 6 2 1 0 0 0 ≥143
Table 2: The number of topological obstructions for the spindle surface with N vertices and M edges. A blank entry in the table should be interpreted as a 0. There are no topological obstructions with fewer than 15 edges
n∖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 ≥230
13 27 60 21 13 1 2 1 ≥125
14 10 46 3 8 1 ≥68
15 19 1 3 ≥23
16 6 ≥6
total 8 7 17 53 142 233 202 111 46 19 6 2 1 ≥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≤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 K6, 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 Gv|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.

Acknowledgments

We thank the anonymous referees for their helpful comments.

References:

  1. Diestel, R. (2017). Graph Theory (5th ed.). Springer.
  2. Knor, M., 1996. Characterization of minor-closed pseudosurfaces. Ars Combinatoria, 43, pp. 246–256.
  3. Robertson, N., and Seymour, P. D., 2004. Graph minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory. Series B, 92(2), pp. 325–357.
  4. Kuratowski, C., 1930. Sur le problème des courbes gauches en Topologie. Fundamenta Mathematicae, 15(1), pp. 271–283.
  5. Wagner, K., 1937. Über eine Eigenschaft der ebenen Komplexe. Mathematische Annalen, 114, pp. 570–590.
  6. Glover, H. H., Huneke, J. P., and Wang, C. S., 1979. 103 graphs that are irreducible for the projective plane. Journal of Combinatorial Theory. Series B, 27(3), pp. 332-370.
  7. Archdeacon, D., 1981. A Kuratowski theorem for the projective plane. Journal of Graph Theory, 5(3), pp. 243–246.
  8. Myrvold, W. and Woodcock, J., 2018. A large set of torus obstructions and how they were discovered. The Electronic Journal of Combinatorics, pp. P1-16.
  9. Mohar, B. and Škoda, P., 2020. Excluded minors for the Klein Bottle I. Low connectivity case. ArXiv preprint arXiv:2002.00258.
  10. Mohar, B., and Škoda, P., 2014. Obstructions of connectivity two for embedding graphs into the torus. Canadian Journal of Mathematics. Journal Canadien de Mathématiques, 66(6), pp. 1327–1357.
  11. Bodendiek, R., and Wagner, K., 1989. The fascination of minimal graphs. In Graph Theory in Memory of G. A. Dirac (Sandbjerg, 1985) (pp. 39–51). North-Holland.
  12. Archdeacon, D., and Bonnington, C. P., 2004. Obstructions for embedding cubic graphs on the spindle surface. Journal of Combinatorial Theory. Series B, 91(2), pp. 229–252.
  13. Širáň, J., and Gvozdjak, P., 1992. Kuratowski-type theorems do not extend to pseudosurfaces. Journal of Combinatorial Theory. Series B, 54(2), pp. 209–212.
  14. Bodendiek, R., Gvozdjak, P., and Širáň, J., 1990. Minimal graphs for 2-amalgamations of spheres. In Contemporary Methods in Graph Theory (pp. 8–25). BI-Wissenschaftsverlag, Mannheim-Zürich-Wien.
  15. Boza, L., Davila, M.T., Fedriani, E.M. and Moyano, R., 2004. On Infinite Kuratowski Theorems. Ars Combinatoria, 7(2), pp. 141-148.
  16. Boza, L., Fedriani, E.M. and Nunez, J., 2004. The problem of outer-embeddings in pseudosurfaces. Ars Combinatoria, 71, pp. 79-91.
  17. Boza, L., Fedriani, E.M. and Nunez, J., 2004. Obstruction sets for outer-bananas-surface graphs. Ars Combinatoria, 73, pp. 65-77.
  18. Boza, L., Fedriani, E.M. and Núñez, J., 2010. Outer-embeddability in certain pseudosurfaces arising from three spheres. Discrete Mathematics, 310(23), pp. 3359-3367.
  19. Abrams, L., snd Slilaty, D. C., 2006. Algebraic characterizations of graph imbeddability in surfaces and pseudosurfaces. Journal of Knot Theory and Its Ramifications, 15(06), pp. 681-693.
  20. Rarity, E., Schluchter, S., and Schroeder, J. Z., 2018. The smallest self-dual embeddable graphs in a pseudosurface. Missouri Journal of Mathematical Sciences, 30(1), pp. 85–92.
  21. Schluchter, S., and Schroeder, J. Z., 2017. Self-dual embeddings of in different orientable and nonorientable pseudosurfaces with the same Euler characteristic. Electronic Journal of Graph Theory and Applications, 5(2), pp. 247–263.
  22. Robertson, N., Seymour, P., and Thomas, R., 1993. Hadwiger’s conjecture for -free graphs. Combinatorica, 13(3), pp. 279–361.
  23. Jobson, A. S., and Kézdy, A. E., 2021. All minor-minimal apex obstructions with connectivity two. Electronic Journal of Combinatorics, 28(1), pp. P1.23, 58.
  24. Archdeacon, D., 2005. Variations on a theme of Kuratowski. Discrete Mathematics, 302(1-3), pp. 22-31.
  25. Ding, G., and Dziobiak, S., 2016. Excluded-minor characterization of apex-outerplanar graphs. Graphs and Combinatorics, 32(2), pp. 583–627.
  26. Ding, G., Fallon, J., and Marshall, E., 2018. On almost-planar graphs. Electronic Journal of Combinatorics, 25(1), pp. P1.55-14.
  27. Boyer, J. M., and Myrvold, W. J., 2004. On the cutting edge: simplified {$O(n)$} planarity by edge addition. Journal of Graph Algorithms and Applications, 8(3), pp. 241–273.
  28. McKay, B. D., and Piperno, A., 2014. Practical graph isomorphism, II. Journal of Symbolic Computation, 60, pp. 94–112.
  29. Savitsky, T.J. and Schluchter, S., https://github.com/tjsavitsky/spindle
  30. Bosma, W., Cannon, J., and Playoust, C., 1997. The Magma algebra system. I. The user language. Journal of Symbolic Computation, 24(3-4), pp. 235–265.
  31. Tange, O., 2011. Gnu parallel‐the command‐line power tool. Usenix Mag, 36(1), p. 42.
  32. Lipton, M., Mackall, E., Mattman, T.W., Pierce, M., Robinson, S., Thomas, J. and Weinschelbaum, I., 2017. Six variations on a theme: almost planar graphs. Involve, a Journal of Mathematics, 11(3), pp. 413-448.
  33. McKay, B. D., http://users.cecs.anu.edu.au/~bdm/data/formats.txt
Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin

1970-2025 CP (Manitoba, Canada) unless otherwise stated.