Topological inductive constructions for tight surface graphs

DOI10.1007/s00373-022-02557-0zbMath1498.05074arXiv1909.06545OpenAlexW3134432690MaRDI QIDQ2084791

Qays Shakir, Derek Kitson, James Cruickshank, Stephen C. Power

Publication date: 13 October 2022

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

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

zbMATH Keywords

contact graphinductive constructionvertex splittingsparse graphrotation systemtight graphtorus graphcontacts of circular arcs

Mathematics Subject Classification ID

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

Uses Software

• SageMath

Cites Work

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