4 votes 4 votes State whether the following statement is TRUE or FALSE: There is a linear-time algorithm for testing the planarity of finite graphs. Graph Theory gate1987 graph-theory graph-planarity true-false + – makhdoom ghaya asked Nov 9, 2016 • recategorized Apr 22, 2021 by Lakshman Bhaiya makhdoom ghaya 1.4k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply srestha commented May 3, 2018 reply Follow Share https://gateoverflow.in/208494/dfs-modification 0 votes 0 votes shashankrustagi commented Jan 23, 2021 reply Follow Share Havel hakimi : O($n^{2}$) Erdos Gallai : O($n \times log(n)$) So the answer is NO 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes True http://stackoverflow.com/questions/1854711/how-to-check-if-a-graph-is-a-planar-graph-or-not Sayan Das 1 answered Nov 9, 2016 Sayan Das 1 comment Share Follow See all 0 reply Please log in or register to add a comment.