With the Earth’s climate rapidly warming, the Arctic represents one of the most vulnerable regions to environmental change. These northern high latitude regions experience intensified fire seasons and especially tundra fires are projected to become more frequent and severe. Fires in permafrost regions have extensive impacts, including the initiation of thermokarst (rapid thaw of ice-rich ground), as they combust the upper organic soil layers which provide insulation to the permafrost below. Rapid permafrost thaw is, thus, often observable in fire scars in the first years post-disturbance. In polygonal ice-wedge landscapes, this becomes most prevalent through melting ice wedges and degrading troughs. The further these ice wedges degrade, the more troughs will likely connect and build an extensive hydrological network with changing patterns and degrees of connectivity that influences hydrology and runoff. While subsiding troughs over melting ice wedges may host new ponds, an increasing connectivity may also subsequently lead to more drainage of ponds, which in turn can limit further thaw and help stabilize the landscape. To quantify the changes in such dynamic landscapes over large regions, highly automated methods are needed that allow extracting information on the geomorphic state and changes over time of ice-wedge trough networks from remote sensing data. We developed a computer vision algorithm to automatically derive ice-wedge polygonal networks and the current microtopography of the degrading troughs from very high resolution, airborne laserscanning-based digital terrain models. We represent the networks as graphs (a concept from the computer sciences to describe complex networks) and apply methods from graph theory to describe and quantify hydrological network characteristics of the changing landscape. In fire scars, we especially observe rapidly growing networks and fast micromorphological change in those degrading troughs. In our study, we provide a space-for-time substitution comparing fire scars throughout the Alaskan tundra of up to 70 years since the fire disturbance, to show how this type of disturbed landscape evolves over time.