Left Right Planarity testing and Maximal planar subgraph

Abstract

According to our best knowledge, the Left-Right algorithm offers the fastest speed for planarity testing. We show that in finding the Kuratowski K_5 graph, the Left-Right algorithm fails in some cases. We have revised the Left-Right algorithm for the Kuratowski graph with 5 vertices. We further added some features to the Left-Right algorithm to extract the Kuratowski subgraphs. We will discuss the additions to the Left-Right approach and its possible usages.

It is proven that Left-Right (LR) approach is one of the fastest algorithms to find if a graph is planar. We updated the algorithm of LR to extract the Kuratowski subgraphs efficiently. A maximal planar subgraph (G’) of G is a graph with the same vertex set of G and with a minimal set of missing edges from G such that if any removed edge is added to G', the graph becomes non-planar again. If G is planar, then the maximum (maximal) planar subgraph is itself. Otherwise we will discuss how to find the minimum set of edges to be removed to make a graph planar using the updated LR approach.