A simple recognition of maximal planar graphs
In this paper, we consider the problem of determining whether a given graph is a maximal planar graph or not. We show that a simple linear time algorithm can be designed based on canonical orderings. Our algorithm needs no sophisticated data structure and is significantly easy to implement compared with the existing planarity testing algorithms. (C) 2003 Elsevier B.V. All rights reserved.
maximal planar graph linear time algorithm planarity test triangulated plane graph graph algorithms