I've been thinking about doing this for procedurally generated dungeon maps. Basically, randomly add some subset of grid squares, then work out naive as-the-crow-flies connectivity between the closest neighbors to generate the sparse graph.

For straightforward corridor and room maps, each corridor/room object just becomes a node.