Geodesic
New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces
Ars Mathematica Contemporanea, Tome 17 (2019) no. 1, pp. 1-35.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.1800.40c
Keywords: Graph embedding, genus 
@article{10_26493_1855_3974_1800_40c,
     author = {Marston D. E. Conder and Klara Stokes},
     title = {New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces},
     journal = {Ars Mathematica Contemporanea},
     pages = {1--35},
     publisher = {mathdoc},
     volume = {17},
     number = {1},
     year = {2019},
     doi = {10.26493/1855-3974.1800.40c},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1800.40c/}
}
TY  - JOUR
AU  - Marston D. E. Conder
AU  - Klara Stokes
TI  - New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces
JO  - Ars Mathematica Contemporanea
PY  - 2019
SP  - 1
EP  - 35
VL  - 17
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1800.40c/
DO  - 10.26493/1855-3974.1800.40c
LA  - en
ID  - 10_26493_1855_3974_1800_40c
ER  - 
%0 Journal Article
%A Marston D. E. Conder
%A Klara Stokes
%T New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces
%J Ars Mathematica Contemporanea
%D 2019
%P 1-35
%V 17
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1800.40c/
%R 10.26493/1855-3974.1800.40c
%G en
%F 10_26493_1855_3974_1800_40c
Marston D. E. Conder; Klara Stokes. New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces. Ars Mathematica Contemporanea, Tome 17 (2019) no. 1, pp. 1-35. doi : 10.26493/1855-3974.1800.40c. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1800.40c/

Cité par Sources :