A practical algorithm for the computation of the genus

DOI10.26493/1855-3974.2320.c2dzbMath1504.05274arXiv2005.08243OpenAlexW3024750138MaRDI QIDQ5037919

Gunnar Brinkmann

Publication date: 29 September 2022

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

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

zbMATH Keywords

NP-completenessgenusbacktracking

Mathematics Subject Classification ID

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

Related Items (1)

House of graphs 2.0: a database of interesting graphs and more

Uses Software

• nauty
• House of Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Genus of the Cartesian product of triangles
• On the genus of \({\mathbb{Z}}_ 3\times {\mathbb{Z}}_ 3\times {\mathbb{Z}}_ 3\)
• On the connectivity of graphs embedded in surfaces
• House of Graphs: a database of interesting graphs
• The genus of the Gray graph is 7
• On embeddings of circulant graphs
• The graph genus problem is NP-complete
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Stronger ILPs for the Graph Genus Problem.
• New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces
• The connectivity of the dual

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