A characterization of the minimalbasis of the torus (Q1087550)

Let S be a closed surface and \(>\) a pre-order on the set \(\Gamma\) (of isomorphism types) of graphs not embeddable in S. The minimal basis \(M(S,>)\) of \(\Gamma\) is the subset of \(\Gamma\) consisting of all graphs minimal with respect to the pre-order \(>\). In the paper to particular pre-orders are considered: \(>_ 1\), the familiar topological containment \((H>_ 1G\) iff H contains a subdivision of G) and \(>_ 4\) whose definition is too involved to be repeated here. It is worth noting, however, that \(M(S,>_ 4)\subseteq M(S,>_ 1)\), \(M(plane,>_ 1)=\{K_{3,3},K_ 5\}\) and \(M(plane,>_ 4)=\{K_ 5\}\). The authors first prove that for an orientable surface \(S_ p\) of genus p the genus of any graph \(G\in M(S_ p,>_ 4)\) is \(p+1\) and its non-orientable genus q satisfies the inequalities \(1\leq q\leq 2(p+1)\). Then a characterization of graphs of M(torus,\(>_ 1)\) with \(q=1\) is given. Furthermore 19 graphs of \(M(torus,>_ 4)\) are exhibited. It is shown that five of them have non-orientable genus \(q=1\), ten of them have \(q=2\), and four of them have \(q=3\). It is not known whether there are graphs in \(M(torus,>_ 4)\) with \(q=4\). Using the minimal basis M(projective plane,\(>_ 4)\) of [\textit{R. Bodendiek, H. Schumacher} and \textit{K. Wagner}, Die Minimalbasis der Menge aller nicht in die projektive Ebene einbettbaren Graphen. J. Reine Angew. Math. 327, 119-142 (1981; Zbl 0454.05024)] the graphs of \(M(torus,>_ 4)\) with \(q=2\) are characterized. This result is then applied to construct another graph of \(M(torus,>_ 4)\). The list of the 20 minimal graphs does not seem to be complete, however, it is believed that it should contain about 25 graphs.