Topological inductive constructions for tight surface graphs

DOI10.1007/S00373-022-02557-0MaRDI QIDQ2084791zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(3)

• Polygon representations of surface graphs
• An inductive construction of \((2,1)\)-tight graphs
• Tight and untight triangulations of surfaces by complete graphs

Describes a project that uses

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)