DFS Modification

Question

How DFS(Depth First Search) modification is used to find whether a graph is planar or not ?

Comments

I am confused that here linear means O(V) or O(E)..according to above video of prof Shai Simonson , linear means O(V) and in the paper of Hopcraft-Tarjan, they have taken adjacency list. may be that's why it is O(V) because adjacency list is for sparse graphs where E = O(V)...but according to wikipedia , DFS takes linear time in the size of the graph ie O(E)..

---

@ankit

I got that

DFS works for linear time, if it is in place algo, otherwise not

https://cs.stackexchange.com/questions/79934/lower-bound-on-space-of-dfs-keeping-the-running-time-linear

https://arxiv.org/abs/1803.04282

---

@srestha , yes , everywhere ,it is written that DFS/BFS takes linear time ie O(m+n) but I m not getting that it is linear in terms of no. of nodes or no. of edges..because if graph is dense then m = O(n²) then time complexity of dfs becomes O(n²)  which is not linear time in terms of no. of nodes..but in above video , sir said , it takes linear time in terms of no. of nodes..that's why I m confused.

in ur link https://arxiv.org/abs/1803.04282  , they also said O(m+n) as linear time...