Projeto P&D 008/06 Light (ANEEL/Concert/UFMG)
Desenvolvimento de Ferramenta para Geração Automática de Diagrama Ortogonal
das Redes de Distribuição
Relatório 2
Tema do Relatório: Pesquisa sobre os métodos passíveis de
uso na geração automática de sinóticos
Coordenação Técnica:
Renato Cardoso Mesquita (UFMG)
Vinícius Magalhães da Cruz (Light)
Daniel Corrêa Ramos (Concert)
Departamento de Engenharia Elétrica
Universidade Federal de Minas Gerais
21 de junho de 2007
Equipe (UFMG)
Professor:
Renato Cardoso Mesquita (Coordenação técnica);
Alunos:
Leandro Terra Cunha Melo (Mestrado em Engenharia Elétrica)
Raphael Duarte Chaves (Graduação em Engenharia Elétrica)
Equipe (Light)
Vinícius Magalhães da Cruz (Gerente)
Alexandre dos Santos Pereira (Pesquisador)
Jorge Ricardo de Carvalho (Pesquisador)
Equipe (Concert)
Edimar Vieira Froede Jr. (Coordenador)
Daniel Corrêa Ramos (Pesquisador)
Deyler S. Paiva (Pesquisador)
Petrônio Saldanha Gomes (Pesquisador)
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
2
Resumo
Este relatório descreve métodos passíveis de serem utilizados para geração automática
de sinóticos, conforme previsto no segundo quadrimestre do P&D 008/06
Light/Concert/UFMG, “Desenvolvimento de Ferramenta para Geração Automática de
Diagrama Ortogonal das Redes de Distribuição”. No relatório da Etapa 1 do P&D 008/06
foram analisadas as principais técnicas existentes para o desenho automático de grafos.
Neste relatório detalham-se as técnicas mais específicas que podem ser aplicadas neste
projeto, especialmente as baseadas em programação linear inteira. Estas serão utilizadas
para a modelagem dos diversos critérios estéticos que serão adotados para a construção
dos diagramas unifilares da rede de distribuição da Light.
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
3
Sumário
1 - Introdução ....................................................................................................................................... 5
2 – Topologia-Forma-Métrica baseada em Programação Linear Inteira ............................................. 8
2.1 Ortogonalização Utilizando Programação Linear Inteira (GIOTTO) ........................................ 8
2.2 Ortogonalização utilizando Programação Linear Inteira (Kandinsky) .................................... 10
3- Modelagem de critérios estéticos utilizando Programação Linear Inteira .................................... 12
3.1 Posicionamento de arestas em um dos lados de um vértice..................................................... 12
3.2 Pré-determinação do tamanho dos vértices .............................................................................. 14
3.3 - Utilização de rótulos .............................................................................................................. 15
3.3.1 Rotulação dos elementos de um grafo previamente construído ........................................ 16
3.3.2 Rotulação dos elementos do grafo durante a fase de compactação .................................. 18
4- Biblioteca para Resolução de Problemas de Programação Linear Inteira ..................................... 21
5- Biblioteca para manipulação e execução de algoritmos de grafos. ............................................... 22
6- Conclusões ..................................................................................................................................... 23
7. Referências Bibliográficas ............................................................................................................. 24
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
4
1 - Introdução
A utilização de técnicas que permitem o desenho de grafos com restrições estéticas é
importante em diversas aplicações. Como exemplos de aplicação de Desenho de Grafos
pode-se citar a Engenharia de Software (diagramas de fluxos de dados, grafos de
chamadas de subrotinas, hierarquias de classes e diagramas de objetos em programas
orientados a objeto), Bancos de Dados (diagramas entidade/relacionamento), Sistemas
de Informação (diagramas organizacionais), Sistemas de Tempo Real (redes de Petri,
diagramas de transição de estado), Sistemas de Suporte à Decisão (redes PERT, árvores
de atividade), Projeto de circuitos integrados (diagramas de circuitos), Sistemas de
Energia (diagramas das redes de transmissão e distribuição), Inteligência Artificial
(diagramas de representação do conhecimento), etc.
Cada uma destas aplicações possui requisitos específicos de desenho, dentre os quais os
critérios estéticos [BAT99b]. Nos diagramas unifilares da rede de distribuição da Light, por
exemplo, várias restrições estéticas foram identificadas, conforme discutiu-se nos
relatórios anteriores [MES07].
Os critérios estéticos geralmente utilizados pelos algoritmos de desenho de grafos são
bastante gerais, tratando, por exemplo, da diminuição do número de cruzamentos entre
arestas e/ou do direcionamento dos elementos do grafo em um sentido qualquer
[BAT99b].
No primeiro relatório discutiu-se a metodologia topologia-forma-metrica. Como se sabe,
esta técnica é divida em três fases distintas: A primeira fase é responsável pela
planarização do grafo e tem como resultado um embutimento planar do mesmo, em que
os cruzamentos de arestas são substituídos por vértices falsos. Na segunda fase, o
embutimento planar é ortogonalizado, sendo atribuídas seqüências de dobras a cada uma
das arestas do desenho e ângulos de incidência das arestas sobre os vértices. Na
terceira e última fase são calculadas as coordenadas dos vértices e das dobras de
arestas, de acordo com a representação ortogonal [MES07].
Destas três fases, a primeira é baseada em heurística, enquanto a segunda e a terceira
são modeladas como um problema de otimização. Na segunda fase (ortogonalização)
tenta-se minimizar o número de dobras em arestas, enquanto na terceira fase
(compactação) tenta-se minimizar a área total do desenho. A técnica utilizada para
formulação dos algoritmos de ortogonalização e compactação é baseada em minimização
de custos do fluxo em redes, que também já foi discutida [MES07]. Tentativas de
incorporar restrições ao desenho de grafos utilizando algoritmos baseados em fluxo em
rede [BRI97] porém, apresentam pouca flexibilidade de inserção de novas restrições,
como adição de rótulos em vértices e arestas.
Uma abordagem alternativa à utilização de fluxo em redes é apresentada em [EIG00]. A
técnica é baseada em Programação Linear Inteira (PLI) e apresenta algumas vantagens
como a possibilidade de utilização de várias restrições para desenhos de grafos planares
ou não-planares, além de maior eficiência, se comparada às abordagens baseadas em
fluxo em rede [EIG00, EIG01, KLA01,KLA02]. Cada uma destas restrições é modelada
através de um conjunto de equações e inequações lineares que devem ser satisfeitas,
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
5
produzindo um desenho ortogonal. A forma de implementação das restrições é única,
variando apenas as equações responsáveis pela modelagem de cada uma delas.
Utilizando-se PLI, também podem ser introduzidas restrições que permitam o desenho de
grafos com vértices de grau superior a 4. Esta metodologia, denominada Kandinsky
[EIG01], é ideal quando não são adotadas restrições quanto ao grau dos vértices,
possibilitando, por exemplo, a inclusão de duas ou mais arestas paralelas em um mesmo
lado de um vértice qualquer.
Nos diagramas unifilares da rede de distribuição da Light, além das restrições que
possibilitem a modelagem de vértices com arestas paralelas, diversas outras devem ser
introduzidas visando tratar os seguintes critérios estéticos:
1. Vértices
 Vértices de tamanho pré-determinados;
 Vértices com posições fixas.
