3 ms·

This is pretty choice - reminds me of untangling a circuit layout... Never really looked into it that much, but I'd imagine there must be a mathematical techniq

This is pretty choice - reminds me of untangling a circuit layout... Never really looked into it that much, but I'd imagine there must be a mathematical technique that can be applied. My first instinct has always been to put the point with the most connections in the centre, then map out from that.

eru 18y ago
Good luck. The problem may be NP complete in general.
- shrughes 18y ago
  Well, for the cases on planarity.net, it seems O(n) to me. Or maybe something like O(n log n)
  - gjm11 18y ago
    It's O(n) in the general case, so certainly also for the special cases on planarity.net.
    - eru 18y ago
      Could you give me a source or the name of the algorithm, that allows this running time?
      - eru 18y ago
        P.S. I found a O(n) running time for planarity testing - but not embedding.
      - gjm11 18y ago
        The Wikipedia article on planarity testing cites, for instance, this paper: http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf which describes a not-insanely-complicated algorithm that constructs planar embeddings (or proves they don't exist) in linear time.
- deleted 18y ago
  [deleted]
boblol123 18y ago
Take the vertex whose vertices cross the biggest number of other vertices and move it. Repeat until nothing crosses. I remember this problem in maths ages ago, there is a way to know if you can't untangle something- look up the water gas electricity problem
- gjm11 18y ago
  A graph is nonplanar if and only if it has a subgraph that looks like either (1) five vertices all connected to one another or (2) two sets of three vertices, with every vertex in one set connected to every vertex in the other. "Looks like" means: can be turned into by repeatedly replacing -o- (a vertex with two edges coming out of it) with -- (a single edge between the vertex's two old neighbours). See http://en.wikipedia.org/wiki/Planar_graph http://en.wikipedia.org/wiki/Planar_graph for details.

eru 18y ago

Good luck. The problem may be NP complete in general.

shrughes 18y ago
Well, for the cases on planarity.net, it seems O(n) to me. Or maybe something like O(n log n)
- gjm11 18y ago
  It's O(n) in the general case, so certainly also for the special cases on planarity.net.
  - eru 18y ago
    Could you give me a source or the name of the algorithm, that allows this running time?
    - eru 18y ago
      P.S. I found a O(n) running time for planarity testing - but not embedding.
    - gjm11 18y ago
      The Wikipedia article on planarity testing cites, for instance, this paper: http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf which describes a not-insanely-complicated algorithm that constructs planar embeddings (or proves they don't exist) in linear time.
deleted 18y ago
[deleted]

boblol123 18y ago

Take the vertex whose vertices cross the biggest number of other vertices and move it. Repeat until nothing crosses. I remember this problem in maths ages ago, there is a way to know if you can't untangle something- look up the water gas electricity problem

gjm11 18y ago
A graph is nonplanar if and only if it has a subgraph that looks like either (1) five vertices all connected to one another or (2) two sets of three vertices, with every vertex in one set connected to every vertex in the other. "Looks like" means: can be turned into by repeatedly replacing -o- (a vertex with two edges coming out of it) with -- (a single edge between the vertex's two old neighbours). See http://en.wikipedia.org/wiki/Planar_graph http://en.wikipedia.org/wiki/Planar_graph for details.