zeldris's blog

Planar graph
By zeldris, history, 8 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

»
8 years ago, hide # |
 
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
»
8 years ago, hide # |
← 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
»
8 years ago, hide # |
 
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