Embedding grid graphs on surfaces

DOI10.1007/S00373-022-02488-WzbMATH Open1486.05203arXiv2104.12270OpenAlexW3158732798MaRDI QIDQ2127724FDOQ2127724

Authors: Christian Millichap, Fabian Salinas 

Publication date: 21 April 2022

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

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.

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

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

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)

Cites Work

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

Cited In (6)

• Title not available (Why is that?)
• Embedding grids in surfaces
• Surface Constructions on Irregular Grids
• Topological surfaces as gridded surfaces in geometrical spaces
• Title not available (Why is that?)
• 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)