Vertex-frequency representations can be impractical for applications.

High computational complexity is the main reason for impracticality.

We developed an algorithm for fast calculation of vertex-frequency representations.

We tested it using the windowed graph Fourier transform and the graph S-transform.

A several orders of magnitude decrease in computational complexity is achieved.