In response to increasing Arctic temperatures, ice-rich permafrost landscapes are undergoing rapid changes. In permafrost lowlands, polygonal ice wedges are especially prone to degradation. Melting of ice wedges results in deepening troughs and the transition from low-centered to high-centered ice-wedge polygons. This process has important implications for surface hydrology, as the connectivity of such troughs determines the rate of drainage for these lowland landscapes. In this study, we present a comprehensive, modular, and highly automated workflow to extract, to represent, and to analyze remotely sensed ice-wedge polygonal trough networks as a graph (i.e., network structure). With computer vision methods, we efficiently extract the trough locations as well as their geomorphometric information on trough depth and width from high-resolution digital elevation models and link these data within the graph. Further, we present and discuss the benefits of graph analysis algorithms for characterizing the erosional development of such thaw-affected landscapes. Based on our graph analysis, we show how thaw subsidence has progressed between 2009 and 2019 following burning at the Anaktuvuk River fire scar in northern Alaska, USA. We observed a considerable increase in the number of discernible troughs within the study area, while simultaneously the number of disconnected networks decreased from 54 small networks in 2009 to only six considerably larger disconnected networks in 2019. On average, the width of the troughs has increased by 13.86%, while the average depth has slightly decreased by 10.31%. Overall, our new automated approach allows for monitoring ice-wedge dynamics in unprecedented spatial detail, while simultaneously reducing the data to quantifiable geometric measures and spatial relationships.