http://www.newgrounds.com/portal/vi ew/655010 What kind of

Graph theory basicly. These problems are often linked to computer sience though, with algorithms like depth-first search and width-first search

>>7659927
https://en.wikipedia.org/wiki/Knot_Theory

>>7659927
graph theory. Look at planarity of a graphs and elementary counterexamples (K5, graphs having K5 as a subgraph)

I play with feelings. I at lvl 8 atm :^)

Prop 65 Warning:
This activity may contain a problem known to the state of California to be unsolvable by the means of the greedy algorithm.

>>7659961
>width-first search
At least know the proper terminology if you're going to be a pop-comp-scientist

topological graph theory to be precise

Is that e really needed?

>>7660247
define needed
loops are important sometimes

>>7659962
lol no

>>7660236
This is the correct answer.

The one with bridges and rivers and shit

>>7660292
yes

>>7660155
Might be he has a different native language and translated it directly

>>7659927

There are linear-time planarity testing algorithms. I think some of them might also give you a planar embedding as output (probably as a rotation system)

https://en.wikipedia.org/wiki/Planarity_testing#Algorithms

although if you want to do it by hand it's a bit different.

As some quick heuristics you could do some basic checks like..

If the graph has no triangles, then m <= 2n - 4 and in general m <= 3n - 6 where n = number of vertices and m = number of edges. If your graph doesn't satisfy those, then it's impossible to solve.

if you aren't sure whether it's possible - if you are, just run one of those algorithms on the wiki article I guess.

Wouldn't it be a good idea to find some holes (induced cycles) as the outer plane? I mean you know that in a planar embedding that those have to form regions.

I mean you might end up with less space to work with since you might choose a C_3 as your outer face since those are easy to find induced cycles...


actually scratch that, you wouldn't want induced cycles, you'd want cycles without any paths or chords... so I guess you can't really guarantee much besides triangles without already knowing how it's gonna be embedded?

Okay. Would a good strategy be to find a triangle in the graph with vertices of the highest possible degree, then to just continue to find adjacent triangles to those and embed those close to the edges? Since any C_3 in a graph is going to have to be its own region. I'm on the 4th last level so far by going through a strategy similar to this.

File: last level planar.png (82KB, 1043x1048px) Image search: [Google]

82KB, 1043x1048px

The last level is not possible, is it?

Unless I counted wrong the degree sequence is:
5, 6, 5, 5, 5, 6, 6, 9, 5, 9, 5, 9, 5, 5, 5, 9, 6, 7, 7, 6, 7, 8, 7, 7, 6, 9, 7, 5, 5, 5, 9, 6, 5, 9, 9, 5, 9, 5, 9, 5, 5, 9, 6, 9, 6, 6, 9, 9, 5, 9, 9, 8

which means |V| = 52 and |E| = 176, which violates |E| <= 3|V| - 6

it also violates some other properties regarding vertex degrees of planar graph, in particular the amount of degree <6 vertices with respect to degree >6 vertices.

I mean, maybe i just miscounted or something... but it's pretty far off from meeting those.

giving a non-planar graph for the last level is pretty evil though, so it would make sense...

File: Nerd snip.png (14KB, 628x414px) Image search: [Google]

14KB, 628x414px

>>7659927
I feel like I was nerd snipped

>>7660269
Why would you use it in this case?

>>7661942
I just beat it.

>>7661942

Disregard that, I was counting the closed neighborhoods instead of the open neighborhood, so I guess subtract 1 from each of those degrees. Oops.

File: planar beat.png (66KB, 1050x1056px) Image search: [Google]

66KB, 1050x1056px

>>7661951

see >>7661996

I just beat it too. It was actually easier than the last couple levels since you could just orient a K_3 and then orient other K_3s along the sides of the triangle since the graph was very dense (for a planar graph).

>>7659927
If pic is related then I remember seeing that in the MIT statistics/probability lectures.

FUCK YOU FUCK YOU FUCK YOU WHY DID I START THIS FUCKING SHIT YOU FUCKING FUCK FUCKER

File: Graph.jpg (76KB, 655x662px) Image search: [Google]

76KB, 655x662px

This is where I became too tired.

Basically the strategy is to start with one large triangle and keep putting the nodes one-by-one in place.

>>7659927
Judging by the picture, it looks like it'll have something to do with Graphs and combinatorics.

>>7661063
Really basic knot theory since the lines are all straight. Planar graph theory would be better.

>>7660155
nigga