Maximal Planarization of Non - Planar Graphs

Abstract

Abstract This paper presents a MAXIMAL - PLANARIZE algorithm using EQUIVELANT - GRAPH procedure . The algorithm proceeds by embedding one or few edges at each stage , without creating nonplanarity of the resultant graph , and to construct a maximal planar subgraph G , of G directly . The present implementation shows that using two planarization algorithms is unnecessary because of their complexities . It runs in linear time to give a maximal planar subgraph and adds the maximum number of edges possible without creating nonplanarity , using only one simple and efficient algorithm .

Keywords

• key words: nonplanar graph
• hamiltonian circuit