2. Rótulos
 Rotulação dos diversos elementos existentes no desenho;
 Possibilidade de se utilizar mais de um rótulo por elemento;
 Rótulos de diferentes tamanhos;
3. Arestas
 Direcionamento de arestas, visando a padronização em certas áreas do
desenho.
4. Visualização
 Minimização da área do desenho, facilitando a visualização e localização dos
diversos elementos do sistema.
 A área do desenho deve seguir uma razão de aspecto pré-determinada.
 O número de cruzamentos e dobras deve ser mínimo, visando melhorar a
inteligibilidade do desenho.
Na figura 1.1, construída por desenhista, diversos destes critérios estéticos podem ser
observados.
Os algoritmos baseados em PLI são muito mais intuitivos, tendo em vista que qualquer
nova restrição pode ser adicionada através de uma equação algébrica linear. Além disso,
a grande maioria dos algoritmos que lidam com restrições é baseada em PLI. A utilização
de restrições baseada em algoritmos de fluxo em redes foi abordada em apenas uma
referência [BAT99].
Tendo em vista a maior versatilidade da PLI para o tratamento de restrições nos
desenhos de grafo, o objetivo deste relatório é descrever algoritmos encontrados na
literatura que viabilizem a implementação do conjunto de critérios estéticos identificados
neste projeto.
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
6
Figura 1.1 Diagrama ortogonal construído por desenhista
contendo diversas restrições estéticas.
O restante deste relatório é dividido da seguinte forma: na seção 2 é apresentada uma
visão geral sobre a abordagem baseada em programação linear inteira. Algoritmos
baseados em PLI para tratamento de restrições são apresentados na seção 3. Nas
seções 4 e 5 são apresentadas duas bibliotecas para construção de modelos que
envolvam PLI e para manipulação e execução de algoritmos em grafos, respectivamente.
Finalmente, na seção 6, apresentam-se as conclusões alcançadas nesta etapa.
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
7
2 – Topologia-Forma-Métrica baseada em Programação Linear Inteira
A programação linear inteira envolve a otimização (maximização ou minimização) de uma
função objetivo da forma
(2.1)
f x1, x2, ..., xn = a1 x1 + a 2 x2 + .... + a n xn
sujeita a restrições modeladas por equações e inequações lineares, tais como
 Ax   b

 x   0
(2.2)
Nas equações 2.1 e 2.2, cada uma das variáveis x é chamada variável objetivo, a matriz
A é chamada matriz de coeficientes e o vetor b vetor de restrições. Se a matriz de
coeficientes e o vetor de restrições são formados por elementos inteiros, diz-se que a
programação linear é inteira.
O objetivo de um problema de PLI como o mostrado acima é minimizar ou maximizar a
função objetivo, determinando o valor de cada variável objetivo.
A grande vantagem deste tipo de modelagem no desenho de grafos está no fato de que
qualquer novo critério estético a ser aplicado ao desenho exige apenas a inclusão de uma
nova inequação (restrição) na matriz de coeficientes, sem necessidade de alterações no
algoritmo em si. Esta característica torna as metodologias baseadas em PLI bastante
atraentes tendo em vista a flexibilidade oferecida por estas para a inclusão de novas
restrições.
Em [EIG00] são apresentadas diversas equações para modelagem de critérios estéticos
utilizando PLI. Além destas, também são apresentados dois modelos para implementação
da fase de ortogonalização do algoritmo topologia-forma-métrica, sendo um baseado em
grafos com vértices de grau inferior a quatro (GIOTTO) e outra em grafos sem restrições
quanto ao grau dos vértices (Kandinsky).
Nesta seção, as duas abordagens são descritas de maneira completa, tendo em vista a
possível utilização das mesmas na obtenção de diagramas ortogonais.
2.1 Ortogonalização Utilizando Programação Linear Inteira (GIOTTO)
No relatório 1 deste projeto, apresentou-se a formulação da etapa de ortogonalização
como um problema de fluxo em redes [MES07]. Agora, apresentamos a formulação do
mesmo problema através de PLI. Assim, como na ortogonalização por fluxo, como
entrada utiliza-se o embutimento planar de um grafo G = (V,E), com vértices V e arestas
E, dados pela ordem cíclica  (v) em sentido horário das arestas incidentes a cada vértice
v. Cada aresta e = (v,w) pertencente a E aparece duas vezes em  , sendo uma como
(v,w) em  (v) e outra como (w,v) em  (w) .
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
8
Determina-se também o conjunto F de faces. Seja Fin o conjunto de faces internas e Fout o
conjunto de faces externas (que consiste exatamente de uma face). Cada face f
pertencente a F é armazenada como a lista ordenada de arestas que definem f. Cada
aresta e em uma face f é direcionada tal que a face prescrita f esteja à direita de e (figura
2.1).
Figura 2.1. Definição de faces utilizada em [EIG00]. Nesta figura há duas
faces: F1: {e1, e6, e5, e4, e3, e2} e F2: {e1, e2, e3, e4, e5, e6}.
Para a construção do sistema de equações que definirão o PLI utilizou-se a mesma
modelagem dos problemas de custo mínimo de fluxo em redes. São dois tipos de
variáveis do sistema: Para cada aresta (u,v) pertencente a  , há uma variável r(u,v), que
conta o número de dobras de 90º (dobras à direita) e uma variável l(u,v), que conta o
número de dobras de 270º (dobras à esquerda), ambas ao longo da aresta na direção u-v.
As variáveis l(v,u) e r(v,u) contam o número de dobras da direção contrária v-u (uma dobra
de 270º em uma direção é uma dobra de 90º na direção contrária) (figura 2.2). Para se
obter um desenho com número mínimo de dobras, minimiza-se a soma das variáveis r(u,v)
e l(u,v).
Figura 2.2: Percorrendo-se e(u,v), tem-se duas dobras à direita (r(u,v) = 2 ) e uma à
esquerda ( l(u,v) = 1 ). Na direção contrária, e(v,u), tem-se r(v,u) = 1 l(v,u) = 2.
O segundo tipo de variável corresponde aos ângulos de vértices: Para cada aresta e =
(u,v) pertencente a  há uma variável a(u,v) que denota o ângulo entre e e seu
predecessor cíclico em  (v) no vértice v. O valor r de uma variável a(u,v) corresponde a
um valor de r*90º do ângulo correspondente. Todos os ângulos incidentes têm que ser
múltiplos de 90º, de forma que se deve demandar, explicitamente, que as variáveis
possuam valores inteiros, o que leva ao problema de programação linear inteira definido
pelas equações 2.3:
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
9
min
 (l
( v ,w)  E
(T 1)
a
( v , w)
( v , w)   ( v )
( v ,w)
 r( v , w) ) sujeito a
 4 v  V
