Desenho retangular em grade para DCELs

Resumo

Um desenho retangular de um grafo G é uma imersão plana de G em que todas as arestas são desenhadas como segmentos de reta verticais ou horizontais e todas as faces são retangulares. O algoritmo de desenho retangular para um grafo plano com cantos fixos é utilizado na construção de outras técnicas de desenhos de grafos, como desenhos caixa-retangulares e desenhos ortogonais, e é base para o algoritmo de desenhos retangulares generalizado para grafos planares. Neste trabalho, apresentamos uma implementação do algoritmo de desenho retangular para grafos planos com cantos fixos representados por listas de arestas duplamente ligadas. O algoritmo que desenvolvemos consome tempo linear e, como resultado do algoritmo, um desenho retangular com coordenadas em grade é construído.

Palavras-chave: Desenho de grafos. Grafo plano. Desenho retangular. Desenho em grade. Listas de arestas duplamente ligadas.

Abstract

A rectangular drawing of a graph G is a planar embedding of G such that each edge is drawn as a vertical or horizontal line segment and each face is a rectangle. The rectangular drawing algorithm for plane graphs with fixed corners is used on other graph drawing techniques, such as box-rectangular drawing and orthogonal drawing, and it is fundamental in the development of the more general rectangular drawing algorithm for planar graphs. In this study, we present an implementation of the rectangular drawing algorithm for plane graphs with fixed corners represented as doubly connected edge lists. The algorithm implemented has linear time complexity and, as a result of this algorithm, a rectangular drawing on a grid is obtained.

Keywords: Graph drawing. Plane graph. Rectangular drawing. Grid drawing. Doubly connected edge list.