Math problem
I have a non-planar graph with 33 nodes and 83 edges.
I would like to represent it on a sheet of paper as almost-planar; that is, minimizing the number of edge crossings. Or equivalently, remove a minimal subset of edges such that the result is planar and I can sketch in the removed edges in a different color (or something).
Are there any algorithms/tools that would do this? The links I'm finding so far just give me a yes/no answer about planarity. One will even rearrange the nodes for me to prove that it's planar but just returns a simple "no" if it fails.
Run time is not a serious concern, though a run time of 2^83 would clearly be a bad idea.
I would like to represent it on a sheet of paper as almost-planar; that is, minimizing the number of edge crossings. Or equivalently, remove a minimal subset of edges such that the result is planar and I can sketch in the removed edges in a different color (or something).
Are there any algorithms/tools that would do this? The links I'm finding so far just give me a yes/no answer about planarity. One will even rearrange the nodes for me to prove that it's planar but just returns a simple "no" if it fails.
Run time is not a serious concern, though a run time of 2^83 would clearly be a bad idea.