theorems about planarity the most well-known of these is kuratowski' theorem which states that " finite graph is planar if and only if it does not contain subgraph that is homeomorphic toor subdivision ofk or , anotherbased on the concept of minorsis wagner' theorem which states that " finite graph is planar if and only if it does not have or , as minora good general approach for testing planarity is therefore to search for subgraphs of the given graph that can be transformed into or , this is not entirely straightforwardbut algorithms do exist which allow graph with vertices to be tested for planarity with time complexity (nexercisefind out exactly how these algorithms work traversals systematically visiting all vertices in order to traverse graphi systematically visit all its verticeswe clearly need strategy for exploring graphs which guarantees that we do not miss any edges or vertices becauseunlike treesgraphs do not have root vertexthere is no natural place to start traversaland therefore we assume that we are givenor randomly picka starting vertex there are two strategies for performing graph traversal the first is known as breadth first traversal we start with the given vertex then we visit its neighbours one by one (which must be possible no matter which implementation we use)placing them in an initially empty queue we then remove the first vertex from the queue and one by one put its neighbours at the end of the queue we then visit the next vertex in the queue and again put its neighbours at the end of the queue we do this until the queue is empty howeverthere is no reason why this basic algorithm should ever terminate if there is circle in the graphlike abc in the first unweighted graph abovewe would revisit vertex we have already visitedand thus we would run into an infinite loop (visiting ' neighbours puts onto the queuevisiting that (eventuallygives us cand once we reach in the queuewe get againto avoid this we create second array done of booleanswhere done[jis true if we have already visited the vertex with number jand it is false otherwise in the above algorithmwe only add vertex to the queue if done[jis false then we mark it as done by setting done[jtrue this waywe will not visit any vertex more than onceand for finite graphour algorithm is bound to terminate in the example we are discussingbreadth first search starting at might yieldabdce to see why this is called breadth first searchwe can imagine tree being built up in this waywhere the starting vertex is the rootand the children of each vertex are its neighbours (that haven' already been visitedwe would then first follow all the edges emanating from the rootleading to all the vertices on level then find all the vertices on the level belowand so onuntil we find all the vertices on the 'lowestlevel the second traversal strategy is known as depth first traversal given vertex to start fromwe now put it on stack rather than queue (recall that in stackthe next item to be removed at any time is the last one that was put on the stackthen we take it from the stackmark it as done as for breadth first traversallook up its neighbours one after the otherand put them onto the stack we then repeatedly pop the next vertex from the stackmark it as doneand put its neighbours on the stackprovided they have not been marked as donejust as we did for breadth first traversal for the example discussed abovewe might (starting from agetabced againwe can see why this is called depth first by