I think that's the proper way to go between a graph and its dual, so in theory it works. But for this game there are a couple problems. First, currently the game only allows simple graphs (no loops or parallel edges), so for example you could only have one N-3 connection in your first example.
Even if we'd allow non-simple graphs, the second challenge would be layouting. You might have to connect far away vertices (the N-3 connections go around the whole graph), so making the final graph clean could be difficult. I'm sure algorithms for this exist but sounds like a lot of work for this game.
So, cool idea but maybe it has to be a separate project :) Maybe a game where one graph shows some clues and the dual shows other clues and you have to switch between them to solve it.