The two previous posts looked at adjacency networks. The first used examples of US states and Texas counties. The second post made suggestions for using these networks in a classroom. This post is a continuation of the previous post using examples from Japan.

Japan is divided into 8 regions and 47 prefectures. Here is a network diagram of the prefectures in the Kanto region showing which regions border each other. (In this post, “border” will be regions share a large enough border that I was able to see the border region on the map I was using. Some regions may share a very small border that I left out.)

This is a good example of why it is convenient in GraphViz to use variable names that are different from labels. I created my graphs using English versions of prefecture names, and checked my work using the English names. Then after debugging my work I changed the label names (but not the connectivity data) to use Japanese names.

To show what this looks like, my GraphViz started out like this

    graph G {
    layout=sfdp
    AI [label="Aichi"]
    AK [label="Akita"]
    AO [label="Aomori"]
    ...
    AO -- AK
    AO -- IW
    AK -- IW
    ...

and ended up like this

    graph G {
    layout=sfdp
    AI [label="愛知県"]
    AK [label="秋田県"]
    AO [label="青森県"]
    ...
    AO -- AK
    AO -- IW
    AK -- IW
    ...

Here’s a graph only showing which prefectures border each other within a region.

This image is an SVG, so you can rescale it without losing any resolution. Here’s the same image as a PDF.

Because this network is effectively several small networks, it would be easy to look at a map and figure out which nodes correspond to which prefectures. (It would be even easier if you could read the labels!)

Note that there are two islands—literal islands, as well as figurative islands in the image above—Hokkaido, which is its own region, and Okinawa, which a prefecture in the Kyushu region.

Here’s the graph with all bordering relations, including across regions.

The image above is also an SVG. And here’s the same image as a PDF.

In the previous post I looked at graphs created from representing geographic regions with nodes and connecting nodes with edges if the corresponding regions share a border.

It’s an interesting exercise to recover the geographic regions from the network. For example, take a look at the graph for the continental United States.

It’s easy to identify Alaska in the graph. The node on the left represents Maine because Maine is the only state to border exactly one other state. From there you can bootstrap your way to identifying the rest of the states.

Math class

This could make a fun classroom exercise in a math class. Students will naturally come up with the idea of the degree of a node, the number of edges that meet that node, because that’s a handy way to solve the puzzle: the only possibilities for a node of degree n are states that border n other states.

This also illustrates that networks preserve topology, not geometry. That is, the connectivity information is retained, but the shape is dramatically different.

Geography class

Someone asked me on Twitter to make a corresponding graph for Brazil. Mathematica, or at least my version of Mathematica, doesn’t have data on Brazilian states, so I made an adjacency graph using GraphViz.

Labeling the blank nodes is much easier for Brazil than for the US because Brazil has about half as many states, and the topology of the graph gives you more to work with. Three nodes connect to only one other node, for example.

Here the exercise doesn’t involve as much logic, but the geography is less familiar, unless of course you’re more familiar with Brazil than the US. Labeling the graph will require staring at a map of Brazil and you might accidentally learn a little about Brazil.

GraphViz

The labeled version of the graph above is available here. And here are the GraphViz source files that make the labeled and unlabeled versions.

The layout of a GraphViz file is very simple. The file looks like this:

    graph G {

        layout=sfdp

        AC [label="Acre"]
        AL [label="Alagoas"]
        ...
        AC -- AM
        AC -- RO
        ...
    }

There are three parts: a layout, node labels, and connections.

GraphViz has several layout engines, and the sfdp one matched what I was looking for in this case. Other layout options lead to overlapping edges that were confusing.

The node names AC, AL, etc. do not appear in the output. They’re just variable names for your convenience. The text inside the label is what appears in the final output. I’ll give an example in the next post in which it’s very convenient for the variables to be different from the labels. The order of the labels doesn’t matter, only which variables are associated with which labels.

Finally, the lines with variables separated by dashes are the connection data. Here we’re telling GraphViz to connect node AC to nodes AM and RO. The order of these lines doesn’t matter.

Related posts

• Star Wars Master-Apprentice graph
• Mathematical genealogy
• Traveling salesman tours of North and South America

This is the final post in a series of three posts about shortest tours, solutions to the so-called traveling salesmen problem.

The first was a tour of Africa. Actually two tours, one for the continent and one for islands. See this post for the Mathematica code used to create the tours.

The second was about the Americas: one tour for the North American continent, one for islands, and one for South America.

This post will look at Eurasia and Oceania. As before, I limit the tours to sovereign states, though there are disputes over which regions are independent nations. I first tried to do separate tours of Europe and Asia, but this would require arbitrarily categorizing some countries as European or Asian. The distinction between Asia and Oceania is a little fuzzy too, but not as complicated.

Oceania

Here’s a map of the tour of Oceania.

Here’s the order of the tour:

1. Australia
2. East Timor
3. Indonesia
4. Palau
5. Papua New Guinea
6. Micronesia
7. Marshall Islands
8. Nauru
9. Solomon Islands
10. Vanuatu
11. Fiji
12. Tuvalu
13. Kiribati
14. Samoa
15. Tonga
16. New Zealand

The total length of the tour is 28,528 kilometers or 17,727 miles.

Eurasia

Here’s a map of the the Eurasian tour.

Here’s the order of the tour:

1. Iceland
2. Norway
3. Sweden
4. Finland
5. Estonia
6. Latvia
7. Lithuania
8. Belarus
9. Poland
10. Czech Republic
11. Slovakia
12. Hungary
13. Romania
14. Moldova
15. Ukraine
16. Georgia
17. Armenia
18. Azerbaijan
19. Turkmenistan
20. Uzbekistan
21. Afghanistan
22. Pakistan
23. Tajikistan
24. Kyrgyzstan
25. Kazakhstan
26. Russia
27. Mongolia
28. China
29. North Korea
30. South Korea
31. Japan
32. Taiwan
33. Philippines
34. East Timor
35. Indonesia
36. Brunei
37. Malaysia
38. Singapore
39. Cambodia
40. Vietnam
41. Laos
42. Thailand
43. Myanmar
44. Bangladesh
45. Bhutan
46. Nepal
47. India
48. Sri Lanka
49. Maldives
50. Yemen
51. Oman
52. United Arab Emirates
53. Qatar
54. Bahrain
55. Saudi Arabia
56. Kuwait
57. Iran
58. Iraq
59. Syria
60. Lebanon
61. Jordan
62. Israel
63. Cyprus
64. Turkey
65. Bulgaria
66. North Macedonia
67. Serbia
68. Bosnia and Herzegovina
69. Montenegro
70. Albania
71. Greece
72. Malta
73. Italy
74. San Marino
75. Croatia
76. Slovenia
77. Austria
78. Liechtenstein
79. Switzerland
80. Monaco
81. Andorra
82. Spain
83. Portugal
84. France
85. Belgium
86. Luxembourg
87. Germany
88. Netherlands
89. Denmark
90. United Kingdom
91. Algeria

The total length of the tour is 61,783 kilometers or 38,390 miles.