Group Abstract Group Abstract

Message Boards Message Boards

The inverse of moving from a map to a network topology

Caveat: this may be more of a math problem than a Mathematica-specific problem, but I thought some in this group might have insight.

A solved problem is moving from a map in which there are districts with boundaries to a representation of that map as a network in which the vertices are the districts and edges represent shared boundaries between districts.

 fr = UndirectedGraph[
   NestGraph[#["BorderingCountries"] &, Entity["Country", "France"], 
    3]]

But what about the inverse problem: how does one move from a network to a map which is consistent with that network. There are likely to be an infinite number of such maps, but how does one even find a single exemplar. I'm thinking this is actually quite a difficult problem, but perhaps some people here might have insight on the matter and how such an exercise might be tackled using Mathematica.

POSTED BY: Seth Chandler
6 Replies

You are right, this method may not create a triconnected graph. I made a mistake. Here's a simple example:

Mathematica graphics

POSTED BY: Szabolcs Horvát

I appreciate the lucid code and explanation. Attached is a file showing that this method, though extremely helpful, may not work perfectly. In particular, it looks as if the IGSmoothen function may not always create a 3-connected graph which, as I understand it, is necessary for this method to work. There is also a substantial possibility that I am misunderstanding the concepts here. Any thoughts appreciated. I can also be reached offline via an email that you can surely figure out or via Wolfram Community,

Attachments:
POSTED BY: Seth Chandler
POSTED BY: Szabolcs Horvát
POSTED BY: Seth Chandler

Oops, it went missing ... I fixed it now.

Keep in mind that this is still a work in progress and there are likely some bugs. Do let me know if you find any problems, no matter how small (either in functionality or documentation).

Also, there is a limitation that's worth pointing out: effectively, only simple graphs are supported (multi-edges are typically ignored). This means that it would be troublesome to work with non-triconnected graphs which have multigraph duals.

POSTED BY: Szabolcs Horvát

What you describe sounds like the "dual graph", possibly excluding the exterior vertex and edges. If so, then the solution is the essentially the same as what you do to go from map to dual: treat vertices as planar faces, and edges as boundaries between those faces. Then use PlanarGraph to draw it.

POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard