MURAL - Maynooth University Research Archive Library



    New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces


    Conder, Marston and Stokes, Klara (2019) New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces. Ars Mathematica Contemporanea, 17 (1). pp. 1-35. ISSN 1855-3966

    [img]
    Preview
    Download (434kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    The question of how to find the smallest genus of all embeddings of a given finite connected graph on an orientable (or non-orientable) surface has a long and interesting history. In this paper we introduce four new approaches to help answer this question, in both the orientable and non-orientable cases. One approach involves taking orbits of subgroups of the automorphism group on cycles of particular lengths in the graph as candidates for subsets of the faces of an embedding. Another uses properties of an auxiliary graph defined in terms of compatibility of these cycles. We also present two methods that make use of integer linear programming, to help determine bounds for the minimum genus, and to find minimum genus embeddings. This work was motivated by the problem of finding the minimum genus of the Hoffman-Singleton graph, and succeeded not only in solving that problem but also in answering several other open questions.

    Item Type: Article
    Additional Information: This work is licensed under https://creativecommons.org/licenses/by/4.0/
    Keywords: Graph embedding; genus;
    Academic Unit: Faculty of Science and Engineering > Electronic Engineering
    Item ID: 14074
    Identification Number: https://doi.org/10.26493/1855-3974.1800.40c
    Depositing User: Klara Stokes
    Date Deposited: 24 Feb 2021 17:41
    Journal or Publication Title: Ars Mathematica Contemporanea
    Publisher: Society of Mathematics, Physicists and Astronomers of Slovenia
    Refereed: Yes
    URI:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year