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

Author

Novak, A.B. ; Tuza, Zsolt

Author_Institution

Fac. of Inf. Technol., Peter Pazmany Catholic Univ., Budapest

fYear

0

fDate

0-0 0

Firstpage

118

Lastpage

122

Abstract

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

Keywords

relational databases; spatial data structures; tree data structures; trees (mathematics); visual databases; Halin graph; PLA relational spatial model; mathematical tree; planar graph; Automation; Bipartite graph; Computer science; Information technology; Mechanical engineering; Programmable logic arrays; Tree graphs;

fLanguage

English

Publisher

ieee

Conference_Titel

Intelligent Engineering Systems, 2006. INES '06. Proceedings. International Conference on

Conference_Location

London

Print_ISBN

0-7803-9708-8

Type

conf

DOI

10.1109/INES.2006.1689353

Filename

1689353