Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.07347 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916814100889600 |
|---|---|
| author | Metzger, Alexander Ulrigg, Austin |
| author_facet | Metzger, Alexander Ulrigg, Austin |
| contents | We study the problem of determining the minimal genus of a simple finite connected graph. We present an algorithm which, for an arbitrary graph $G$ with $n$ vertices and $m$ edges, determines the orientable genus of $G$ in $O(n(4^m/n)^{n/t})$ steps where $t$ is the girth of $G$. This algorithm avoids difficulties that many other genus algorithms have with handling bridge placements which is a well-known issue. The algorithm has a number of useful properties for practical use: it is simple to implement, it outputs the faces of an optimal embedding, and it iteratively narrows both upper and lower bounds. We illustrate the algorithm by determining the genus of the $(3,12)$ cage (which is 17); other graphs are also considered. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07347 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Efficient Genus Algorithm Based on Graph Rotations Metzger, Alexander Ulrigg, Austin Discrete Mathematics Combinatorics We study the problem of determining the minimal genus of a simple finite connected graph. We present an algorithm which, for an arbitrary graph $G$ with $n$ vertices and $m$ edges, determines the orientable genus of $G$ in $O(n(4^m/n)^{n/t})$ steps where $t$ is the girth of $G$. This algorithm avoids difficulties that many other genus algorithms have with handling bridge placements which is a well-known issue. The algorithm has a number of useful properties for practical use: it is simple to implement, it outputs the faces of an optimal embedding, and it iteratively narrows both upper and lower bounds. We illustrate the algorithm by determining the genus of the $(3,12)$ cage (which is 17); other graphs are also considered. |
| title | An Efficient Genus Algorithm Based on Graph Rotations |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2411.07347 |