A practical algorithm for the computation of the genus

DOI10.26493/1855-3974.2320.C2DMaRDI QIDQ5037919zbMATH OpenOpenAlexFDO

Authors Gunnar Brinkmann

Publication date 29 September 2022

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2005.08243

zbMATH Keywords

backtrackinggenusNP-completeness

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We describe a practical algorithm to compute the (oriented) genus of a graph, give results of the program implementing this algorithm, and compare the performance to existing algorithms. The aim of this algorithm is to be fast enough for many applications instead of focusing on the theoretical asymptotic complexity. Apart from the specific problem and the results, the article can also be seen as an example how some design principles used to carefully develop and implement standard backtracking algorithms can still result in very competitive programs.

Recommendations

• A Symbolic-Numeric Algorithm for Genus Computation
• scientific article; zbMATH DE number 2081135
• An algorithm for computing set-theoretic generators of an algebraic variety
• Approximation algorithms for Euler genus and related problems
• Numerical computation of the genus of an irreducible curve within an algebraic set
• Computing the Krichever genus
• Genus computation of global function fields
• Computing all integer solutions of a genus 1 equation
• scientific article; zbMATH DE number 671746

Cites work

• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Genus of the Cartesian product of triangles
• House of Graphs: a database of interesting graphs
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 1305401 (Why is no real title available?)
• scientific article; zbMATH DE number 3208815 (Why is no real title available?)
• New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces
• On embeddings of circulant graphs
• On the connectivity of graphs embedded in surfaces
• On the genus of \({\mathbb{Z}}_ 3\times {\mathbb{Z}}_ 3\times {\mathbb{Z}}_ 3\)
• Stronger ILPs for the Graph Genus Problem.
• The connectivity of the dual
• The genus of the Gray graph is 7
• The graph genus problem is NP-complete

Cited in

(11)

• House of graphs 2.0: a database of interesting graphs and more
• Genus from sandpile torsor algorithm
• A Symbolic-Numeric Algorithm for Genus Computation
• Local extrema in genus-stratified graphs
• Calculating genus polynomials via string operations and matrices
• Stronger ILPs for the Graph Genus Problem.
• GENOM3CK: a library for genus computation of plane complex algebraic curves using knot theory
• New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces
• Generating maps on oriented surfaces using the homomorphism principle
• An efficient genus algorithm based on graph rotations
• The maximum and minimum genus of a multibranched surface

Describes a project that uses

Uses Software

• House of Graphs
• nauty

This page was built for publication: A practical algorithm for the computation of the genus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5037919)