Planarização de grafos por divisão de vértices

Abstract

Resumo: Essa dissertação tem como tema o estudo de um sub-campo da Teoria dos Grafos conhecida como planarização de grafos. Um grafo planar é aquele que pode ser desenhado em um plano de maneira que não haja cruzamentos de arestas. "Planarizar" um grafo significa transformar um grafo não-planar, através de um numero mínimo de operações, em um grafo planar. O objetivo da dissertação é apresentar o método planarização de grafos por divisão de vértices, método esse, que pode ser considerado novo no leque dos conhecidos e publicados métodos de planarizacao: remoção de vértices ou arestas, particionamento planar ou introdução de vértices dummy. As justificativas para o estudo desse assunto e método podem ser sintetizadas em três pontos: na importância que esse campo de estudo tem para as diversas áreas que se utilizam da representação gráfica para disporem suas informações, tais como projetos de banco de dados e de circuitos integrados; no caráter menos destrutivo desse método de planarização em relação a estrutura original do grafo; e no caráter inédito de sua implementação, até então inexistente. Para atingir-se tal propósito a metodologia abrangeu dois aspectos: a revisão dos conceitos básicos sobre a teoria de grafos e a específica relacionada aos métodos de planarização e a estrutura de dados chamada de árvore-PQ por eles utilizada; e a revisão dos aspectos conceituais do trabalho iniciado na Tese de doutoramento de Mendonça [17], dando um passo a mais, levando a cabo a implementação do algoritmo aqui intitulado de Planariza por Divisão - PPD. Os resultados apontaram para um algoritmo com complexidade de tempo O(n²) e de espaço O(n + m). Duas modificações importantes foram realizadas no algoritmo original melhorando sua eficiência em termos de número de vértices divididos e condições limitantes da estrutura de dados utilizada bem como do algoritmo PPD, em si, foram evidenciadas.

Abstract: The statement problem that this work addressed was the study of graph planarization, a subfield of the Graph Theory. A graph is planar if it can be drawn in a plane without edge crossings between non incident edges or overlappings. "Planarize" a graph means transform it with a small number of operations into a planar graph. The research objetive is to present a new method intituled Graph Planarization by Vertex Splitting regardless the known and published method as: edge or vertex deletion, planar partitioning, and dummy vertices. The reasons of studying both theme and method can be synthesized into tree important pillars: in the increasing rule that graphical techniques, especially visualization, played in the actual world, such as data bank projects, which apply the popular notation Entity- Relationship – ER, and VLSI projects; in the less destructive features that our planarization method enables in concern with the original graph structure; and in the unpublished character of the implementation, until then inexistent. To reach such purpose the methodology included two aspects: the revision of the basic concepts on the graph theory and the specific related to the planarization methods as well as the data structure call PQ-Tree used by them; and the revision of the conceptual aspects of the work start by Mendon¸ca [17] during his Doctor Degree, giving a step further, carrying out the implementation of the algorithm entitled for us of the Split-Planarize. The results pointed out that Split-Planarize algorithm performs its task in time complexity O(n²) and uses space O(n + m). Two important modifications were accomplished in the original algorithm improving its efficiency, measured in terms of vertex splitting and constraints that narrow the performance of the Split-Planarize algorithm such as the data structure used as well as the algorithm, itself, were evidenced.