2 k  4
 l ( v , w)  r( v , w) )  
( v , w)  f
2 k  4
(T 3) l ( v , w)  r( w,v ) (v, w)  E
(T 2)
 (a
( v , w)
f  Fin , | f |  k
f  Fout , | f |  k
f  F
(2.3)
l ( v , w) , r( v , w)   (v, w)  E
a ( v , w)  {1,..,4} (v, w)  E
Na restrição (T2) da equação 2.3, | f | denota o número de ângulo de vértices dentro de
uma face f. Em [TAM87], mostra-se que as condições acima são suficientes para gerar
desenhos ortogonais.
2.2 Ortogonalização utilizando Programação Linear Inteira (Kandinsky)
O algoritmo Kandinsky pode tratar vértices com grau superior a quatro, permitindo ângulo
zero entre arestas incidentes a um dos quatro lados de um vértice. Neste modelo, tem-se
um grid de linhas mais espessas, pois atribui-se a cada uma delas um conjunto de linhas
mais finas onde as arestas são roteadas. Para assegurar a correção do desenho, a
propriedade bend-or-end deve ser mantida, o que implica no controle do tamanho dos
vértices: Para duas arestas e1 = (v,w) e e2 = (v,u), w  u , ao menos uma das arestas e1
ou e2 deve possuir dobras, caso estejam anexadas ao mesmo lado do vértice v. É
fundamental a garantia de que as duas arestas não se interceptem, conforme se observa
na figura 2.3.
Figura 2.3: Arestas deixando o vértice v a partir
do mesmo lado sem se interceptarem [EIG00]
O PLI abaixo estende a formulação empregada na seção 2.1, através do agrupamento
das dobras ao longo das arestas em dobras de vértice e dobras de face. Cada dobra que
se deve à condição bend-or-end é denominada dobra de vértice, sendo atribuída ao
vértice que deve satisfazer a condição. Todas as outras dobras são denominadas dobras
de face.
Cada aresta pode ter duas dobras de vértice, uma para cada vértice que nela incide. Para
este propósito, introduz-se para cada aresta (v,w) pertencente a  quatro variáveis: lbv(v,w)
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
10
, rbv(v,w) , lbw(v,w) e rbw(v,w), que representam as dobras de vértice nos vértices v e w. As
variáveis lb(v,w) e rb(v,w) que denotam as dobras de face na aresta (v,w). Para simplificar,
escreve-se l(v,w) = lbv(v,w) + lb(v,w) + lbw(v,w) e r(v,w) = rbv(v,w) + rb(v,w) + rbw(v,w). Comparando a
notação entre as formulações GIOTTO e Kandinsky, observa-se que l(v,w) é sempre o
número total de dobras à esquerda de (v,w). A formulação Kandinsky completa é dada
pelo conjunto de equações 2.4:
min
 (l
( v , w)  E
( K1)
a
( v , w)
( v , w)   ( v )

( v , w)
 r( v , w) )
a
4 v  V
2 k  4
 l( v , w)  r( v , w) )  
