Handmade Network»Forums
217 posts
How to find a planar embedding of graph and draw it on a grid?

How can I find a planar embedding of a graph and draw it on a grid? I've tried to read some papers on this problem but I still don't get it (I'm not a native speaker and math isn't my strong suit). They're full of weird symbols and hard-to-understand "words". Can someone just give me a quick and simple overview of a couple of algorithms and some easy-to-understand sample code? Or maybe point to some resources (that don't have any weird math symbol).

217 posts
How to find a planar embedding of graph and draw it on a grid?
Replying to Shastic (#25883)

Thanks, will check those out!

I'm experimenting with procedurally generating a level based on an input graph. I need these algorithms to a) know whether a graph is planar or not (I only want to generate from a planar graph) and b) find all the graph's faces and sort it by size.

217 posts
How to find a planar embedding of graph and draw it on a grid?
Replying to Shastic (#25883)

Just spend time reading the "Algorithms for Testing and Embedding Planar Graphs" one and it's pretty interesting. But when the paper went deeper into how a specific algorithm works, I still had no idea what it was saying. I don't know if you've read any of these papers but if you have then can you explain them to me? I just need to know an algorithm.

The first link you sent me was actually a python interface for another repository which I did find some other interesting links in the Readme. I probably spend some more time reading those.

It's just kind of weird that there aren't any great tutorials or videos about these kinds of algorithms.

217 posts
How to find a planar embedding of graph and draw it on a grid?
Replying to Shastic (#25966)

I know the basic stuff about graph theory and all the terminologies here. I also watched your video before. The theorem that you were referring to is the Kuratowski theorem. What I want to know is how to implement these things in C code? What are the algorithms that people usually use? Your video and a lot of other tutorials online are mostly focusing on math rather than computer programming. Is the course that you're watching about programming or math?

217 posts
How to find a planar embedding of graph and draw it on a grid?
Replying to Shastic (#25968)

When you understand the algorithm, you can write the C code.

That's the point. The video you send didn't have any algorithms. She only talks about the theorem and it only states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of k5 or k3,3. The video doesn't tell you how to know if a graph is or isn't a subdivision of k5 or k3,3. It's just a basic introduction to the graph theory which I said that I already know.

There's a tiny bit of math (if you could call it that) to set things up, then they show graphs, then show pseudo code to explain it. When you understand it, you code it in the language of your choice.

Are you talking about the Numberphile video? Or the papers? If it's the video then as I said above it doesn't contain any "pseudo code". If you're talking about the papers then can I ask you a couple of questions about those algorithms?

If you can't find anything on something for games, its because game devs haven't used it.

Not really. I only want to know "How to find a planar embedding of a graph and draw it on a grid" which is a pretty general question in computer science about graph theory. There isn't anything specific to game development. I'm just having a hard time understanding these papers and couldn't find any youtube videos about the topic (there are only videos about basic introduction to graph theory).