How to ensure that MorphologicalGraph produces a planar graph?

Question

MorphologicalGraph can produce a graph from an image. Such graphs should always be planar, but if the pixel structure has a certain unfortunate shape, then MorphologicalGraph will produce something that is not planar in the strict sense, causing trouble down the analysis pipeline (such as identifying faces and finding the dual graph).

Here's an example:

im = Image[{
   {0, 1, 0, 0, 0, 1, 0},
   {0, 0, 1, 0, 0, 1, 0},
   {0, 0, 0, 1, 1, 0, 0},
   {0, 0, 0, 1, 1, 0, 0},
   {0, 0, 1, 0, 0, 1, 0},
   {0, 1, 0, 0, 0, 0, 1}
  } , "Bit"];

This is the graph we get:

MorphologicalGraph[im]

Technically this is a planar graph, through this particular drawing of it is not. However, if we connected the four corner vertices with a cycle, it would no longer be planar. This simple example is just to illustrate the situations that cause non-planarity, or derail face identification.

Question: What practical ways are there to avoid this situation and get a graph without edge crossings from an image?

---

To illustrate the applications better, I work with images similar to this:

(source)

Answer 1

This is only a start, but I need to write this down, because otherwise it bugs me the whole weekend. The main reason why this happens is two-fold. Firstly, the thinning algorithm is not perfect and in situations like the first example of Szabolcs, the 2x2 box in the middle is kept because with simple morphological operations it is not possible to thin this further without changing the connectivity.

This is the reason that when you try to find the branch-points in this image, you get not a point, but the complete inner 2x2 box

im = Image[{{0, 1, 0, 0, 0, 1, 0}, {0, 0, 1, 0, 0, 1, 0}, {0, 0, 0, 1,
      1, 0, 0}, {0, 0, 0, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0}, {0, 1, 
     0, 0, 0, 0, 1}}, "Bit"];
MorphologicalTransform[im, "SkeletonBranchPoints", Padding -> 0]

In itself, this is basically (a very cautious basically) not a problem. However, MorpholocialGraph is a bit inconsistent because although the above 2x2 box is one branch-point, it regards this as 4 different branch points.

From the image-processing point of view, this is wrong because it is one morphological component. The reason for this inconsistency can be seen in oMorphologicalGraph that you can reach by opening

<< GeneralUtilities`;
PrintDefinitions[MorphologicalGraph]

and clicking through iMorphologicalGraph (somehow, it's not possible to directly open Image`MorpolocigalOperationsDump`oMorphologicalGraph). There, you find the following

vertices = ImageAdd[
  MorphologicalTransform[skeleton, "SkeletonEndPoints", Padding -> 0],
  MorphologicalTransform[skeleton, "SkeletonBranchPoints", Padding -> 0]
];
vertexComponents = Replace[ImageData @ vertices, 1 :> PreIncrement[vertexCount], {2}];

The last line is in its essence a MorpholocicalComponents call that gives each vertex a unique integer-label. However, since it does not take into account that not each pixel is a separate branch-point, even connected pixel get different id's.

We can fix this by doing this on our own and replacing the last line with

vertexComponents = MorphologicalComponents[vertices];
vertexCount = ComponentMeasurements[vertices, "Count"] // Length;

pressing Shift+Enter applies the patch and we can try it out. First the good news

MorphologicalGraph[im]

and it even works on the real example

img = Binarize[Import@"https://i.stack.imgur.com/obndp.png"] // Thinning;
MorphologicalGraph[img]

Here are some places that changed (old -> fixed)

However, there are some disgusting degenerated cases like this one

ImageResize[Import["https://i.stack.imgur.com/Sva6r.png"], {60, 60}, 
   Resampling -> "Nearest"] // Binarize;
MorphologicalGraph[%]

The cycle is ugly, but Szabolcs is surely able to remove it from the graph. When I understood him correctly, then this image should only create one vertex in the center and then, this is definitely an improvement to

My final recommendation is to take the implementation of MorphologicalGraph and work from there. I had suggested in chat to implement the whole procedure manually, but maybe some fixes to the existing code will be enough.

Edit

I found the flaw in the last degenerated example. The branch-point has a hole in it. A better replacement for branch-points in this case is

ImageMultiply[
 FillingTransform[
  MorphologicalTransform[im, "SkeletonBranchPoints", 
   Padding -> 0]], im]

which leads to the center component being

and then the graph will be