A Method to Represent Restricted Classes of Planar Graphs in the Enhanced Spatial Relational Model PLA, Based on Hahn Graphs

In this paper we enhance the PLA relational spatial model for storing a special type of planar graphs. The PLA-model is very handy to store 2-connected planar graphs, but it is not capable at all to store some other important classes of planar graphs: trees and, more generally, planar graphs with cut edges. In this paper we propose a method for their representation. The main idea is based on Halin graphs that are planar graphs of minimum degree 3 from which the removal of the boundary edges of the infinite region yields a tree. Our results are to identify Halin graphs from the model, and to represent trees as virtual Halin graphs in order to store them without major alteration of the original PLA-model