( v , w)  f
2 k  4
v
v
( K 3) lbv,w  + rbv,w   1 (v, w)  
( K 2)
sujeito
 (a
( v , w)
f  Fin , | f |  k
f  Fout , | f |  k
( K 4)
au,v  + lbvv,w  + rbvv,u   1 (v, w) ,(v, u )  
( K 5)
lbvv,w  = rbvw,v 


lbv,w  = rb w,v 
 w
w

lbv,w  = rb w,v 
f  F
(2.4)
lb(vv , w) , rb(vv , w) , lb(wv , w) , rb(wv , w)  {0,1}
lb( v , w) , rb( v , w)  
a( v , w)  {0,..,4}
Apesar da equivalência entre as abordagens baseadas em redes de fluxo e aquelas
baseadas em PLI, a extensão da abordagem GIOTTO para o modelo Kandinsky,
utilizando redes de fluxo é bastante complicada, comparando-se com a abordagem que
utiliza programação linear inteira.
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
11
3- Modelagem de critérios estéticos utilizando Programação Linear
Inteira
Como dito anteriormente, a modelagem de critérios estéticos em desenho de grafos
dentro da abordagem de programação linear inteira se dá através da inserção de
equações e inequações ao modelo previamente estabelecido. Mostra-se, nesta seção, um
conjunto de restrições encontradas na literatura para a modelagem de critérios estéticos
que estejam de acordo com aqueles anteriormente descritos na seção 1 deste relatório.
3.1 Posicionamento de arestas em um dos lados de um vértice
A restrição de posicionamento de arestas em um lado de um vértice qualquer é
particularmente útil no caso da representação dos diagramas unifilares de distribuição da
Light. Na figura 3.1, obtida do Visualizador de Sinóticos xOMNI, observa-se que ocorre
um agrupamento de elementos de igual função (nodos azuis) em uma dada região do
grafo e que as linhas que os conectam a outros elementos do circuito sempre partem do
mesmo lado.
Figura 3.1. Parte de um diagrama ortogonal de circuito de distribuição da Light
apresentado no Visualizador de Sinóticos do xOMNI. Arestas posicionam-se à direita dos
vértices azuis.
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
12
Em [EIG00] é apresentado um método baseado em PLI para a modelagem deste critério
estético. Para tal, inicialmente devem ser feitas algumas definições. Seja Sd(v) o conjunto
de arestas a serem anexadas a um lado d do vértice v, onde d pode ser qualquer dos
lados do vértice (lado esquerdo, lado direito, lado de cima ou lado de baixo). Insere-se,
então, no conjunto de equações e inequações que definem o PLl, a variável s(dv ,w)  {0,1} . A
variável se igualará a 1 se e somente se a aresta {v,w} tiver uma de suas extremidades no
lado d, previamente definido. Assim, pelo fato de cada aresta ser incidente a exatamente
um lado de um vértice, a equação 3.1 deve ser inserida no PLI.
s
1
d
( v , w)
d {esquerda, direita,cima ,baixo}
(v, w)  
(3.1)
Sejam:



Eixo de balanço o eixo que divide um vértice em dois retângulos iguais;
c(v,w) o ângulo entre a extremidade esquerda do eixo de balanço horizontal de v e
a extremidade w da aresta (v,w) incidente a v;
m(v,w) o resultado da operação c(v,w) mod 4 .
Tem-se que o lado no qual uma aresta (v,w) é anexada ao vértice v, é determinado pelo
ângulo entre a extremidade esquerda do eixo de balanço horizontal do vértice v e a aresta
(v,w). Tal condição se expressa nas equações 3.2 [EIG00]:
4m(esquerda
 c( v , w)  3(1  s (esquerda
)
v , w)
v , w)
4m(esquerda
 c( v , w)  0
v , w)
cima
4m(cima
v , w )  c ( v , w )  1  3(1  s ( v , w ) )
4m(cima
v , w)  c( v , w)  1
(3.2)
direita
4m(direita
v , w )  c ( v , w )  2  3(1  s ( v , w ) )
4m(direita
v , w)  c( v , w)  2
baixo
4m(baixo
v , w )  c ( v , w )  3  3(1  s ( v , w ) )
4m(baixo
v , w)  c( v , w)  3
Finalmente, para especificar que uma aresta (v,w) é incidente ao lado d de um vértice v,
adiciona-se a restrição:
sd(v,w) = 1
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
(3.3)
13
Assim, através da resolução do conjunto de inequações do ILP anterior, pode-se
posicionar arestas em um lado qualquer de um conjunto de vértices. A figura 3.2 mostra
os resultados obtidos em [EIG00] quando se utilizou o PLI modelado pelas equações
anteriores.
Objetivando a obtenção de simetria do grafo 3.2(b) com relação aos nodos S1 e S8,
aplicou-se a restrição de posicionamento de arestas somente nos lados direito e esquerdo
destes mesmos nodos, obtendo-se o desenho mostrado na figura 3.2(c).
(b)
(a)
(c)
Figura 3.2. (a) Representação do grafo original. (b) Desenho ortogonal do mesmo grafo.
(c) Desenho do grafo após aplicação das restrições de posicionamento de
arestas somente à direita ou à esquerda dos vértices S1 e S8.
3.2 Pré-determinação do tamanho dos vértices
Uma outra característica que se observa nos diagramas unifilares obtidos da Light são os
diferentes tamanhos dos vértices que representam os diversos componentes do sistema
de distribuição. Isto é notado, especificamente, para as chaves de três direções e as
chaves a gás de n posições
A abordagem topologia-forma-métrica, apesar de seu comprovado sucesso em diversas
aplicações, ainda possui algumas desvantagens e problemas não resolvidos. Um dos
problemas mais complicados é a dificuldade em se produzir desenhos com vértices de
tamanho determinado pelo usuário. Atualmente, muitos algoritmos baseados nesta
abordagem consideram os vértices como pontos infinitesimais [TAM87], ou assumem que
os vértices possuem tamanhos iguais [BAT86, FOß96].
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
14
Há, no entanto, uma forte demanda por aplicações que possibilitem a construção de
desenhos ortogonais com vértices de tamanho arbitrário, definidos pelo usuário. É o que
se observa, por exemplo, em representações que utilizam grafos para construção de
diagramas UML, onde os elementos possuem distintas formas e tamanhos [EIG03].
[EIG00] apresenta um conjunto de restrições a serem adicionadas à fase de
ortogonalização do algoritmo Kandinsky que permitem especificar o tamanho mínimo de
um vértice em dimensões k1 x k2.
Para tal, deve-se inicialmente definir o lado d (lado esquerdo, lado direito, lado de cima,
lado de baixo) de um vértice v e a restrição de tamanho k que deve ser aplicada a este
lado. Assim, se d corresponde aos lados de cima ou de baixo, tem-se k = k1; caso
correspondam à esquerda ou à direita do vértice, utiliza-se k = k2. Além disso, define-se
E’ como as k-1 arestas precedentes a e em  (v) , incluindo e.
Toma-se cada intervalo E '   (v) de tamanho k, onde a primeira aresta deixa o vértice v
no lado d. Neste caso, assegura-se que a aresta é adjacente a um ângulo diferente de 0.
E para assegurar a incidência desta aresta no lado d do vértice v, utiliza-se a seguinte
restrição [EIG00]:
s(du ,v ) 
a
( v , w )E '
( v , w)
1
E '   (v), | E ' | k  1, e  (u, v) primeira aresta em E '
(3.3)
Na equação 3.3, a variável a(v,w) denota o ângulo entre a aresta (v,w) e seu predecessor
cíclico no embutimento planar e incidente no vértice w.
3.3 - Utilização de rótulos
Nos diagramas unifilares da rede de distribuição da Light, observa-se que a quase
totalidade dos vértices e elementos são identificados através de rótulos, caracterizados
por diferentes tamanhos e posicionamentos. Os diversos tipos de rótulos que se pode
observar na figura 3.3 são caracterizados pelas seguintes propriedades:





Não há sobreposição entre rótulos e outros elementos;
Cada rótulo caracteriza um único elemento do diagrama;
Existe a possibilidade de se incluir mais de um rótulo por elemento;
Há rótulos de tamanhos variados;
Compromisso entre área ocupada pelo rótulo e legibilidade do mesmo.
É de fundamental importância que se consiga o cumprimento de todos os requisitos
acima, visando a diminuição da complexidade visual do desenho. Dessa forma,
buscaram-se na literatura algoritmos que possibilitem a utilização de rótulos atendendo a
todas as características citadas.
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
15
Figura 3.3: Diversos tipos e disposições de rotulação estão presentes nos diagramas
unifilares da rede de distribuição da Light
Os algoritmos de rotulação de vértices podem ser divididos em duas abordagens:
1. Primeiro desenhar, depois rotular. Nesta abordagem, o processo de rotulação
ocorre em uma fase de pós-processamento, após a execução do algoritmo de
desenho. Dessa forma, a construção do desenho é executada em duas fases. Na
primeira delas, é produzido o desenho de um grafo sem levar em consideração
qualquer tipo de informação relativa ao posicionamento de rótulos. Na segunda
fase aplicam-se algoritmos de rotulação de mapas para caracterização de cada
elemento do desenho [KAK98].
2. Combinação entre Compactação e Rotulação. Nesta abordagem, combina-se o
problema de rotulação de vértices com a fase de compactação da metodologia
Topologia-Forma-Métrica. Neste caso, o posicionamento dos rótulos será levado
em consideração ao se atribuir coordenadas aos vértices do grafo planar [KLA01,
KLA02].
Há ainda uma terceira abordagem, que consiste em tratar os rótulos como vértices. Neste
caso, os rótulos são modelados como vértices de tamanhos previamente definidos e
anexados aos seus respectivos vértices através de arestas artificiais. Dessa forma o
posicionamento dos vértices se dá na fase de ortogonalização da metodologia topologiaforma-métrica.
Decidiu-se, porém, não abordar esta terceira abordagem em detalhes no presente
relatório, tendo em vista algumas de suas desvantagens. A primeira delas refere-se ao
aumento dos graus dos vértices devido à inclusão de arestas artificiais, acarretando em
um aumento desnecessário da complexidade de implementação de algoritmos. Além
disso, arestas e vértices artificiais podem destruir propriedades estruturais do grafo,
determinando um desenho de má qualidade [KLA01].
3.3.1 Rotulação dos elementos de um grafo previamente construído
Em [KAK98] apresenta-se uma abordagem geral para resolver o problema de atribuição
de textos ou símbolos a um conjunto de elementos gráficos em desenhos ou mapas
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
16
bidimensionais. Este tipo de problema é referenciado como problema GFLP (Graphical
Feature Label Placement), sendo que, por “feature” deve-se entender os diversos
componentes do grafo, como arestas e vértices. Nesta abordagem, os rótulos podem ter
tamanhos e orientação arbitrários.
O algoritmo consiste de três passos principais, resumidos no procedimento 3.1.
Procedimento 3.1: Algoritmo GFLP
Entrada: Desenho de um Grafo G e um conjunto de vértices a serem rotulados.
Saída: Um grafo com vértices rotulados.
1: Encontrar um conjunto de possíveis posições para os rótulos de cada vértice.
2: Reduzir o conjunto encontrado com base em regras estéticas.
3: Escolher a melhor dentre todas as posições encontradas.
Cada um destes passos pode ser implementado utilizando vários algoritmos, desde que
sejam observadas as seguintes regras estéticas (passo 2):



Não sobreposição dos rótulos com outros elementos do grafo.
Cada rótulo deve caracterizar apenas um elemento do grafo.
O rótulo deve ser posicionado no melhor local possível (dentre todas as
posições aceitáveis).
Quando se considera o grafo em que os rótulos serão inseridos, existe a possibilidade de
que mesmo um posicionamento ideal dos vértices não determine o cumprimento das três
regras acima. Dessa forma, associam-se custos a cada possível posição do rótulo, de
forma a se definir as melhores possíveis. Assim, faz-se com que o problema de
posicionamento de rótulos passe a ser visto como um problema de otimização, em que o
objetivo é encontrar o posicionamento de menor custo para um rótulo.
Um resultado obtido utilizando-se o procedimento 3.1 pode ser observado na figura 3.2
Figura 3.2: Desenho obtido utilizando-se o procedimento 3.1. As caixas pretas são os
vértices, as brancas os rótulos de aresta e as cinzas os rótulos de vértice [KAK98].
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
17
Observa-se, no entanto, que este tipo de algoritmo apresenta algumas desvantagens. A
principal delas está no fato de que o espaço existente para o posicionamento dos rótulos
não é suficiente, tendo em vista que, ao se compactar um grafo, não se assume a
posterior colocação dos mesmos. Isto faz com que restem quatro possibilidades para se
posicionar os rótulos:
1. Posicionar os rótulos permitindo a possível sobreposição destes com outros
elementos do desenho.
2. Posicionar os rótulos afastados de seu vértice correspondente, dificultando a leitura
do desenho.
3. Escalonar o grafo, permitindo a colocação de todos os rótulos, porém diminuindo a
qualidade do desenho, devido ao aumento do comprimento das arestas.
4. Minimizar o tamanho do rótulo de forma que este possa ser posicionado próximo
ao nodo correspondente e sem sobreposição com os demais elementos do
desenho, o que pode ocasionar em rótulos muito pequenos, dificultando a leitura
dos mesmos.
Quando não há restrição quanto à área a ser ocupada pelo desenho do grafo, os
algoritmos baseados em rotulação de mapas são uma boa alternativa, tendo em vista a
não necessidade de se alterar a metodologia topologia-forma-métrica. Porém, no caso
dos diagramas ortogonais da Light em que a compactação dos desenhos é um dos
fatores a serem considerados, alternativas devem ser buscadas.
3.3.2 Rotulação dos elementos do grafo durante a fase de compactação
A possibilidade de se determinar o melhor posicionamento final dos elementos de um
grafo (vértices e arestas) levando-se em consideração a existência de rótulos é de
fundamental importância para a minimização da área do desenho e diminuição da
complexidade visual do mesmo. Diferentemente do que ocorre em rotulação de mapas,
onde a posição dos objetos é especificada na entrada do problema, as coordenadas dos
vértices e arestas em um problema de rotulação de grafos (PRG) devem ser
determinadas levando-se em consideração a existência dos rótulos, o que determina uma
maior complexidade deste tipo de algoritmo.
Em [KLA02], cria-se uma nova abordagem para o problema de posicionamento de rótulos,
tratando-os durante a fase de compactação da metodologia topologia-forma-métrica. O
problema de rotulação e compactação, ou COLA (Compaction and Labeling Problem), é
tratado através de um algoritmo que, a partir da representação ortogonal do grafo e
algumas informações acerca de seus vértices, gera um desenho planar ortogonal com
comprimento total de arestas mínimo. Segundo os autores, o método proposto é superior
às abordagens tradicionais de aplicação de algoritmos de rotulação de mapas em
desenhos de grafo.
Primeiramente, um conjunto de rótulos é associado a cada um dos vértices v,
satisfazendo, obrigatoriamente, duas condições:
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
18
1. O rótulo associado a cada vértice v deve tocar v em pelo menos um ponto;
2. Não deve haver sobreposição entre o rótulo associado a v e outros elementos do
grafo.
A primeira condição determina a impossibilidade do rótulo de um vértice v estar afastado
do mesmo devido a inexistência de área para disposição do rótulo próximo ao vértice.
Como discutido na seção 3.3.1, essa condição não é necessariamente satisfeita quando
se emprega algoritmos de rotulação de mapas sobre desenhos de grafo. Na figura 3.3 há
uma comparação entre os algoritmos de posicionamento dos vértices de um mesmo grafo
utilizando algoritmos de rotulação de mapas e a abordagem descrita em [KLA02].
(a)
(b)
Figura 3.3: (a) Rótulos posicionados por algoritmo de rotulação de mapas.
(b) Rótulos posicionados durante a fase de compactação [KLA02]
Como se observa, o mau posicionamento dos rótulos determinou um acréscimo na área
total do desenho 3.3-(a), além de menor legibilidade, tendo em vista o afastamento de
alguns rótulos de seus vértices correspondentes.
Há, porém, uma questão a ser tratada. Apesar da técnica descrita em [KLA02] se mostrar
mais eficiente que os algoritmos de rotulação de mapas, os autores não descrevem como
esta pode ser aplicada a desenhos ortogonais com vértices de tamanho pré-determinado,
apesar de afirmarem que a técnica é extensível a este caso. Além disso, o algoritmo
“branch-and-cut” utilizado nesta abordagem tem tempo de execução exponencial no pior
caso e os autores não fornecem qualquer resultado experimental que valide a abordagem
utilizada.
Em [EIG01], é descrito um novo algoritmo através do qual se pode construir um desenho
ortogonal em que os vértices possuam tamanhos pré-determinados, requerendo tempo de
execução linear. O novo algoritmo é baseado na combinação entre um algoritmo de
compactação exata [KLA99] e a técnica de decomposição retangular [TAM87]. O
resultado final é obtido através da resolução de três problemas:
1. Dado o embutimento G de um grafo com vértices de grau máximo 4 e com
representação ortogonal H, encontrar um desenho de G com representação
ortogonal H.
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
19
O problema acima descreve, basicamente, a terceira fase da metodologia topologiaForma-Métrica, sendo solucionado tanto por algoritmos baseados em redes de fluxo
[EIG02] quanto por algoritmos baseados em programação linear inteira [EIG00]. Os
autores estendem o problema acima, de forma que se possa obter a representação
ortogonal de grafos com vértices de grau superior a 4. O problema é, então, redefinido:
2. Dado o embutimento G de um grafo com representação quasi-ortogonal Q e com
propriedades Kandinsky, encontrar um desenho de G com representação quasiortogonal Q, em que os vértices de G são representados como ponto.
Uma representação quasi-ortogonal determina que duas ou mais arestas possam ser
adjacentes ao mesmo lado de um vértice conforme se observa na figura 3.4.
Figura 3.4: Representação quasi-ortogonal de um conjunto de
vértices e arestas
Para resolução do problema 2, os autores utilizam uma extensão do algoritmo de
programação linear inteira (PLI) utilizada na resolução do problema 1. Há, ainda, a
necessidade de se estender a resolução dos problemas anteriores de forma que se possa
incluir nas equações que modelam o PLI os vértices de tamanho pré-determinado, o que
define um novo problema:
3. Dado o embutimento G de um grafo com representação quasi-ortogonal Q e com
as propriedades Kandinsky. Encontrar o desenho de G com representação
ortogonal Q, em que cada vértice v de G é representado por uma caixa de
tamanho (largura(v), altura(v)).
Ainda em [EIG01], os autores fornecem um algoritmo detalhado, baseado em PLI para
resolução do problema 3 em tempo linear.
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
20
4- Biblioteca para Resolução de Problemas de Programação Linear
Inteira
Diversos são os aplicativos disponíveis para a resolução de problemas de programação
linear, sendo que há dois tipos básicos de aplicativos utilizados no tratamento deste tipo
de problema:

Algoritmos para resolução de problemas ou solvers: são utilizados para encontrar
soluções ótimas para problemas específicos de programação linear. Têm como
entrada uma listagem das restrições do problema bem como uma matriz de
coeficientes para modelagem das equações e inequações do problema.

Sistemas de modelagem: São utilizados na formulação de problemas de
programação linear e na análise de suas soluções. Têm como entrada uma
descrição do problema em uma linguagem acessível ao usuário, fornecendo sua
solução nos mesmos termos.
Neste projeto, nos restringiremos à utilização do primeiro tipo de aplicativo, tendo em vista
que os critérios estéticos já estão modelados através de equações e inequações
conforme mostrado nas seções anteriores.
Os solvers existentes utilizam diferentes métodos de otimização como as abordagens
simplex e as técnicas baseadas em pontos interiores. O CLP [CLP04] e o lpsolve [LPS03],
por exemplo, são baseados no método simplex, enquanto o HOPDM [HOP98] utiliza
otimização baseada em pontos interiores.
Para a resolução dos problemas de programação linear através dos quais se modelarão
os diversos critérios estéticos presentes nos diagramas unifilares da rede de distribuição
da Light, um solver deve apresentar características como:



Ser baseado em software livre, de forma a evitar custos oriundos de sua aquisição;
Eficiência, tendo em vista a complexidade dos problemas de PLI.
Disponibilidade sob forma de biblioteca, disponibilizando uma API (Application
Programming Interface) de programação em C++.
Um solver que cumpre os três requisitos acima é o lpsolve [LPS03], cuja manutenção e
supervisão são feitas por Kjell Eikland e Peter Notebaert sendo constantemente
atualizado (está atualmente sob versão 5.1.10). É disponibilizado sob a licença LGPL 2.1,
e diferentemente de outros projetos baseados em software livre, permite sua utilização
sem a necessidade de disponibilizar o código-fonte da aplicação que o utilize. Para a
resolução dos problemas de programação linear o lpsolve utiliza uma versão revisada do
método simplex, além do método Branch-and-bound para inteiros.
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
21
5- Biblioteca para manipulação e execução de algoritmos de grafos.
Conforme discutido anteriormente, os diagramas ortogonais a serem construídos a partir
da rede de distribuição da Light serão modelados através de grafos. Assim, torna-se
necessária a utilização de uma ferramenta que possibilite a manipulação e execução de
algoritmos em grafos.
Para tal, será utilizada neste trabalho a biblioteca GTAD (Graph Toolkit for Algorithms and
Drawings), desenvolvida em uma dissertação de mestrado na UFMG [MEL07]. Esta
biblioteca adota o paradigma de programação genérica que objetiva tornar um software
independente das estruturas de dados sobre as quais ele opera, definindo conceitos que
modelem as abstrações de um determinado domínio. Uma das conseqüências desta
abordagem é a reutilização de componentes, tendo em vista que uma mesma estrutura
de dados pode ser mapeada a diferentes conceitos.
Um aspecto importante na programação genérica é o desempenho. É comum a existência
de restrições de tempo de execução em aplicações reais como as que serão
desenvolvidas neste projeto. Portanto, é imprescindível que implementações genéricas
sejam tão eficientes quanto implementações especializadas. Felizmente, o mecanismo de
templates da linguagem de programação C++, fundamental para o desenvolvimento de
componentes genéricos, tem resolução de tipos em tempo de compilação.
Conseqüentemente, bibliotecas desenvolvidas sob o paradigma de programação genérica
são freqüentemente mais rápidas que bibliotecas desenvolvidas sob o paradigma
convencional de orientação a objetos.
Com o intuito de promover um alto grau de flexibilidade, as implementações de algoritmos
da GTAD são altamente parametrizáveis. Há recursos que permitem a personalização de
partes do comportamento interno do algoritmo e a definição de quais dados devem ser
armazenados durante sua execução. Como essas configurações são feitas em tempo de
compilação, não há impactos ou sobrecarga no desempenho.
A GTAD é altamente flexível e extensível. Sua lista de adjacências, estrutura de dados
que representa o grafo, permite a parametrização dos vértices, arestas e outras
propriedades do grafo. Adicionalmente, a arquitetura da biblioteca também permite que
estruturas de dados alternativas possam substituir a lista de adjacência padrão, uma
característica decorrente da utilização de programação genérica.
Maiores detalhes sobre a GTAD e extensões a ela que serão implementadas neste
projeto, serão apresentadas no relatório da próxima etapa.
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
22
6- Conclusões
A realização deste trabalho de busca por métodos que permitam o desenho dos
diagramas ortogonais da rede de distribuição da Light, levando-se em consideração todos
os seus critérios estéticos, mostrou que não há na literatura um método específico que
possa ser aplicado para a resolução deste problema. Mostrou ainda que, enquanto alguns
algoritmos estão consolidados em termos de bibliografia e resultados práticos, como é o
caso do método de compactação VLSI ou dos algoritmos de rotulação de mapas
aplicados a grafos, outros ainda requerem certo esforço de pesquisa para que possam
ser utilizados de forma a produzir resultados aplicáveis a situações práticas, como é o
caso dos algoritmos de rotulação de vértices integrados à metodologia Topologia-FormaMétrica.
Certamente serão necessárias adaptações nas diversas abordagens descritas neste
relatório, de forma a alcançar o objetivo proposto. Apesar disso, já é possível estabelecer
uma direção a ser seguida em relação a quais métodos deverão ser implementados para
resolução do problema.
É ainda necessário comentar que as formulações matemáticas para introdução de alguns
tipos de restrições não foram encontradas na literatura. Por exemplo, a inclusão de mais
de um rótulo para cada elemento do diagrama, a compactação segundo uma razão de
aspecto pré-definida, ou ainda a possibilidade de manter um vértice qualquer em uma
posição fixa do grafo. A possibilidade de se conseguir tais recursos através de pequenas
adaptações nos algoritmos encontrados deve ser investigada e parece ser possível,
através da inclusão de novas restrições ao problema de programação linear inteira a ser
solucionado. Este foi mais um dos motivos que nos fez modificar a estratégia
anteriormente prevista, que era modelar o problema através de fluxo em redes, passando
a utilizar a modelagem mais geral da programação linear inteira.
Apesar destas questões ainda em aberto, foram selecionadas algumas técnicas para a
resolução da maioria das restrições: para o desenho de vértices com tamanho
previamente especificado, o que é essencial para a representação dos diversos
elementos do sistema de distribuição da Light, a abordagem apresentada em [EIG00]
poderá ser utilizada; para a fase de compactação, que deverá levar em consideração a
existência de vértices não pontuais, a abordagem presente em [EIG01] nos pareceu
bastante interessante, principalmente pelo fato de esta abordar a existência de vértices de
tamanho predeterminado; finalmente, as restrições de minimização do número de
cruzamentos e de dobras são tratadas durante a execução das fases de planarização e
ortogonalização, respectivamente, dos algoritmos GIOTTO e Kandinsky [EIG00].
Na próxima etapa, iniciaremos a implementação computacional dos algoritmos
apresentados neste e nos relatórios anteriores do projeto. Para esta implementação
contaremos com a biblioteca GTAD de algoritmos em grafos desenvolvida na UFMG
[MEL07] e com a biblioteca lpsolve [LPS03], de programação linear inteira, disponível sob
licença LGPL, podendo, portanto, ser utilizada neste projeto sem qualquer problema
associado a copyright.
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
23
7. Referências Bibliográficas
[BAT86] BATINI, C., NARDELLI, E., TAMASSIA, R.
diagrams. IEEE Trans. Softw. Eng., 4:538-546, 1986.
A layout algorithm for data-flow
[BAT99a] BATTISTA, G. D., DIDIMO, W., PATRIGNANI, M., PIZZONIA, M. Orthogonal
and quasi-upward drawings with vertices of prescribed size. Proceedings of the 7th
International Symposium on Graph Drawing (GD'99), Springer, J. Kratochvil, Ed., vol.
1731 of LNCS, 297-310, 1999.
[BAT99b] BATTISTA, G. D., EADES, P., TAMASSIA, R., TOLLIS, I.G. Graph Drawing:
Algorithms for the Visualization of Graphs, Prentice Hall, 1999.
[BRI97] BRIDGEMAN, S., FANTO, J., GARG, A., TAMASSIA, R., VISMARA,
L.InteractiveGiotto: An Algorithm for Interactive Orthogonal Graph Drawing. Proceedings
on GD'97, Rome, LNCS 1353, 303-308, 1997.
[CLP04] CLP SOLVER. http://www.coin-or.org/Clp/index.html, 2004.
[EIG00] EIGLSPERGER, M., FÖßMEIER, U., KAUFMANN, M. Orthogonal graph drawing
with constraints. Proceedings of the eleventh annual ACM-SIAM symposium on Discrete
algorithms, 3-11, 2000.
[EIG01] EIGLSPERGER, M., KAUFMANN, M. Fast compaction for orthogonal drawings
with vertices of prescribed size. In Proceedings of the 9th International Symposium on
Graph Drawing (GD'2001), Springer, vol. 2265, 124-138, 2001.
[EIG02] EIGLSPERGER, M., FEKETE, S. P., KLAU, G. W. Orthogonal graph drawing,
Lecture Notes in Computer Science, 2025:121-171, 2001.
[EIG03] EIGLSPERGER, M., KAUFMANN, M., SIEBENHALLER, M. 2003. A topologyshape-metrics approach for the automatic layout of UML class diagrams. In Proceedings
of the 2003 ACM Symposium on Software Visualization (San Diego, California, June 11 13, 2003). SoftVis '03. ACM Press, New York, NY, 189-ff, 2003.
[FOß96] FÖßMEIER, U., KAUFMANN, M. Drawing high degree graphs with low bend
numbers. In F. J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of
LNCS, pages 254-266. Springer, 1996.
[HOP98] HOPDM SOLVER, http://www.maths.ed.ac.uk/~gondzio/software/hopdm.html,
1998.
[KLA01] KLAU, G. W. A Combinatorial Approach to Orthogonal Placement Problems. PhD
thesis, Universitát des Saarlandes, 2001.
[KLA02] KLAU, G. W., MUTZEL, P. Combining Graph Labeling and Compaction
(Extended Abstract). In Kratochvíl, Jan, Eds. Proceedings Graph Drawing, pages pp. 2737, Stirín Castle, Czech Republic, 1999
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
24
[KLA99] KLAU, G. W., MUTZEL, P. Optimal Compaction of orthogonal grid drawings. In
Integer Programming and Combinatorial Optimization (IPCO'99), number 1610 in LNCS, p
304-319, 1999.
[KAK98] KAKOULIS, K. G., TOLLIS, I. G. A unified approach to labeling graphical
features. In Proceedings of the 14th Annual. ACM Symposium of Computational Geometry
(SoCG'98), pp. 347-356,1998.
[LEN90] LENGAUER, T. Combinatorial Algorithms for Integrated Circuit Layout. WileyTeubner, 1990.
[LPS03] LPSOLVE v. 5.5.0.10. http://tech.groups.yahoo.com/group/lp_solve/, 2003.
[MEL07] MELO, L. T. C. Uma Biblioteca para Desenho de Grafos construída sob o
paradigma de Programação Genérica. Dissertação de Mestrado, Programa de PósGraduação em Engenharia Elétrica, UFMG, 2007.
[MES07] MESQUITA, R. C. & MELO, L. T. C. - Levantamento do estado da arte na área
de desenho de grafos, Relatório 1 do Projeto P&D 008/06 Light (ANEEL/Concert/UFMG) Desenvolvimento de Ferramenta para Geração Automática de Diagrama Ortogonal das
Redes de Distribuição, Fevereiro de 2007.
[TAM87] TAMASSIA, R. On embedding a graph in the grid with the minimum number of
bends. SIAM Journal Comput., 3:421-444, 1987.
[TAM89] TAMASSIA, R., TOLLIS, I. G. Planar Grid Embeddings in Linear Time. IEEE
Trans. on Circuits and Systems CAS-36, pp. 1230-1234, 1989.
[SIX00] SIX, J. M., KAKOULIS, K. G., TOLLIS, I. G. Techniques for the Refinement of
Orthogonal Graph Drawings, Journal of Graph Algorithms and Applications, vol. 4, no. 3,
pp. 75-103, 2000.
Relatorio2-MetodosPassiveisDeUso.doc – P&D 008/06 – LIGHT/CONCERT/UFMG
25