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).
I don't know what you would use that for in a game, but I found a couple of interesting links.
https://github.com/hagberg/planarity/blob/master/planarity/src/graphEmbed.c
This one goes through all the different types researchers have tried:
https://richard.myweb.cs.uwindsor.ca/cs510/survey_jiang.pdf
There's some code in this one.
https://www.ecei.tohoku.ac.jp/alg/nishizeki/sub/j/DVD/PDF_J/J054.pdf
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.
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.
I lost interest pretty quick, because I couldn't see where I would use it. The reason I looked at all, is I'm interested in problems graphs are used to solve.
At the moment I'm watching a course on planners, by the University of Edinborgh which is good, so I suggest you look for an online course that covers planar graphs.
This professor likes to talk about them. She mentions a theorem that tells if a graph is not embedable:
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?
When you understand the algorithm, you can write the C code.
Math and computer science are closely related.
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.
"It's just kind of weird that there aren't any great tutorials or videos about these kinds of algorithms."
If you can't find anything on something for games, its because game devs haven't used it. Usually if they find something useful for their games, they blog about it or do lectures at game dev conferences. So perhaps you are searching for the wrong thing?
What do game makers use for procedural level generation?
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).
I found this just now. I hate to post a link to stackoverflow (cringe). The accepted answer might help you, or likely it probably won't. On looking at it, it reminds me of something you might see in a 3D modelling tool.
https://stackoverflow.com/questions/25512321/algorithm-for-a-planar-graph-game
Also this might have something: http://cs.rkmvu.ac.in/~shreesh/media/planarity.pdf
You might be able to figure it out, looking at this C code, which I think you already found above. Lucky it is a BSD license.
https://github.com/graph-algorithms/edge-addition-planarity-suite
"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?"
I was recommending you try to find a proper course on the subject, as they are much easier to understand than just text books. I can't help you understand this subject, because after reading a little about it, I couldn't see how I could put it to use, so my motivation to understand it went away. That github link looks pretty good though, if I was doing it, I would use that, as well as well as check out the other links posted.