2025/12/15 by Yufeng Shen, Shen, Yufeng, Song, Zhiyu +5
Computer Science · #05C69 #05C85 #05E45 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2512.12933
openalex publication_date 2025/12/15 · openalex created_date 2025/12/17 · openalex updated_date 2026/07/28
In this paper, we investigate three fundamental problems regarding cut complexes of graphs: their realizability, the uniqueness of graph reconstruction from them, and their algorithmic recognition. We define the parameter m(d,n) as the minimum number of additional vertices needed to realize any d-dimensional simplicial complex on n vertices as a cut complex, and prove foundational bounds. Furthermore, we characterize precisely when a graph on n ≥ 5 vertices is uniquely reconstructible from its 3-cut complex. Based on this characterization, we develop an O(n4) recognition algorithm. These results deepen the connection between graph structure and the topology of cut complexes.