@



This page is dedicated to Cahit spiral chains. What I’m trying to do is to apply Cahit spiral chains to simplified rectangular maps and then add this tool to the java program I’m writing.

Disclaimer:

  • These are just personal notes about spiral chains. Not being a mathematician, some of the content that I’ll insert here maybe initially wrong. Sorry for that. I’ll fix it if someone will let me notice the error!

Examples

Example: Spiral chains change depending from the starting point. Considering that Tutte’s graph has a rotational simmetry of 120° (pinning the vertex at the center), only three different elaborations in spiral chains will be possible.

Example: This is the spiral chain elaboration for a rectangular map of 30 faces >= F5. If you need to recreate the map within the Java program, type in:

1b+, 20b+, 24b+, 29b+, 27b-, 28b-, 26b-, 24e-, 23b-, 25b-, 21b-, 22b-, 20e-, 17b-, 18b-, 21e-, 19b-, 16b-, 13b-, 7b-, 11b-, 12b-, 10b-, 4b-, 7e-, 9b-, 5b-, 4e-, 2b-, 3b-, 5e-, 6b-, 9e-, 10e-, 8b-, 6e-, 3e-, 11e-, 13e-, 14b-, 16e-, 17e-, 15b-, 14e-, 12e-, 18e-, 15e-, 8e-, 23e-, 22e-, 26e-, 27e-, 25e-, 19e-, 28e-, 29e+, 2e+, 1e+

This is a rectangular map of 12 faces, that has only one spiral:


Notes on the algorithm: identify the spiral chains

A very short way to express the spiraling algorithm is:

  • Start from a vertex on the outer loop
  • Go to the second vertex moving clockwise on the outer loop
  • For all the other vertices of the spiral, always try to turn left
  • If you can’t turn left (because you will end up on a vertex already visited), then turn right
  • If you can’t turn right, it means the spiral terminates here

Rules for the algorithm for the computer (clockwise spirals):

  • Special rules
    • The starting vertex of the first spiral chain has to be on the external cycle of the graph
    • The starting vertex of all other spiral chains, if the previous spiral chain did not cover all vertexes, is the closest vertex to the last vertex of the previous spiral chain
    • For the first move of the first spiral chain, walk on the edge of the external cycle moving clockwise
    • Note: For the first move of the other spiral chains, the direction to choose is forced by the general rules, because one of the edges will surely reach a “used” vertex. This can be proved (but I think is not so trivial to prove) by the way the starting vertex of these spiral chains has been choosen
  • General rules
    • Every time you leave a vertex, mark it as “used” (not to be reached again), meaning also that you cannot walk on an edge that will take you on one of these “used” vertexes
    • To identify the next vertex of the spiral chain, always choose the left-most edge. Remember also to apply the previous rules: if the left-most edge will take you to a vertex that has already be reached (consider also all previous spiral chains), use the other edge at the right
    • Continue until all previous rules can be applied. The spiral chain ends when there is nothing else to do, and all rules will fail

Pseudocode:

spiral chain number = 1
all spiral chains found = false
number of all "used" vertices of the graph = 0

while (all spiral chains found == false) {
  if (spiral chain number == 1)
    move to a random vertex on the external cycle
  }
  else {
    move to the closest unused vertex to the last vertex of the last spiral chain
  }

  spiral chain vertex number = 1
  spiral chain completed = false

  while (spiral chain completed == false) {
    set the vertex as "used"
    set all incident edges as "used"

    if ((spiral chain number == 1) and (spiral chain vertex number == 1)) {
      move to the second vertex of the external cycle clockwise
      number of "used" vertices = number of "used" vertices + 1
    }
    else {
      if (edge at left is not "used") {
        move to the next vertex at the end of the left edge
        number of all "used" vertices of the graph = number of all "used" vertices of the graph + 1
      }
      else if (edge at righ is "used") {
        move to the next vertex at the end of the right edge
        number of all "used" vertices of the graph = number of all "used" vertices of the graph + 1
      }
      else {
        spiral chain completed = true
      }
    }
  }
  if (number of all "used" vertices of the graph == number of vertices of the graph) {
    all spiral chains found = true
  }
  else {
    spiral chain number = spiral chain number + 1
  }
}

See the sourceforge project for the final implementation.


Notes on the algorithm: 3-edge coloring spiral chains (1 spiral chain)

To be finished.


Notes on the algorithm: 3-edge coloring spiral chains (n spiral chains)

To be finished.


Links to external pages, documents and other stuff

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