Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Embedding K3,3 and K5 on the double torus

Gagarin, Andrei ORCID: https://orcid.org/0000-0001-9749-9706 and Kocay, William L. 2024. Embedding K3,3 and K5 on the double torus. Discrete Applied Mathematics 354 , pp. 29-47. 10.1016/j.dam.2023.05.018

[thumbnail of 1-s2.0-S0166218X23001865-main.pdf]
Preview
PDF - Published Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (606kB) | Preview

Abstract

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.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Mathematics
Publisher: Elsevier
ISSN: 0166-218X
Date of First Compliant Deposit: 6 June 2023
Date of Acceptance: 20 May 2023
Last Modified: 03 Jun 2024 09:05
URI: https://orca.cardiff.ac.uk/id/eprint/160199

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics