The Kuratowski graphs K3,3 and K5 characterize planarity. Counting distinct 2-cell embeddings of these two graphs on orientable surfaces was previously done by Mull (1999) and Mull et al. (2008), using Burnside’s Lemma and automorphism groups of K3,3 and K5, without actually constructing the embeddings. We obtain all 2-cell embeddings of these graphs on the double torus, using a constructive approach. This shows that there is a unique non-orientable 2-cell embedding of K3,3, and 14 orientable and 17 non-orientable 2-cell embeddings of K5 on the double torus, which are explicitly obtained using an algorithmic procedure of expanding from minors. Therefore we confirm the numbers of embeddings obtained by Mull (1999) and Mull et al. (2008). As a consequence, several new polygonal representations of the double torus are presented. Rotation systems for the one-face embeddings of K5 on the triple torus are also found, using exhaustive search.

Abstract Given a 3-uniform hypergraph H having a set V of vertices, and a set of hyperedges $$T\subset \mathcal {P}(V)$$ T ⊂ P ( V ) , whose elements have cardinality three each, a null labelling is an assignment of $$\pm 1$$ ± 1 to the hyperedges such that each vertex belongs to the same number of hyperedges labelled $$+1$$ + 1 and $$-1$$ - 1 . A sufficient condition for the existence of a null labelling of H (proved in Di Marco et al. Lect Notes Comput Sci 12757:282–294, 2021) is a Hamiltonian cycle in its 2-intersection graph. The notion of 2-intersection graph generalizes that of intersection graph of an (hyper)graph and extends its effectiveness. The present study first shows that this sufficient condition for the existence of a null labelling in H can not be weakened by requiring only the connectedness of the 2-intersection graph. Then some interesting properties related to their clique configurations are proved. Finally, the main result is proved, the NP-completeness of this characterization and, as a consequence, of the construction of the related 3-hypergraphs.

For each prime power $n \equiv 1$ (mod 4), a pair of connected graphs on 4n-4 vertices, with reconstruction number at least 2n-1, is constructed.