# The inverse of moving from a map to a network topology

Posted 3 years ago
4118 Views
|
6 Replies
|
10 Total Likes
|
 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. Answer
6 Replies
Sort By:
Posted 3 years ago
 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. Answer
Posted 3 years ago
 As Daniel said, you want the faces of the planar dual graph.Mathematica's planar graph support is currently pretty limited. But good news: the next version of IGraph/M will have a lot of planar-graph related functionality. Things are a bit in a flux right now, so I haven't done a proper release yet, but you can try everything out in this "beta":https://www.dropbox.com/s/558aq5dynz81huk/IGraphM-0.3.99.92.paclet?dl=0Please email me with any feedback. That will help me polish this functionality before release. Here's a small demo:One issue is that in general there can be multiple, different "maps" corresponding to a graph. The "map" (i.e. the dual) will be uniquely defined if the graph is planar and 3-vertex-connected. More accurately, the map will be unique on a sphere, but not in the plane. In the plane we can choose any face to be the outer face.So, to make our life simple, let's work with 3-connected graphs.First, let's generate a planar graph: < "PlanarEmbedding"] Neither of these are very pretty though. We can get a nicer layout for 3-connected graphs with Tutte's method. IGLayoutTutte[g, VertexShapeFunction -> "Name"] It looks like we could draw a country around any vertex now, but this is not the only way to do lay out the graph. We could choose any face to be the outer face. Here are all the faces: In[]:= IGFaces[g] Out[]= {{2, 8, 9, 16}, {2, 16, 10, 20}, {2, 20, 8}, {4, 10, 16}, {4, 16, 9, 13}, {4, 13, 19, 10}, {8, 20, 10}, {8, 10, 19}, {8, 19, 13, 9}} Here are two more ways to plot it: g1 = IGLayoutTutte[g, VertexShapeFunction -> "Name", "OuterFace" -> {4, 10, 16}] g2 = IGLayoutTutte[g, VertexShapeFunction -> "Name", "OuterFace" -> {2, 8, 9, 16}] Mathematica also has built-in functionality for a Tutte layout, but it does not allow choosing the outer face.The second one is nice, so let's use it to build a map.First, we generate the dual graph: dual = IGDualGraph[g] Each vertex corresponds to a face, including the outer face, in the order returned by IGFaces.We take a particular drawing of g (g2 from above), compute thcentreer of each face, and set is as vertex coordinates for the dual. Then we remove the vertex corresponding to g2's outer face from the dual. dual2 = Graph[dual, VertexCoordinates -> (Mean[GraphEmbedding[g2][[#]]] &) /@ IGFaces@IndexGraph[g], GraphStyle -> "WarmColor"] Show[g2, VertexDelete[dual2, 1 (* the outer face was the first one in g2 *)]] You can see that the map is taking shape. Each vertex of g corresponds to a face of the dual graph, except for the vertices of the outer face of g, i.e. 9, 8, 2, 16.To fix that, we add some infinite half-lines: d = VertexDelete[dual2, 1]; centre = Mean@GraphEmbedding[d]; pts = PropertyValue[{d, #}, VertexCoordinates] & /@ AdjacencyList[dual, 1]; Show[ d, Graphics[{RGBColor[.816, .443, .192], HalfLine[#, # - centre] & /@ pts}] ] And finally, we have the map. Answer
Posted 3 years ago
 This is extremely helpful. What is g2 in the discussion above? Not seeing where you define it. Answer
Posted 3 years ago
 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. Answer
Posted 3 years ago
 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: Answer
Posted 3 years ago
 You are right, this method may not create a triconnected graph. I made a mistake. Here's a simple example:  Answer