[zackmorris]

For what it's worth, I wrote a small iOS app for a client, to convert isometric 2D line drawings to 3D, and encountered similar complexity issues:

https://itunes.apple.com/us/app/dotpaper-3d/id662561642

My naive implementation ended up being something like O(n!) in the number of lines, due to combinations/permutations. That's because I created a 3D representation as large as the dimensions of the graph that was drawn, and tried arranging the blocks in every possible combination and seeing which one matched the hand drawn lines when projected to 2D.

If each cube in that 3D space represents a bit, then even a 4x4x4 space has 2^64 (18 quintillion) possibilities. So you could draw a few overlapping blocks, but add one more and the iPhone would freeze for several minutes. Add a few more and it wouldn't finish on a human timescale!

I ended up getting around it with a hill climbing algorithm that tried toggling blocks and keeping the result that most closely matched the projection, with a certain amount of fanout up to N entries. It was basically a primitive genetic algorithm. It actually worked great even on relatively large graphs, because humans tend to draw them as a sheet where all of the blocks are next to one another on a diagonal.

It's not perfect and really falls down if a line's out of place (think M.C. Escher) but it's worth playing around with. The client is a teacher, so if you purchase the app, the money will go to a good cause.