Topological inductive constructions for tight surface graphs

DOI10.1007/S00373-022-02557-0zbMATH Open1498.05074arXiv1909.06545OpenAlexW3134432690MaRDI QIDQ2084791FDOQ2084791

Authors: James Cruickshank, Derek Kitson, Qays Shakir, S. C. Power 

Publication date: 13 October 2022

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

Abstract: We investigate properties of sparse and tight surface graphs. In particular we derive topological inductive constructions for $(2,2)$-tight surface graphs in the case of the sphere, the plane, the twice punctured sphere and the torus. In the case of the torus we identify all 116 irreducible base graphs and provide a geometric application involving contact graphs of configurations of circular arcs.

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

Recommendations

• Tight and untight triangulations of surfaces by complete graphs
• Surface embeddability of graphs via homology
• An inductive construction of \((2,1)\)-tight graphs
• scientific article; zbMATH DE number 475589
• On graphs embedded in a surface
• On the connectivity of graphs embedded in surfaces
• SEIFERT SURFACES FOR GRAPHS
• Tight trees and model geometries of surface bundles over graphs
• scientific article; zbMATH DE number 1156577
• Constructions of large graphs on surfaces

zbMATH Keywords

inductive constructionvertex splittingcontact graphsparse graphrotation systemtight graphtorus graphcontacts of circular arcs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Density (toughness, etc.) (05C42) Graph representations (geometric and intersection representations, etc.) (05C62) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Cites Work

• An algorithm for two-dimensional rigidity percolation: The pebble game
• Pebble game algorithms and sparse graphs
• Graphs on surfaces
• A primer on mapping class groups
• Representations by contact and intersection of segments
• Rigidity of Frameworks Supported on Surfaces
• Irreducible quadrangulations of the torus
• The generic rigidity of triangulated spheres with blocks and holes
• Planar minimally rigid graphs and pseudo-triangulations
• Title not available (Why is that?)
• Note on irreducible triangulations of surfaces
• All 2-manifolds have finitely many minimal triangulations
• Algorithms – ESA 2004
• Classes and recognition of curve contact graphs
• Contact Graphs of Circular Arcs
• The rigidity of a partially triangulated torus

Cited In (2)

• Polygon representations of surface graphs
• Tight and untight triangulations of surfaces by complete graphs

Uses Software

• SageMath

This page was built for publication: Topological inductive constructions for tight surface graphs

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