3 ms·
Thanks for that link. One thing caught my eye: the algorithm starts with a depth first walk of the graph. Reading that, I thought "that n must be the number of
by Someone 13y ago
Thanks for that link. One thing caught my eye: the algorithm starts with a depth first walk of the graph. Reading that, I thought "that n must be the number of edges". However, theorem 1 in section 6 starts with "Given a graph G with n vertices" and the proof starts with "The depth first search [...] implemented with well-known linear time algorithms."
I don't know that well-known algorithm, and neither does Google, it seems. At least, I can't find it, and can't see how it would work. Now, section 5 has a procedure that requires <= 3n-5 edges for a graph with n vertices. Is that supposed to hold throughout? If so, what's that 3n-5 about? Are there well-known theorems or algorithms to disprove planar it's for such graphs?