4 ms·

Algorithms for Planar Graphs and Beyond (2011)

71 points by charlysl 8y ago

deleted 8y ago
[deleted]
dmichulke 8y ago
A little bit off-topic but I have a real problem: I sometimes play with my 4 year old son with the Lego Duplo train and I realized that often our tracks have fixed points in the sense that if the train starts at a random track piece and random direction, it eventually arrives at a piece where it cannot - traverse the same piece the other way round - reach all other pieces from the same piece The track consists only of standard 2-ended pieces and junctions with 3 ends ABC where AB or AC is an edge but not BC. In order to come up with a track where the above problems do not arise, I'd like to - formalize the track layout and find a suitable logic (which is not that easy given that AB and AC are edges and therefore BA and CA are edges but it does not follow that: BA & AC => BC, i.e., it's not transitive) - find track layouts where each piece is reachable in either direction from every other piece/direction combination on the track. (I know that an 8 where the middle point consists of 2 connected junctions is such a track) Up to now I have been unable to find anything formal and useful other than trivalent graphs [1] (a dead end) and penrose railway mazes [2] where the problem is just solved on images using search algorithms. [1] https://en.wikipedia.org/wiki/Cubic_graph https://en.wikipedia.org/wiki/Cubic_graph [2] https://demonstrations.wolfram.com/PenrosesRailwayMazes/ https://demonstrations.wolfram.com/PenrosesRailwayMazes/ Can anyone help me?
- ratmice 8y ago
  i'm not sure i understand, but perhaps https://en.wikipedia.org/wiki/Pancyclic_graph https://en.wikipedia.org/wiki/Pancyclic_graph
- harrisongsmith 8y ago
  I think you are on the right track with the figure 8 configuration. I think the two loops are what are important for traversing both directions. I would formally define this loop as follows. (Note: that since these edges are directional I am using "->" to denote these edges.) Definition: Junction Loop Consider an arbitrary junction K with vertices l,m,n such that l->m and l->n. This junction K will contain a loop if there exists a path that connects m->n or n->m. ------------------------------ Defintion: A Dmichulke Track A Dmichulke Track is a track that any piece of track can be traversed in both directions and there exists a path between any two pieces of track ------------------------------- Conjecture: Any track will be a Dmichulke track if it has a two junctions J_1 (with vertices a,b,c such that a->b, a->c) and J_2 ( with vertices x,y,z where x->y and x->z) that satisfy the following conditions. 1) J_1 and J_2 must be have a path connecting vertex a to vertex x 2) J_1 and J_2 must contain a loop. 3) There must exist a path to either of these junctions from any point of the track. ------------------------------- This should satisfy the stated conditions. You should play around with track configurations that satisfy these conditions and see if you can find a counter example. This is only a conjecture though since I didn't really prove anything. I may take a crack at working on that proof over the weekend and let you know how it goes.
theaeolist 8y ago
This may sound snarky but it's actually something I would really like to know: Are there any serious applications of planar graph theory?
- mlevental 8y ago
  tsp on the surface of the Earth?
- charlysl 8y ago
  From https://www.cs.sfu.ca/~ggbaker/zju/math/planar.html https://www.cs.sfu.ca/~ggbaker/zju/math/planar.html connecting utilities (electricity, water, natural gas) to houses. If we can keep from crossing those lines, it will be safer and easier to install. Connecting components on a circuit board: the connections on a circuit board cannot cross. If we can connect them without resorting to another layer of traces, it will be cheaper to produce. Subway system: if subway lines need to cross, we've got some serious engineering to do. Also: The study of two-dimensional images often results in problems related to planar graphs, as does the solution of many problems on the two-dimensional surface of our earth. Many natural three-dimensional graphs arise in scientific and engineering problems. These often come from well-shaped meshes, which share many properties with planar graphs.

71 points by charlysl 8y ago

deleted 8y ago

[deleted]

A little bit off-topic but I have a real problem: I sometimes play with my 4 year old son with the Lego Duplo train and I realized that often our tracks have fixed points in the sense that if the train starts at a random track piece and random direction, it eventually arrives at a piece where it cannot - traverse the same piece the other way round - reach all other pieces from the same piece The track consists only of standard 2-ended pieces and junctions with 3 ends ABC where AB or AC is an edge but not BC. In order to come up with a track where the above problems do not arise, I'd like to - formalize the track layout and find a suitable logic (which is not that easy given that AB and AC are edges and therefore BA and CA are edges but it does not follow that: BA & AC => BC, i.e., it's not transitive) - find track layouts where each piece is reachable in either direction from every other piece/direction combination on the track. (I know that an 8 where the middle point consists of 2 connected junctions is such a track) Up to now I have been unable to find anything formal and useful other than trivalent graphs [1] (a dead end) and penrose railway mazes [2] where the problem is just solved on images using search algorithms. [1] https://en.wikipedia.org/wiki/Cubic_graph https://en.wikipedia.org/wiki/Cubic_graph [2] https://demonstrations.wolfram.com/PenrosesRailwayMazes/ https://demonstrations.wolfram.com/PenrosesRailwayMazes/ Can anyone help me?

ratmice 8y ago
i'm not sure i understand, but perhaps https://en.wikipedia.org/wiki/Pancyclic_graph https://en.wikipedia.org/wiki/Pancyclic_graph
harrisongsmith 8y ago
I think you are on the right track with the figure 8 configuration. I think the two loops are what are important for traversing both directions. I would formally define this loop as follows. (Note: that since these edges are directional I am using "->" to denote these edges.) Definition: Junction Loop Consider an arbitrary junction K with vertices l,m,n such that l->m and l->n. This junction K will contain a loop if there exists a path that connects m->n or n->m. ------------------------------ Defintion: A Dmichulke Track A Dmichulke Track is a track that any piece of track can be traversed in both directions and there exists a path between any two pieces of track ------------------------------- Conjecture: Any track will be a Dmichulke track if it has a two junctions J_1 (with vertices a,b,c such that a->b, a->c) and J_2 ( with vertices x,y,z where x->y and x->z) that satisfy the following conditions. 1) J_1 and J_2 must be have a path connecting vertex a to vertex x 2) J_1 and J_2 must contain a loop. 3) There must exist a path to either of these junctions from any point of the track. ------------------------------- This should satisfy the stated conditions. You should play around with track configurations that satisfy these conditions and see if you can find a counter example. This is only a conjecture though since I didn't really prove anything. I may take a crack at working on that proof over the weekend and let you know how it goes.

theaeolist 8y ago

This may sound snarky but it's actually something I would really like to know: Are there any serious applications of planar graph theory?

mlevental 8y ago
tsp on the surface of the Earth?
charlysl 8y ago
From https://www.cs.sfu.ca/~ggbaker/zju/math/planar.html https://www.cs.sfu.ca/~ggbaker/zju/math/planar.html connecting utilities (electricity, water, natural gas) to houses. If we can keep from crossing those lines, it will be safer and easier to install. Connecting components on a circuit board: the connections on a circuit board cannot cross. If we can connect them without resorting to another layer of traces, it will be cheaper to produce. Subway system: if subway lines need to cross, we've got some serious engineering to do. Also: The study of two-dimensional images often results in problems related to planar graphs, as does the solution of many problems on the two-dimensional surface of our earth. Many natural three-dimensional graphs arise in scientific and engineering problems. These often come from well-shaped meshes, which share many properties with planar graphs.