To solve complex problems with long horizons, intelligent agents must be able to create useful temporally extended actions, also known as skills. Graph-based skill discovery methods identify these behaviours by exploiting the connectivity structure of an environment when modelled as a graph. However, it is unclear how best to construct graphs that represent environments with continuous state spaces, and whether the identified skills would be useful. We present a novel algorithm for constructing abstract state transition graphs in continuous-state environments by clustering states within a temporal distance embedding space. This approach enables the application of any graph-based skill-discovery method. We empirically demonstrate that our framework successfully captures underlying environment connectivity and supports the application of diverse graph-based skill discovery algorithms.