0 votes 0 votes How DFS(Depth First Search) modification is used to find whether a graph is planar or not ? Algorithms depth-first-search algorithms graph-algorithms shai-simonson + – ankitgupta.1729 asked Mar 21, 2018 ankitgupta.1729 1.3k views answer comment Share Follow See all 16 Comments See all 16 16 Comments reply srestha commented Mar 21, 2018 reply Follow Share DFS is not contradictory with any graph and also with planar graph DFS only for checking in a graph , if certain edge is visited or not 0 votes 0 votes ankitgupta.1729 commented Mar 21, 2018 reply Follow Share @Srestha ,Please check here @11:27 https://www.youtube.com/watch?v=i_AQT_XfvD8&index=6&list=PL6ED884C7AEE68027 0 votes 0 votes srestha commented Mar 21, 2018 reply Follow Share ok that concept is about decidability Can check here https://www.sciencedirect.com/science/article/pii/0020019088900488 https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1634&context=cstech 0 votes 0 votes ankitgupta.1729 commented Mar 21, 2018 reply Follow Share @srestha, In the given paper, they explained how to find depth first tree and cyclic separator in the given planar graph.. Here I am asking about if we have a graph then how to find whether it is planar or not using DFS. 0 votes 0 votes srestha commented Mar 21, 2018 reply Follow Share means u want to know, what planer graph is?? 0 votes 0 votes ankitgupta.1729 commented Mar 21, 2018 reply Follow Share @Srestha ,I want to check the planarity of the graph using modified DFS...I got this pdf from internet...page no. 11 https://www.google.co.in/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0ahUKEwis-NHn8vzZAhXLr48KHedZDa8QFgguMAE&url=https%3A%2F%2Fpdfs.semanticscholar.org%2F17f4%2F62dba804c16bb88bda7e4489d71ad1365efa.pdf&usg=AOvVaw1jQtCJzzc3MswEGO9XOrMJ I think , It is not related to GATE bcoz it requires knowledge of palm tree.. 0 votes 0 votes srestha commented Mar 21, 2018 reply Follow Share not in gate but good for some extra knowledge 1 votes 1 votes ankitgupta.1729 commented Mar 21, 2018 reply Follow Share yes :) 0 votes 0 votes ankitgupta.1729 commented May 2, 2018 reply Follow Share @srestha , question was asked in gate 1987 https://gateoverflow.in/80584/gate1987-2e http://bkocay.cs.umanitoba.ca/G&G/articles/Planarity.pdf 1 votes 1 votes srestha commented May 2, 2018 reply Follow Share good notice :) but that is linear time algo 0 votes 0 votes ankitgupta.1729 commented May 2, 2018 reply Follow Share Yes.. Here I also asked the same algo..using DFS, we check the planarity in linear time.. 0 votes 0 votes srestha commented May 2, 2018 reply Follow Share chk it is for biconnected and triconnected component not only for planar Even it's complexity could be $O\left ( m+n \right )$ which could be equal to $O\left (n^{2} \right )$ So, non linear right? 1 votes 1 votes ankitgupta.1729 commented May 2, 2018 reply Follow Share yes , this algo is used to find bi-connected , tri-connected components in a graph and it is also used to check the planarity of a graph.. Here , Linearity means O(E) , not O(V)...DFS takes O(V+E) = O(E) which is linear in terms of no. of edges of the graph and no. of edges represents the size of the graph. So, it is linear in terms of size of the graph. "The time and space analysis of DFS differs according to its application area. In theoretical computer science, DFS is typically used to traverse an entire graph, and takes time Θ(|V| + |E|),[4] linear in the size of the graph." https://en.wikipedia.org/wiki/Depth-first_search 0 votes 0 votes ankitgupta.1729 commented May 2, 2018 reply Follow Share 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).. 0 votes 0 votes srestha commented May 3, 2018 reply Follow Share @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 0 votes 0 votes ankitgupta.1729 commented May 3, 2018 reply Follow Share @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(n2) then time complexity of dfs becomes O(n2) 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... 0 votes 0 votes Please log in or register to add a comment.