Embedding grid graphs on surfaces

DOI10.1007/S00373-022-02488-WMaRDI QIDQ2127724zbMATH OpenOpenAlexFDO

Authors Christian Millichap, Fabian Salinas

Publication date 21 April 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

planar graphsgrid graphstoroidal graphsgenus of a graphquadrilateral embeddings

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15)

Abstract: In this paper, we analyze embeddings of grid graphs on orientable surfaces. We determine the genus of a large class of k-dimensional grid graphs and effective two-sided bounds for the genus of any 3-dimensional grid graph, both in terms of a grid graph's combinatorics. As an application, we provide a complete classification of planar and toroidal grid graphs. Our work requires a variety of combinatorial arguments to determine effective lower bounds on the genus of a grid graph, along with explicitly constructing embeddings of grid graphs on surfaces to determine effective upper bounds on their genera.

Recommendations

• Embedding graphs on surfaces
• Embedding grids in surfaces
• On graphs embedded in a surface
• scientific article; zbMATH DE number 432759
• Grid graphs and lattice surfaces
• Embedding digraphs on orientable surfaces
• Graphs on surfaces
• scientific article; zbMATH DE number 5016711
• Embedding a graph-like continuum in a surface
• Surface embedding of \((n,k)\)-extendable graphs

Cites work

• scientific article; zbMATH DE number 3179262 (Why is no real title available?)
• Additivity of the genus of a graph
• Das Geschlecht des vollständigen paaren Graphen
• Embeddings of bipartite graphs
• Genus of cartesian products of regular bipartite graphs
• Genus of the hypercube graph and real moment-angle complexes
• Nonorientable genus of cartesian products of regular graphs
• Orientable and non orientable genus of the complete bipartite graph
• Orientable quadrilateral embedding of products of graphs
• Quadrilateral embeddings of bipartite graphs
• The Genus of Repeated Cartesian Products of Bipartite Graphs
• The Genus of the n-Cube
• The Genus, Regional Number, and Betti Number of a Graph
• The Maximum Genus of Cartesian Products of Graphs
• The maximum genus of graph bundles
• Topics in graph theory. Graphs and their Cartesian product
• Über drei kombinatorische Probleme am \(n\)-dimensionalen Würfel und Würfelgitter

Cited in

(6)

• scientific article; zbMATH DE number 7111090 (Why is no real title available?)
• Embedding grids in surfaces
• Surface Constructions on Irregular Grids
• Topological surfaces as gridded surfaces in geometrical spaces
• scientific article; zbMATH DE number 6783474 (Why is no real title available?)
• The construction of regular grids on \(n\)-dimensional surfaces

This page was built for publication: Embedding grid graphs on surfaces

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