Generating maps on surfaces

DOI10.1007/S00454-016-9853-8MaRDI QIDQ517449zbMATH OpenOpenAlexFDO

Authors Thom Sulanke

Publication date 23 March 2017

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

closed 2-cell embeddingirreducible triangulationmapopen 2-cell embeddingpolyhedral embedding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We describe procedures for generating all 2-cell embedded simple graphs with up to a fixed number of vertices on a given surface. We also modify these procedures to generate closed 2-cell embeddings and polyhedral embeddings. We give results of computer implementations of these procedures for seven surfaces: the sphere, the torus, the double torus, the projective plane, the Klein bottle, the triple cross surface, and the quadruple cross surface.

Recommendations

• Generating closed 2-cell embeddings in the torus and the projective plane
• The Enumeration of Maps on the Torus and the Projective Plane
• scientific article; zbMATH DE number 975323
• The construction of cubic maps on orientable surfaces
• Generating projective plane polyhedral maps

Cites work

• All 2-manifolds have finitely many minimal triangulations
• Fast generation of planar graphs
• Generating the triangulations of the projective plane
• Graph minors. VII: Disjoint paths on a surface
• Graphs on surfaces
• scientific article; zbMATH DE number 4024313 (Why is no real title available?)
• scientific article; zbMATH DE number 3509333 (Why is no real title available?)
• Irreducible triangulations of the Klein bottle
• Isomorph-Free Exhaustive Generation
• Note on the irreducible triangulations of the Klein bottle

Cited in

(8)

• Operations on oriented maps
• Generating projective plane polyhedral maps
• The construction of cubic maps on orientable surfaces
• Enumeration and random realization of triangulated surfaces
• The optimal packing of eight points in the real projective plane
• Space-efficient generation of nonisomorphic maps and hypermaps
• Generating maps on oriented surfaces using the homomorphism principle
• Computation of toroidal Schnyder woods made simple and fast: from theory to practice

Describes a project that uses

Uses Software

• plantri
• Surftri

This page was built for publication: Generating maps on surfaces

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