State whether the following statement is TRUE or FALSE: There is a linear-time algorithm for testing the planarity of finite graphs.

GATE 1987 · Discrete Mathematics · Graph Planarity · medium

Answer: A linear-time planarity test exists, so the statement is TRUE.

1. Recall the planarity-testing result: Hopcroft and Tarjan (1974) gave an O(V + E) algorithm that decides whether a graph is planar; Booth-Lueker (PQ-trees) and the left-right/Boyer-Myrvold methods are also linear time.
2. Why O(V + E) is effectively linear here: for the planar case E = O(V), so the test is O(V); for non-planar inputs the algorithm halts early once a forbidden structure appears.