Objectives: This study introduces and evaluates GraphTrace, a graph-based method for identifying crime hotspots suitable for CCTV placement. The method addresses key limitations in traditional spatial crime analysis techniques, such as rigid spatial divisions and reliance on heuristics, by dynamically modeling crime clusters with guaranteed distance constraints. Methods: We evaluate GraphTrace using five years of official crime data (N = 125,512) from Malmö, Sweden, and compare its performance against four established spatial methods: Grid+KDE, K-Means, HDBScan, and Greedy PAI Maximization. Each method uses crime data from one year to identify high-crime locations used as suggested CCTV camera placements, which are then evaluated based on their ability to capture crimes occurring within a specified radius in the following year. For example, hotspots identified from 2019 data are assessed against 2020 crime data by counting how many crimes that fall within the radius of each location. Performance is measured using total crime counts and the Predictive Accuracy Index (PAI). Results: GraphTrace significantly outperforms all comparison methods (p<0.05) in terms of both crime capture and PAI. Effect sizes using Cohen’s d range from 0.14 to 1.98, demonstrating up to very large improvements in PAI. Despite its performance, GraphTrace maintains feasible runtimes and scales well. Conclusions: GraphTrace balances precision and computational efficiency by avoiding exhaustive pairwise comparisons while preserving spatial flexibility. Unlike grid-based methods, it does not segment the study area arbitrarily, and unlike many clustering heuristics, it enforces strict distance constraints. This study presents an initial evaluation and open-source implementation of GraphTrace for hotspot detection and CCTV placement, showing strong promise for spatial crime analysis.