zeldris's blog

Planar graph
By zeldris, history, 6 years ago, In English

Hello everyone

I'm writing a problem for a contest in my college, so I need generate a planar graph. I need to make sure the graph is planar. Is there any trick to generate such graphs?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Kuratowski's theorem gives a sufficient and necessary condition for a graph being planar. I'm unsure though how could you check that.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is a O(n^2) algorithm for detecting if a graph is minor of an other graph. But probably its not something easy to implement for a contest !

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

There is Gamma-algorithm, try to google it, cuz I found only russian tutorial version

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, when I had the problem like this, I used random dots and two treaps. You can connect dots as in a Cartesian tree, then invert priority, and connect dots again. So you have the planar graph in O(N) time.

If you want more edges, I guess it can be done from geometry easily.

→ Reply