||| T2 |||


Note: 01/Nov/2016:


Theorem:

All regular maps can be topologically transformed into circular maps or rectangular maps.

Stated in terms of graph theory:

3-regular planar graphs can be seen as graphs induced by overlapping axis-oriented opaque rectangles, with the base of each rectangle starting at consecutive y-coordinates. Here is an example that show what I mean by overlapping rectangles:

.

Why I think this result is important:

  • It gives the possibility to approach the problem of coloring maps with 4 colors from a different point of view. Real maps with their different shapes can be really elusive objects to work with. Since, based on this theorem, all maps can be topologically transformed into this more visually “regular” maps, my hope is that the approach to solve the problem will be easier
  • The step by step method used to prove this theorem (T2) for circular maps and rectangual maps, gives also the possibility to use a computer 😦 to create and visualize simplified maps (see T1) with many faces
  • This theorem may also be useful for other areas of investigation in topology, not only for the four color theorem

Proof:

It is straightforward to consider a map as a jigsaw puzzle, if we imagine that the faces that compose the map are the pieces of the puzzle itself. This way to consider maps has the important advantage to imagine the process of transformation from the original map into circular and rectangular maps, as made of consecutive steps (piece after piece construction), as anyone would do with a real jigsaw puzzle.

Now follow these steps.

Start from a region facing the ocean and rebuild the puzzle piece by piece, applying these rules:

  • Always get a piece (a face) confining with one of the pieces already chosen (that are forming the partial map)
  • During the process of rebuilding the entire map, never make holes in the partial map created
    • It is always possible to avoid this situation, since instead of selecting a face that will generate the hole, you can select a face that is in the hole (the hole itself is indeed composed by one or more faces), and that respect the first rule
  • Insert the ocean as the last piece (this is also forced by the second rule)

Every time you select a piece (considering also the first one), you can deform it the way you wish, as long as all the topological properties of the face and the topological properties of the map being created (confining states, order of appearance of neighbors along the edges, etc.) are respected.

Using this building technique, each selected F can be inserted in the map being built, as a section of a circular ring of a larger concentric circle, starting from the inner one. An example of the result of this process along with the original map and the transformed map is shown in the next picture.

Consider for example the face number 4. Detach the piece from the original map, deform it to assume the shape shown in the center of the picture. Now, follow the border of the selected face on the original map clockwise, starting from a point on one the borders of a neighbour not yet chosen (or facing the ocean of the partial map being built – without the face number 5 or above). Walking on this border you will enconter: face number 3 (blu in the example), face number 2 and the face number 1. Just replicate this pattern on the circular map. To do it manually, it is easier to do it on a squared paper and realize directly the rectangular map as shown in the next paragraph.

Following more or less the same procedure explained for circular maps, we can create rectangular maps. This kind of maps can also be created starting from circular maps. Actually it was the way I found rectangular maps! Since, for circular maps, you started from a state facing the ocean, the inner circle (representing the first chosen piece of the jigsaw puzzle) touches the ocean (which is the last chosen piece). For example, if you look at the “A” and “B” points on the next picture, it is easy to see how we can easily deform circular maps into rectangular maps.

Some steps of the construction method for rectangular maps can be seen in this picture, with the small dots representing the vertexes of the map:

Here is a famous graph (Tutte’s map) and the two representations:

Face number 25 surrounding all the other faces on the original map, is the ocean of the rectangular and circular maps.

Same map converted into circular and rectangular (using different colors):

With a little imagination, these kind of maps seem:

  • Rectangular pieces of paper, layered one over the other overlapping
  • The skyline of New York city, made of skyscrapers constructed in order of height, one behind the other. The ocean is all around the city

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s