Dissertação
Dissertação-Fabricio_Lira.pdf
Documento PDF (2.8MB)
Documento PDF (2.8MB)
UNIVERSIDADE FEDERAL DE ALAGOAS
INSTITUTO DE MATEMÁTICA
PROGRAMA DE PÓS-GRADUAÇÃO EM MATEMÁTICA
FABRICIO DE MACEDO LIRA
TRIANGULAÇÃO DE SUPERFÍCIES FECHADAS
E ORIENTÁVEIS COM POUCOS VÉRTICES
MACEIÓ
2015
FABRICIO DE MACEDO LIRA
TRIANGULAÇÃO DE SUPERFÍCIES FECHADAS
E ORIENTÁVEIS COM POUCOS VÉRTICES
Dissertação de Mestrado apresentada ao Programa
de Pós-Graduação em Matemática da Universidade
Federal de Alagoas, como requisito parcial para
obtenção do título de mestre em Matemática.
Orientador: Prof. Dr. Dimas Martínez
MACEIÓ
2015
Catalogação na fonte
Universidade Federal de Alagoas
Biblioteca Central
Divisão de Tratamento Técnico
Bibliotecário Responsável: Valter dos Santos Andrade
L768t
Lira, Fabricio de Macedo.
Triangulação de superfícies fechadas e orientáveis com poucos vértices /
Fabricio de Macedo Lira - 2015.
40 f. : il.
Orientador: Dimas Martínez.
Dissertação (Mestrado em Matemática) – Universidade Federal de Alagoas.
Instituto de Matemática. Programa de Pós-Graduação em Matemática. Maceió,
2015.
Bibliografia: f. 38-40.
1. Superfície. 2. Triangulação. 3. Triangulação irredutível. 4. Triangulação
minimal. I. Título.
CDU: 514.752.4
Agradecimentos
O termo gratidão vem do latim gratia que significa literalmente graça, ou gratus
que se traduz como agradável. Significa reconhecimento agradável por tudo quanto se
recebe ou lhe é reconhecido. Estar feliz e satisfeito por algo recebido, e não se esquecer
do ato.
Posto isto, intencionalmente utilizo este breve espaço para expressar minha sincera
gratidão àqueles que estiveram ao meu lado em todos os momentos e que fizeram de meus
sonhos os seus. Tomo então as palavras certas para que esses agradecimentos ecoem como
palavras que carregam verdade e significado.
Em favor de minha alma faço um agradecimento ao meu Deus, vem dEle tudo o
que sou e o que espero. Guia-me sempre por caminhos de paz e rege minha vida com
justiça.
Devoto meus sentimentos aqueles que pela motivação e confiança depositada em
mim eternamente serei devedor: minha família. Ainda que tentasse, jamais poderia retribuir o amor e o carinho dados a mim. Em especial meus pais, Benildo (in memoriam) e
Josefa, que da maneira que sabiam e podiam ajudavam e reconheciam meus esforços, me
proporcionando chegar até aqui.
Ao professor Dimas Martínez agradeço por acreditar, confiar, incentivar e torcer
por mim. Se não é possível agradecer adequadamente posso ao menos evidenciar seu
profissionalismo e competência, e reconhecer que nessa parceria eu saí ganhando.
Desejo agradecer aos membros da banca Perfilino Eugênio e Thales Vieira por
honrar-nos com sua presença, por seus oportunos comentários e sugestões, e por contribuírem em minha formação. Também devo estender meus gradecimentos aos professores
Francisco Barros (Chico Potiguar) e Adelailson Peixoto pelas oportunidades de aprendizado e crescimento.
Aos colegas de curso devo dizer que tão importante quanto tudo que aprendi nessa
jornada, foi e será nossa cumplicidade, ajuda e amizade. De forma especial aos amigos
do Laboratório de Computação Gráfica pela agradável convivência e companheirismo.
E finalmente, agradeço também a CAPES pelo apoio financeiro concedido.
Resumo
Dada uma superfície fechada e orientável 𝑆 , Ringel e Jungerman asseguram que o menor
número possível de vértices para construir uma triangulação em 𝑆 é dada pelo menor
√
inteiro maior que (7 + 1 + 48𝑔)/2, onde 𝑔 ̸= 2 é o gênero da superfície 𝑆 e quando
𝑔 = 2 a quantidade mínima necessária é 10 vértices. Estas triangulações são conhecidas
na literatura como triangulações minimais.Uma triangulação 𝒯 em 𝑆 chama-se de triangulação irredutível se o colapso de qualquer aresta de 𝒯 não gera uma nova triangulação
em 𝑆 . Em termos do número de vértices, também em função do gênero da superfície 𝑆 ,
suas triangulações irredutíveis não ultrapassam 13𝑔 − 4 vértices com 𝑔 > 0, no caso em
que 𝑔 = 0 existe uma única triangulação irredutível que coincide com a triangulação minimal para este gênero, contendo exatamente 4 vértices.Neste trabalho abordamos como
construir triangulações de superfícies fechadas e orientáveis com poucos vértices, isto é,
a quantidade de vértices está compreendida entre o número necessário para existência da
triangulação e a cota superior definida no grupo das triangulações irredutíveis.
Palavras-chaves: superfície. triangulação. triangulação irredutível. triangulação minimal.
Abstract
Given a closed orientable surface 𝑆 , Ringel and Jungerman ensure that the smallest
number possible of vertices to build a triangulation in 𝑆 is given by the smallest integer
√
greater than (7+ 1 + 48𝑔)/2 where 𝑔 ̸= 2 is the genus of the surface 𝑆 and when 𝑔 = 2 the
quantity minimum required is 10 vertices. These triangulations are known in the literature
as minimal triangulations. A triangulation 𝒯 in 𝑆 call it irreducible triangulation if the
collapse any edge of 𝑆 does not generate a new triangulation in 𝑆 . In terms of the number
of vertices, also depending on the of genus surface 𝑆 , their irreducible triangulations do
not exceed 13𝑔 − 4 vertices 𝑔 > 0, in the case where𝑔 = 0 there exists a unique irreducible
triangulation which coincides with the minimal triangulation for this genus, containing
exactly 4 vertices. In this work we discuss how to construct triangulations of closed
orientable surfaces with few vertices, i.e. the number of vertices is comprised between the
number required for the existence of triangulation and the defined upper bound in group
of irreducible triangulations.
Key-words: surface. triangulation. irreducible triangulation. minimal triangulation.
Lista de ilustrações
Figura 1 – Triangulações da esfera em 4 regiões (a) e do toro em 7 regiões (b). . .
8
Figura 2 – Triangulação do toro com 7 vértices. . . . . . . . . . . . . . . . . . . .
9
Figura 3 – Triangulação irredutível do toro.
. . . . . . . . . . . . . . . . . . . . . 10
Figura 4 – Vizinhança coordenada de um ponto. . . . . . . . . . . . . . . . . . . . 11
Figura 5 – Superfície fechada (a) e aberta (b). . . . . . . . . . . . . . . . . . . . . 12
Figura 6 – Superfícies fechadas e orientáveis. . . . . . . . . . . . . . . . . . . . . . 13
Figura 7 – Soma conexa da esfera e do toro (a) e do toro com o bitoro (b). . . . . 13
Figura 8 – Grafo com 7 vértices e 5 arestas. . . . . . . . . . . . . . . . . . . . . . 14
Figura 9 – Representações do mesmo grafo planar com arestas cruzadas (a) e sem
arestas cruzadas (b). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Figura 10 – Duas realizações do grafo 𝐾4 no toro. . . . . . . . . . . . . . . . . . . . 15
Figura 11 – Simplexos de dimensões 0, 1, 2 e 3. . . . . . . . . . . . . . . . . . . . . 17
Figura 12 – Coleção de simplexos de dimensões 0, 1 e 2. . . . . . . . . . . . . . . . 18
Figura 13 – Complexo simpliciais: 𝑒𝑠𝑡𝑟𝑒𝑙𝑎 (a) e 𝑙𝑖𝑛𝑘 (b) de vértice e de aresta. . . . 19
Figura 14 – Subdivisão de um triângulo (a) e contração de uma aresta (b). . . . . . 19
Figura 15 – Triangulação da esfera (a) e do toro (b). . . . . . . . . . . . . . . . . . 20
Figura 16 – Contração de arestas que modificam a topologia da triangulação. . . . 20
Figura 17 – Triangulação de um cilindro com 12 vértices. . . . . . . . . . . . . . . . 21
Figura 18 – Um 3-ciclo não vinculado a uma face na triangulação. . . . . . . . . . . 21
Figura 19 – Coloração da esfera com 4 cores (a) e do toro com 7 cores (b). . . . . . 22
Figura 20 – Toro de Császár: 7 vértices, 21 arestas e 14 faces. . . . . . . . . . . . . 23
Figura 21 – Triangulação irredutível do toro com 9 vértices. . . . . . . . . . . . . . 24
Figura 22 – Toro gerado por adição de uma alça à esfera (a) e sua triangulação
irredutível com 9 vértices (b). . . . . . . . . . . . . . . . . . . . . . . . 25
Figura 23 – Esquema de rotação definido para 4 vértices. . . . . . . . . . . . . . . . 27
Figura 24 – Esquema de adjacência para um triângulo orientado. . . . . . . . . . . 27
Figura 25 – Esquema de rotação para 𝑠 = 0. . . . . . . . . . . . . . . . . . . . . . . 28
Figura 26 – Condição de fluxo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Figura 27 – Grafo cúbico. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Figura 28 – Grafo cúbico para 𝑠 = 1. . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Figura 29 – Processo de execução do algoritmo de Schipper para uma triangulação
do toro com 12 vértices. . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Figura 30 – Triangulações de superfícies fechadas e orientáveis de gênero um a três.
33
Figura 31 – Triangulação para o bitoro com dez vértices. . . . . . . . . . . . . . . . 34
Figura 32 – Realização em R3 das triangulações da esfera (a) e do toro (b).
. . . . 35
Figura 33 – Resultados obtidos para triangulações de superfícies de gênero 1 a 3500. 36
Sumário
1
INTRODUÇÃO
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1
Objetivo
1.2
Estrutura do Trabalho .
2
DEFINIÇÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1
Superfície
2.2
Grafo .
2.3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
8
9
10
11
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
Complexo Simplicial
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3
TRIANGULAÇÕES
. . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.1
Triangulação Minimal
3.2
Triangulação Irredutível
4
ALGORITMOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
4.1
Triangulação Minimal: Casos 0, 3, 4 e 7 módulo 12 .
. . . . . . . .
26
4.2
Triangulação Irredutível: Triangulação com poucos vértices
. . . .
31
5
RESULTADOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
6
CONCLUSÃO
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
REFERÊNCIAS
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
. . . . . . . . . . . . . . . . . . . . . . . . . . .
22
. . . . . . . . . . . . . . . . . . . . . . . . . .
24
8
1 Introdução
O teorema de Radó afirma que toda superfície compacta admite uma triangulação
(1). Uma triangulação pode ser vista intuitivamente como um poliedro sobre a superfície
de modo que cada face é um triângulo com os três vértices distintos e a interseção de
quaisquer dois triângulos distintos ou é vazia, ou é um único vértice, ou é uma única
aresta. Por exemplo, triangulando a esfera com 4 vértices obtemos o tetraedro como o
poliedro resultante, veja figura 1(a) abaixo.
Ainda olhando para a esfera, poderíamos construir inúmeras triangulações bastando aumentar o número de regiões em que a decompomos. Este exemplo nos fornece
duas informações bastante interessantes: a primeira que 4 vértices são suficientes para
triangular a esfera, e mais que isto são também necessários; a segunda é que se olharmos
somente a conectividade do tetraedro, ou seja, como um grafo de seis arestas, ele contem
todas as arestas possíveis com 4 vértices.
Se agora considerarmos o toro, como na figura 1(b), já era conhecido em 1886
por Möbius que é possível construir uma triangulação com somente 7 vértices (2), e
supreendentemente tal como a esfera, em termos de grafo contem todas as suas 21 arestas.
Figura 1 – Triangulações da esfera em 4 regiões (a) e do toro em 7 regiões (b).
(a)
(b)
Fonte: Disponível no trabalho de Razafindrazaka (3).
Estes exemplos são bastante motivadores para a seguinte questão: dada uma superfície compacta sem bordo e orientável qual a quantidade mínima de vértices necessários
para obtermos uma triangulação desta superfície?
A resposta desta pergunta surge no contexto do Teorema Coloração de Mapas (4).
Este afirma que o número mínimo de cores necessárias para colorir um mapa em uma
superfície compacta sem bordo e orientável com gênero 𝑔 é
√
7 + 1 + 48𝑔
⌊
⌋.
2
Capítulo 1. Introdução
9
Para 𝑔 > 0 o teorema foi provado por Ringel e Youngs (5). O caso 𝑔 = 0 é o
famoso teorema das quatro cores que foi provado por Appel, Haken e Koch (6, 7).
A conexão entre o Teorema Coloração de Mapas e triangulações, está em observar
o grafo obtido por considerar como um vértice cada região do mapa e ligando dois vértices
sempre que as regiões que estes vértices correspondem compartilham uma fronteira comum. O caso extremo, como nos exemplos da esfera e do toro, é quando todos os vértices
são aos pares adjacentes exigindo todas as arestas.
Este grafo de 𝑛 vértices, onde 𝑛 é igual ao número de regiões existentes no mapa,
tem como gênero o menor inteiro maior que (𝑛 − 3)(𝑛 − 4)/12. Note que para os casos
em que o número de vértices é congruente a 0, 3, 4, 7 modulo 12 esta razão é um número
inteiro, isto corresponde, em termos da decomposição da superfície que todas as regiões
são triangulares, e consequentemente o grafo dual do mapa na superfície pode ser tomado
como uma triangulação desta superfície com este gênero.
1.1
Objetivo
Neste trabalho pretendemos construir triangulações de superfícies compactas sem
bordo e orientáveis de gênero arbitrário com poucos vértices. Estas construções tem alto
gênero em comparação com o número de vértices.
Primeiro expomos a construção apresentada por Ringel na demonstração do caso
quando o número de vértices é divisível por sete. Para o primeiro caso desta sequência, a
triangulação do toro com 7 vértices, além da representação combinatória vista na figura
2, há também uma representação geométrica imersa em R3 (8).
Figura 2 – Triangulação do toro com 7 vértices.
Fonte: Autor,2015
A segunda abordagem é começar com uma triangulação arbitrária da superfície e
modificar a triangulação por sucessivos colapsos nas arestas da triangulação de tal maneira
que o resultado é topologicamente o mesmo e ao final do processo temos uma redução
significativa da quantidade de vértices. A triangulação resultante alcançada chamamos
Capítulo 1. Introdução
10
de triangulação irredutível. Isto sempre é possível, pois qualquer superfície compacta tem
uma triangulação irredutível (9), e esta triangulação tem no máximo 13𝑔 − 4 vértices (10).
Figura 3 – Triangulação irredutível do toro.
Fonte: Autor,2015
1.2
Estrutura do Trabalho
O texto está dividido da seguinte forma: começamos no capítulo 2 apresentando superfície, grafo e complexo simplicial relacionando com a ideia de triangulação; na sequência
no capítulo 3 definimos propriamente triangulações, em especial enunciamos dois casos
interessantes, referidos na literatura como triangulações minimais e triangulações irredutíveis; a continuação, no capítulo 4, apresentamos uma construção para triangulações
minimais e um algoritmo para obter triangulações irredutíveis; alguns resultados obtidos
e uma comparação com o algoritmo para triangulações irredutíveis são apresentados no
capítulo 5; finalmente, no capítulo 6 fazemos as considerações finais.
11
2 Definições
Neste capítulo apresentaremos os principais conceitos para o desenvolvimento deste
trabalho. Iniciamos com superfícies, objeto central deste estudo. Abordaremos grafos
tratando de colorações e da relação com triangulações que são por fim expostas.
2.1
Superfície
Em computação gráfica, objetos geométricos são comumente representados por
superfícies. Essa representação permite uma descrição concisa de objetos simples, bem
como uma excelente ferramenta para modelar objetos mais complexos.
Definição 2.1 (Superfície). Um subconjunto 𝑆 ⊂ R3 é uma superfície se, para cada
𝑝 ∈ 𝑆 , existe uma vizinhança 𝑉 de 𝑝 em R3 e uma aplicação 𝜙 : 𝑈 → 𝑉 ∩ 𝑆 de um aberto
𝑈 de R2 sobre 𝑉 ∩ 𝑆 ⊂ R3 tal que:
1. 𝜙 é diferenciável;
2. 𝜙 é um homeomorfismo;
3. Para todo 𝑞 ∈ 𝑈 a diferencial 𝑑𝜙𝑞 : R2 → R3 é injetiva.
A aplicaçao 𝜙 é chamada uma parametrização ou um sistema de coordenadas locais
em uma vizinhança de 𝑝, e 𝑉 ∩ 𝑆 é chamada uma vizinhança coordenada de 𝑆 em 𝑝.
Figura 4 – Vizinhança coordenada de um ponto.
Fonte: Autor,2015
Uma superfície compacta e sem bordo é usualmente chamada somente por superfície fechada, e se há bordo, superfície aberta. Esta será a terminoloia que usaremos ao
longo do trabalho.
Capítulo 2. Definições
12
Figura 5 – Superfície fechada (a) e aberta (b).
(a)
(b)
Fonte: Autor,2015
Se tomarmos um caminho fechado na superfície, podemos pensar em um vetor
normal associado a um ponto desse caminho, e deslocar esse ponto ao longo da curva.
Avaliar a orientação da normal ao percorrer a curva, nos fornece uma valiosa informação
da superfície.
Definição 2.2 (Orientação). Se uma superfície admite um campo contínuo de vetores
normais, então dizemos que essa superfície é orientável.
A esfera na figura 5(a), superfície bem conhecida, é uma superfície orientável e a
faixa de Möbius 5(b) é um exemplo de superfície não orientável.
Uma decomposição de uma superfície fechada e conexa 𝑆 é a partição de 𝑆 em três
subconjuntos finitos chamados de vértices, arestas e faces, onde o conjunto vértices são
pontos de 𝑆 , o conjunto arestas são curvas simples em 𝑆 ligando quaisquer dois distintos
elementos do conjunto vértices, e o conjunto faces são as regiões conexas que tem como
bordo uma curva simples e fechada em 𝑆 formada pela concatenação de elementos do
conjunto arestas.
Uma ferramenta importante para classificar as superfícies é a característica de
Euler da superfície, pois é um invariante topológico, ou seja, superfícies homeomorfas têm
a mesma característica de Euler. Este invariante é denotado por 𝜒(𝑆) para uma superfície
𝑆 , e se define por 𝜒(𝑆) = 𝑣 − 𝑎 + 𝑓 , onde 𝑣 , 𝑎 e 𝑓 são respectivamente as cardinalidades
dos conjuntos vértices, arestas e faces de uma decomposição qualquer da superfície 𝑆 .
Em termos da característica de Euler, defini-se o conceito de gênero da superfície.
Definição 2.3 (Gênero). Seja 𝑆 uma superfície fechada e conexa com característica de
Euler 𝜒(𝑆). O número
{︃
𝑔=
se 𝑆 é orientável,
2 − 𝜒(𝑆), se 𝑆 é não orientável.
2−𝜒(𝑆)
,
2
é chamado gênero da superfície 𝑆 .
Capítulo 2. Definições
13
A figura 15 mostra exemplos de superfícies com gênero 0 15(a), gênero 1 15(b) e
gênero 2 15(c).
Figura 6 – Superfícies fechadas e orientáveis.
(a)
(b)
(c)
Fonte: Autor,2015
Dadas duas superfícies fechadas podemos "somá-las" de modo a conseguir uma
nova superfície fechada, essa operação chama-se de soma conexa. A figura 7 exemplifica
a soma conexa entre a esfera e o toro 7(a) obtendo um novo toro, e do toro com o bitoro
7(b) gerando portanto o tritoro.
Figura 7 – Soma conexa da esfera e do toro (a) e do toro com o bitoro (b).
(a)
(b)
Fonte: Autor,2015
Um fato é que todas as superfícies fechadas e orientáveis, exceto a esfera e o próprio
toro, podem ser vistas topologicamente por somas conexas de toros. É o que nos diz o
teorema de classificação de superfícies (11).
Teorema 2.1.1 (Teorema de Classificação de Superfícies) . Qualquer superfície fechada e
orientável é homeomorfa ou a esfera, ou ao toro, ou a soma conexa de toros.
Pelo teorema de classificação de superfícies sabemos quais são todas as superfícies
fechadas e orientáveis, a menos de um homeomorfismo. Assim, para identificar uma
superfície é suficiente determinar sua característica de Euler, ou equivalentemente seu
gênero, e verificar se a superfície é orientável ou não.
Capítulo 2. Definições
2.2
14
Grafo
Uma maneira intuitiva de imaginar um grafo é pelo desenho de alguns pontos num
papel e traçando linhas de um ponto qualquer aos demais se entre eles correspondem
uma relação. Como esses pontos e linhas são desenhados não é importante, a informação
relevante é quais dos pares de pontos estão conectados e quais não.
Definição 2.4 (Grafo). Um grafo 𝐺 é um par (𝑉, 𝐴) de conjuntos que satisfazem 𝐴 ⊆
𝑉 × 𝑉 . Os elementos de 𝑉 são os vértices do grafo 𝐺 e os elementos de 𝐴 são suas
arestas.
Figura 8 – Grafo com 7 vértices e 5 arestas.
Fonte: Autor,2015
O número de vértices de um grafo 𝐺 = (𝑉, 𝐴) é a sua ordem, e seu número de
arestas sua dimensão. Estes serão denotados por |𝑉 | e |𝐴|, respectivamente. Um grupo
especial de grafos são os grafos que possuem dimensão máxima.
Definição 2.5 (Grafo Completo). Dois vértices 𝑢,𝑣 são adjacentes, se 𝑢𝑣 é uma aresta.
Se todos os vértices são aos pares adjacentes, então o grafo é camado completo. Um grafo
completo com 𝑛 vértices denota-se por 𝐾𝑛 .
Do ponto de vista topológico, um grafo 𝐺 é um par (𝑉 (𝐺), 𝐴(𝐺)), onde 𝐴(𝐺)
denota um conjunto finito de curvas simples e 𝑉 (𝐺) denota um conjunto de pontos, os
quais correspondem às extremidades daquelas curvas.
Neste contexto, adotaremos a seguinte definição para conexidade:
Definição 2.6 (Grafo Conexo). Um grafo G é conexo, se quaisquer dois vértices podem
ser ligados por uma curva ou por concatenação de várias curvas de 𝐴(𝐺).
Um grafo completo é um exemplo trivial de grafo conexo, uma vez que todos os
vértices estão ligados entre si. Além da conexidade, um grafo completo possui outras
propriedades bem interessantes que serão abordadas neste trabalho.
Se for possível desenhar um grafo no plano sem que as arestas se cruzem, este
grafo é dito planar. Uma observação importante é que apesar de um dado grafo admitir
arestas cruzadas isso não significa que esse grafo não seja planar. Pode existir outro modo
de desenhá-lo onde não ocorram arestas cruzadas.
Capítulo 2. Definições
15
Figura 9 – Representações do mesmo grafo planar com arestas cruzadas (a) e sem arestas
cruzadas (b).
(a)
(b)
Fonte: Autor,2015
Essa noção de representação de um grafo planar, como desenhá-lo no plano sem
que as arestas se intersectem, pode ser generalizada para uma superfície qualquer. Quando
isto ocorrer, dizemos que o grafo é realizável nessa superfície.
Definição 2.7 (Realização). Seja 𝑆 uma superfície, um arco aberto em 𝑆 é a imagem do
homeomorfismo 𝛾 : (0, 1) → 𝑆 . Dado um grafo G com 𝑛 vértices 𝑣1 , . . . , 𝑣𝑛 e 𝑚 arestas
𝑎1 , . . . , 𝑎𝑚 , uma realização de 𝐺 em 𝑆 é um subespaço de 𝑆
𝐺(𝑆) = ∪𝑛𝑖=1 𝑣𝑖 (𝑆)
⋃︁
∪𝑚
𝑗=1 𝑎𝑗 (𝑆),
tal que
1. 𝑣1 (𝑆), . . . , 𝑣𝑛 (𝑆) são 𝑛 distintos pontos de 𝑆 .
2. 𝑎1 (𝑆), . . . , 𝑎𝑚 (𝑆) são 𝑚 arcos abertos em 𝑆 , dois a dois disjuntos.
3. Se 𝑎𝑘 = (𝑣𝑖 , 𝑣𝑗 ) então o arco aberto 𝑎𝑘 (𝑆) têm 𝑣𝑖 (𝑆) e 𝑣𝑗 (𝑆) como pontos extremos,
para todo 𝑖, 𝑗 ∈ {1, . . . , 𝑚} e 𝑘 ∈ {1, . . . , 𝑛}.
A condição 1 implica que cada vértice do grafo corresponde a um ponto da superfície. E as condições 2 e 3 que cada aresta corresponde a uma curva simples em que
nenhum par de curvas se intersectam em nenhum ponto, com exceção dos respectivos
pontos extremos.
Figura 10 – Duas realizações do grafo 𝐾4 no toro.
Fonte: Autor,2015
Capítulo 2. Definições
16
A realização de um grafo 𝐺 numa superfície 𝑆 proporciona a partição dessa superfície nas componentes conexas de 𝑆 − 𝐴(𝐺). Cada uma das componentes conexas deste
conjunto chama-se face.
Definição 2.8 (Realização Celular). A realização de um grafo 𝐺 diz-se celular se todas
as faces criadas por essa realização são homeomorfas à R2 . O conjunto destas faces
denota-se por 𝐹 (𝐺).
Com a defição acima pode-se notar que as duas realização de 𝐾4 apresentadas na
figura 10 nenhuma delas são uma realização celular.
Outro importante atributo de um grafo é o seu gênero. Mais adiante apresentaremos um importante resultado para o gênero de grafos completos.
Definição 2.9 (Gênero do Grafo). Chama-se de gênero de um grafo 𝐺, denotado por
𝑔(𝐺), o menor índice da sucessão de superfícies 𝑆0 , 𝑆1 , 𝑆2 , . . . , 𝑆𝑔 , . . . em que 𝐺 é
realizável, onde o índice 𝑔 denota o gênero da superfície 𝑆𝑔 .
Uma consequência direta desta definição é que para qualquer grafo planar 𝐺,
𝑔(𝐺) = 0. E se a superfície é fechada e orientável, um fato bastante conhecido sobre o
gênero do grafo, é a sua relação com o número de vértices, arestas e faces:
Teorema 2.2.1 (Fórmula de Euler). Se 𝐺 é um grafo conexo, então
|𝑉 (𝐺)| − |𝐴(𝐺)| + |𝐹 (𝐺)| = 2(1 − 𝑔(𝐺)).
Supondo que 𝐺 é um grafo conexo tal que |𝑉 (𝐺)| ≥ 3 e admite uma realização
celular numa superfície orientável, então
3|𝐹 (𝐺)| ≤ 2|𝐴(𝐺)|
e, por aplicação do teorema acima conclui-se que
1
1
𝑔(𝐺) ≥ |𝐴(𝐺)| − |𝑉 (𝐺)| + 1.
6
2
No caso particular em que 𝐺 é um grafo completo
𝑔(𝐺) ≥ ⌈
(|𝑉 (𝐺)| − 3)(|𝑉 (𝐺)| − 4)
⌉
12
onde, ⌈ ⌉ é a notação para maior inteiro.
Teorema 2.2.2 (Ringel-Youngs). Se 𝑛 ≥ 3, então 𝑔(𝐾𝑛 ) = ⌈ (𝑛−3)(𝑛−4)
⌉.
12
O resultado acima é conhecido como conjecturada de Heawood (4), que embora
formulado em 1890, apenas foi provada em 1968 por Ringel e Youngs (5).
Capítulo 2. Definições
2.3
17
Complexo Simplicial
Um triângulo em R2 é o polígono com menor número de vértices e arestas, e o
tetraedro em R3 é o poliedro que possui menos vértices, arestas e faces. Uma generalização
em outras dimensões é o conceito de simplexo.
Definição 2.10 (𝑘-simplexo). Um 𝑘-simplexo é o fecho convexo de 𝑘 + 1 pontos de
𝑣0 , 𝑣1 , ..., 𝑣𝑘 ∈ R𝑛 . O número 𝑘 é chamado dimensão do simplexo e denotamos o simplexo por [𝑣0 , 𝑣1 , ..., 𝑣𝑘 ].
Figura 11 – Simplexos de dimensões 0, 1, 2 e 3.
Fonte: Autor,2015
Definição 2.11 (𝑘-face). Seja 𝜎 = [𝑣0 , 𝑣1 , ..., 𝑣𝑙 ] um simplexo. O simplexo 𝜏 determinado
por 𝑘 +1 pontos do conjunto {𝑣0 , 𝑣1 , ..., 𝑣𝑙 } com 𝑘 < 𝑙 é chamado 𝑘-face de 𝜎 . Essa relação
denota-se por 𝜎 ≥ 𝜏 .
De acordo com esta definição as 0-faces de 1-simplexo são seus vértices e as 1-faces
de um 2-simplexo são suas arestas.
Uma vez definido os simplexos, vamos determinar agora as ligações entre eles.
Estas são estabelecidas satisfazendo algumas propriedades.
Definição 2.12 (Complexo Simplicial). Um complexo simplicial 𝒦 é um conjunto finito
de simplexos de forma que:
1. se o simplexo 𝜎 ∈ 𝒦 e 𝜎 ≥ 𝜏 , então 𝜏 ∈ 𝒦;
2. se os simplexos 𝜎, 𝜏 ∈ 𝒦, então 𝜎 ∩ 𝜏 = ∅ ou 𝜎 ∩ 𝜏 ≥ 𝜎 e 𝜎 ∩ 𝜏 ≥ 𝜏.
A condição 1 diz que as 𝑘 -faces de um simplexo também pertencem ao complexo
simplicial. E a condição 2 da definição garante que não existem interseções que não sejam
𝑘 -faces entre os simplexos do complexo simplicial.
Por exemplo, a interseção de um 2-simplexo com algum outro simplexo pode ser
apenas vértices ou arestas e a interseção de um 1-simplexo com outro simplexo se restringe
apenas a vértices.
Capítulo 2. Definições
18
A figura 12 ilustra duas coleções de simplexos. A coleção 𝐾 composta por três
2-simplexo e suas faces é um exemplo de complexo simplicial, enquanto a coleção 𝐿 não é
um complexo simplicial, pois a interseção dos simplexos não é vazia e também não é uma
face dos simplexos.
Figura 12 – Coleção de simplexos de dimensões 0, 1 e 2.
(a) K
(b) L
Fonte: Autor,2015
Definição 2.13 (Dimensão). Seja 𝒦 um complexo simplicial. A dimensão de 𝒦, denotada
por 𝑑𝑖𝑚(𝒦), é dada por
𝑑𝑖𝑚(𝒦) = max{𝑑𝑖𝑚(𝜎); 𝜎 é um simplexo de 𝒦}.
Se 𝑑𝑖𝑚(𝒦) = 𝑘, então chamamos 𝒦 de 𝑘-complexo simplicial ou complexo simplicial
𝑘 -dimensional.
O complexo simplicial 𝐾 da figura 12, possui simplexos de dimensão 0, 1 e 2,
portanto 𝐾 é um complexo simplicial bidimensional.
Definição 2.14 (Espaço Gerado). O espaço gerado por um complexo simplicial 𝒦, denotado por ‖𝒦‖, é a união de todos os simplexos de 𝒦 com a topologia herdada de R𝑛 .
Subconjuntos da coleção de simplexos que definem um complexo simplicial podem
também definir um complexo simplicial. A seguir exibiremos importantes subconjuntos
de simplexos, denominados 𝑒𝑠𝑡𝑟𝑒𝑙𝑎 e 𝑙𝑖𝑛𝑘 , em que isto se verifica.
Definição 2.15 (Estrela e Link). Sejam 𝒦 um complexo simplicial e 𝜎 um simplexo de
𝒦, então os seguintes conjuntos são complexos simpliciais em 𝒦:
1. 𝑒𝑠𝑡𝑟𝑒𝑙𝑎(𝜎) = {𝜏 ∈ 𝒦; 𝜏 ≥ 𝜎};
2. 𝑙𝑖𝑛𝑘(𝜎) = {𝜏 ∈ 𝑒𝑠𝑡𝑟𝑒𝑙𝑎(𝜎); 𝜏 ∩ 𝜎 = ∅}.
A figura 13 ilustra a 𝑒𝑠𝑡𝑟𝑒𝑙𝑎 e o 𝑙𝑖𝑛𝑘 de um vértice e de uma aresta em um complexo
simplicial bidimensional.
Capítulo 2. Definições
19
Figura 13 – Complexo simpliciais: 𝑒𝑠𝑡𝑟𝑒𝑙𝑎 (a) e 𝑙𝑖𝑛𝑘 (b) de vértice e de aresta.
(a)
(b)
Fonte: Autor,2015
Nós introduziremos agora perações que modificam um complexo simplicial, criando novos vértices ou eliminando arestas, estas são chamadas subdivisão e contração,
respectivamente.
Definição 2.16 (Subdivisão). Seja 𝒦 um complexo simplicial. A subdivisão de 𝒦, é
definida como o complexo simplicial ℒ, tal que |𝒦| = |ℒ| e cada simplexo de ℒ está
contido num simplexo de 𝒦.
Tomando 𝑉 𝑒𝑟𝑡(𝒦) como o conjunto de vértices de 𝒦 e considerando 𝑎, 𝑏 ∈ 𝑉 𝑒𝑟𝑡(𝒦)
e𝑐∈
/ 𝑉 𝑒𝑟𝑡(𝒦). Para descrever a contração da aresta 𝑎𝑏 no vértice 𝑐, defini-se uma função
vértice 𝑓𝑐 que leva os vértices 𝑎 e 𝑏 para 𝑐 e leva todos os outros vértices para si:
{︃
𝑓𝑐 (𝑣) =
𝑐, se 𝑣 ∈ {𝑎, 𝑏},
𝑣, se 𝑣 ∈
/ {𝑎, 𝑏}.
Esta função vértice 𝑓𝑐 pode ser estendida para todos os simplexos 𝜎 = [𝑣0 , 𝑣1 , . . . , 𝑣𝑘 ]
de 𝒦 definindo um novo simplexo 𝑓𝑐 (𝜎) = [𝑓𝑐 (𝑣0 ), 𝑓𝑐 (𝑣1 ), . . . , 𝑓𝑐 (𝑣𝑘 )].
Definição 2.17 (Contração). Sejam 𝒦 um complexo simplicial, 𝑎𝑏 uma aresta de 𝒦 e 𝑐
um vértice não pertencente a 𝒦. A função contração, 𝜙𝑎𝑏 : |𝒦| → |ℒ|, é a operação que
muda 𝒦 para ℒ = {𝑓𝑐 (𝜎); 𝜎 ∈ 𝒦}.
Figura 14 – Subdivisão de um triângulo (a) e contração de uma aresta (b).
(a)
(b)
Fonte: Autor,2015
20
3 Triangulações
Neste trabalho definiremos triangulação de uma superfície por meio de complexo
simplicial, pois estamos particularmente interessados na topologia da superfície.
Definição 3.1 (Triangulação). Uma triangulação de uma superfície 𝑆 é um complexo
simplicial bidimensional 𝒯 tal que ‖𝒯 ‖ é homeomorfo a 𝑆 .
Figura 15 – Triangulação da esfera (a) e do toro (b).
(a)
(b)
Fonte: Autor,2015
A triangulação é uma maneira de decomposição bastante utilizada, já que os triângulos são estruturas lineares extremamente simples. Dessa forma, gostaríamos de saber
quando é possível obtermos a triangulação de uma superfície (1).
Teorema 3.0.1 (Radó). Qualquer superfície compacta pode ser triangulada.
Vimos no capítulo 2 uma importante operação realizada sobre complexos simpliciais, a contração de arestas. Uma interessante observação é que podem ocorrer situações
degeneradas quando fazemos uma contração em arestas de uma triangulação, como ilustramos na figura 16. No caso degenerado 16(a), uma aresta do complexo simplicial resultante
será adjacente a quatro triângulos, e no caso degenerado 16(b) houve uma inversão de um
triângulo, causando uma dobra por cima de outro triângulo.
Figura 16 – Contração de arestas que modificam a topologia da triangulação.
(a)
(b)
Fonte: Autor,2015
Capítulo 3. Triangulações
21
Nós gostaríamos de fazer uma contração de aresta somente quando não há nenhuma alteração resultante na topologia, a este caso diremos que a aresta é colapsável.
Edelsbrunner (12) estabelece a condição de link para validar contração da aresta:
Teorema 3.0.2 (Edelsbrunner). Seja 𝒯 uma triangulação e 𝑎𝑏 uma aresta de 𝒯 . Então
𝑎𝑏 é colapsável se, e somente se, 𝑙𝑖𝑛𝑘(𝑎𝑏) = 𝑙𝑖𝑛𝑘(𝑎) ∩ 𝑙𝑖𝑛𝑘(𝑏).
Se fixarmos um vértice numa triangulação, podemos traçar caminhos sobre esta
triangulação através das arestas sempre voltando ao ponto fixado, ou seja, construir ciclos
sobre a triangulação.
Definição 3.2 (𝑘-ciclo). Um 𝑘-ciclo em uma triangulação consiste de 𝑘 arestas 𝑒1 , . . . , 𝑒𝑘
tal que 𝑒𝑖 ∩ 𝑒𝑗 é um único vértice se e somente se |𝑖 − 𝑗| = 1 ou |𝑖 − 𝑗| = 𝑘 − 1 e 𝑒𝑖 ∩ 𝑒𝑗 = ∅
caso contrário, para todo 𝑖, 𝑗 = 1, . . . , 𝑘 com 𝑖 ̸= 𝑗 .
Figura 17 – Triangulação de um cilindro com 12 vértices.
Fonte: Autor,2015
Na triangulação da figura 17 as arestas 𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 formam um 4-cliclo, já que
somente nos casos 𝑒1 ∩ 𝑒2 = 𝑣6 , 𝑒2 ∩ 𝑒3 = 𝑣7 , 𝑒3 ∩ 𝑒4 = 𝑣8 e 𝑒1 ∩ 𝑒4 = 𝑣5 a interseção é um
vértice e nos demais a interseção é vazia, e portanto as condições são satisfeitas.
Outro exemplo são faces de uma triangulação, toda face é um 3-ciclo. No entanto,
pode haver 3-ciclo que não são faces da triangulação como pode ser visto na figura 18.
Figura 18 – Um 3-ciclo não vinculado a uma face na triangulação.
Fonte: Autor,2015
Capítulo 3. Triangulações
22
Se uma aresta está contida em mais de dois 3-ciclo, então pelo menos um 3-ciclo
não está vinculado a uma face, e portanto, nós não poderíamos contrair a aresta (13).
Isto motiva o resultado de Schipper (14), uma equivalência a condição de link dada no
teorema 3.0.2.
Teorema 3.0.3 (Schipper). Qualquer aresta 𝑎𝑏 de uma triangulação 𝒯 é não colapsável
se, e somente se, 𝑎𝑏 é aresta de pelo menos três 3-ciclo ou 𝒯 é uma triangulação da esfera
com quatro vértices.
3.1
Triangulação Minimal
Um problema clássico da Teoria dos Grafos diz respeito à coloração de mapas.
Pretende-se saber qual o menor número de cores necessárias para colorir um mapa de
modo que não existam países, com fronteira comum da mesma cor. Uma forma de modelar
este problema consiste na construção de um grafo relacionando vértices com os países do
mapa e aresta com todos os pares de países com fronteira comum.
Definição 3.3 (Coloração). Dado um grafo 𝐺, os conjuntos 𝑉 de vértices e 𝐴 de arestas
e um conjunto 𝐶 de cores defini-se por coloração de 𝐺 uma função
𝜑 : 𝑉 → 𝐶,
tal que para todo 𝑢, 𝑣 ∈ 𝑉 temos que 𝜑(𝑢) ̸= 𝜑(𝑣) se 𝑢𝑣 ∈ 𝐴.
Com a terminologia acima, o problema de colorir mapas se traduz por determinar
o número cromático 𝜒(𝐺), que se define como sendo
𝜒(𝐺) = min{|𝐶|; 𝜑 : 𝑉 → 𝐶 é uma coloração de vértices em 𝐺}.
Figura 19 – Coloração da esfera com 4 cores (a) e do toro com 7 cores (b).
(a)
(b)
Fonte: Disponível no trabalo de Razafindrazaka (3).
A solução desse problema também foi provada por Ringel e Youngs. Essencialmente, o problema de colorir um mapa é equivalente a encontrar o gênero do grafo que
associamos ao mapa.
Capítulo 3. Triangulações
23
√
⌋.
Teorema 3.1.1 (Ringel-Youngs). Para todo grafo 𝐺 com gênero 𝑔, 𝜒(𝐺) = ⌊ 7+ 1+48𝑔
2
Se supurmos que todas as faces do grafo são triangulares, obteríamos uma triangulação da superfície com a menor quantidade de vértices possível. De fato isto é provado
por Jungerman e Ringel (15):
Teorema 3.1.2 (Jungerman-Ringel). Seja 𝑆 uma superfície fechada e orientável com
gênero 𝑔 e 𝑇 (𝑆) o número de triângulos da menor triangulação de 𝑆 . Então
𝑇 (𝑆) = 2⌊
e
7+
√
1 + 48𝑔
⌋ + 4(𝑔 − 1) se 𝑔 ̸= 2
2
𝑇 (𝑆) = 24 se 𝑔 = 2.
Esta triangulação é conhecida na literatura como triangulação minimal ou trian-
gulação vértice-minimal. No mesmo trabalho de Jungerman e Ringel (15), que demonstra
o teorema, os autores constroem exemplos de triangulações minimais para superfícies
orientáveis. E nesta direção, existem alguns trabalhos para superfícies de baixo gênero.
Uma das primeiras referências de triangulação minimal é a triangulação do toro
com 7 vértices apresentada por Möbius (2). Desta Császár constrói uma realização geométrica em R3 , que foi chamada Toro de Császár (8). Hoje sabe-se que há exatamente 72
diferentes tipos de realizações geométricas da triangulação minimal do toro descrita por
Möbius (16).
Figura 20 – Toro de Császár: 7 vértices, 21 arestas e 14 faces.
Fonte: Disponível no trabalo de Lutz (17).
Outros autores apresentam triangulações minimais para superfícies orientáveis de
gênero de dois a seis (18, 19). Com gênero de dois a quatro todas tem uma realização
geométrica (20, 17, 21), com gênero 5 pelo menos três não têm realizações geométricas
(22), e todas de gênero 6 não são geometricamente realizadas (23).
Capítulo 3. Triangulações
3.2
24
Triangulação Irredutível
Para qualquer superfície fechada há muitas triangulações possíveis com número
diferente de vértices. Para obter uma triangulação com um número pequeno de vértices
poderiamos começar com uma triangulação arbitrária de uma superfície e repetidamente
modificar a triangulação de tal maneira que o resultado é menor e ainda descreve a
superfície.
Uma operação para modificar uma triangulação é colapsando uma aresta. Intuitivamente, nós escolhemos uma aresta qualquer e pois contraí-la não alterará a topologia.
Esta triangulação que pode ser alcançada por repetidos colapsos de arestas chamamos de
triangulação irredutível.
Definição 3.4 (Triangulação Irredutível) . Seja 𝒯 uma triangulação e 𝑎𝑏 uma aresta em
𝒯 . Dizemos que 𝒯 é irredutível, se a contração 𝑎𝑏 altera a topologia de 𝒯 . Em outras
palavras, nenhuma aresta de 𝒯 é colapsável.
Figura 21 – Triangulação irredutível do toro com 9 vértices.
Fonte: Autor,2015
As triangulações irredutíveis foram inicialmente estudadas individualmente. Steinitz e Rademacher (24) mostram que 𝐾4 é a única triangulação irredutível da esfera e
que todas as triangulações da esfera podem ser geradas por uma sequência de subdivisões
a partir de 𝐾4 . Posteriormente, Lavrenchenko (25) apresenta 21 triangulações irredutíveis para o toro com 9 vértices. E Sulanke (26) constrói para o bitoro 865 triangulações
irredutíveis.
Barnette e Edelson (9) provaram que para qualquer superfície fechada, há um
número finito de triangulações irredutíveis. Além disso, podemos obter qualquer triangulação dessa superfície por sucessivas subdivisões a começar de sua triangulação irredutível
(27). E o número máximo de vértices das triangulações irredutíveis é linear no gênero da
superfície (13, 10).
Haijo Schipper (14) apresenta um algoritmo para obter de forma eficiente uma triangulação irredutível de uma superfície fechada e orientável a partir de uma triangulação
dada dessa superfície por uma sequência de colapsos.
Capítulo 3. Triangulações
25
A triangulação irredutível de uma superfície pode não ser uma triangulação minimal dessa superfície, por exemplo, o toro possui uma triangulação irredutível com 9
vértices, mas 7 vértices são suficientes para obter sua triangulação. No entanto, há um
limite superior para quantidade de vértices das triangulações irredutíveis.
Nakamoto e Ota (13) apresentam uma prova construtiva de que o número de
vértices é no máximo 171𝑔 − 72 para a triangulação irredutível de uma superfície fechada
e orientável com gênero 𝑔 . E recentemente, Joret e David (10) dão uma melhor cota para
o número de vértices, 13𝑔 − 4.
O trabalho de Schipper (14) também enumera problemas que permanecem abertos. Primeiro, há uma grande diferença em relação a quantidade de vértices entre a menor
triangulação irredutível de uma superfície e o limite superior para a maior triangulação
irredutível. Outro problema é o número de triangulações irredutíveis para uma determinada superfície. Sabe-se que a esfera tem uma única triangulação irredutível (24), o
toro 22 e o bitoro 865 com 10 vértices (28). O número de triangulações irredutíveis de
outras superfícies ou fórmulas gerais são desconhecidos. Um problema ainda mais difícil
é o problema de encontrar todas as triangulações irredutíveis.
Exemplo 3.1 (Uma construção de triangulações irredutíveis) .
É possível construir triangulações irredutíveis para superfícies fechadas e orientáveis de gênero arbitrário usando uma triangulação da esfera e colando várias cópias
de triangulações de alças de modo que a cada colagem a triangulação resultante é uma
triangulação irredutível.
Figura 22 – Toro gerado por adição de uma alça à esfera (a) e sua triangulação irredutível
com 9 vértices (b).
(a)
(b)
Fonte: Autor,2015
Esta triangulação irredutível tem 3𝑔 + 6 vértices, onde 𝑔 é o gênero da superfície
resultante, pois a cada colagem de triangulações de alças são adicionados somente três
novos vértices e iniciamos com uma triangulação da esfera com seis vértices.
26
4 Algoritmos
Neste capítulo buscamos descrever como construir triangulações para superfícies
fechadas e orientáveis com poucos vértices. Primeiro abordaremos a construção de Ringel
quando tais triangulações tem exatamente a quantidade mínima necessária para descrevêlas. Depois nós construímos triangulações com o número de vértices dado em função do
gênero da superfície, inspirados na operação de soma conexa entre duas superfícies, e
posteriormente reduziremos esta quantidade de vértices através de colapsos das arestas
por meio do algoritmo de Schipper.
4.1
Triangulação Minimal: Casos 0, 3, 4 e 7 módulo 12
O teorema de Ringel e Youngs (5) nos diz que para cada 𝑛 ≥ 4 existe uma triangulação com 𝑛 vértices de uma superfície orientável de gênero no máximo (𝑛 − 3)(𝑛 − 4)/12.
E o máximo é atingido sempre que 𝑛 é congruente com 0, 3, 4 ou 7 mod 12, para estes
casos a triangulação é chamada de triangulação neighborly, sugerindo que todo vértice
tem sua vizinhança completa, isto é, cada vértice da triangulação está ligado com todos
os demais vértices. Estas são muito interessantes, e tem recebido bastante atenção.
O caso 𝑛 = 4 é trivial, realizado pelo tetraedro. O primeiro caso relevante é 𝑛 = 7,
onde existe combinatoriamente uma única configuração, o Toro de Möbius com 7 vértices
(2). A triangulação de Möbius foi redescoberta várias vezes (29, 30), e realizada por
Császár (8). Para as triangulações neighborly com 𝑛 ≥ 12 não são conhecidas realizações.
Em seu artigo de 1891, Heffter (31) provou este teorema para 𝑛 ≤ 12, em particular, ao fazer isso ele introduziu alguns dos conceitos básicos e notações, e assim preparou
ferramentas para a prova completa. A prova completa utiliza argumentos combinatórios
complexos divididos em doze casos, de acordo com 𝑛 mod 12, com algumas construções
necessárias para casos esporádicos.
Nós vamos esboçar a construção de Ringel para o mais estudado dos doze casos,
o caso de 𝑛 ≡ 7 mod 12. Nossa exposição segue seu livro (32), no qual também constam
os outros onze casos. Esta produz triangulações que têm gênero que cresce de forma
quadrática com o número de vértices.
De acordo com Heffter uma superfície combinatória é completamente determinada
se rotular seus vértices e para cada vértice descrever o ciclo de seus vizinhos na ordem da
orientação horária ou anti-horária, um esquema de rotação.
Por exemplo, a figura 23 mostra uma pirâmide vista de cima que consiste em um
quadrilátero e quatro triângulos com um esquema de rotação que nos diz que 1, 2, 3, 4 são
Capítulo 4. Algoritmos
27
os vértices vizinhos de modo cíclico do vértice 0. Em particular, poderia ter escrito (2, 3,
4, 1) em vez de (1, 2, 3, 4), uma vez que este indica a mesma permutação cíclica. Para
garantir que um esquema desta forma realmente descreve uma superfície, é necessário que
satisfaça a condição de interseção: qualquer aresta pertence somente a duas faces (31).
Figura 23 – Esquema de rotação definido para 4 vértices.
Fonte: Disponível no trabalo de Ringel (32).
No caso de uma triangulação as condições de interseção são bastante fáceis de
descrever. De fato, se 𝑗 , 𝑘 aparecem adjacentes na lista cíclica de vizinhos de um vértice
𝑖, então isso significa que (𝑖, 𝑗, 𝑘) é um triângulo orientado da superfície, assim, 𝑘 , 𝑖 têm
que ser adjacentes nesta ordem no ciclo de vizinhos de 𝑗 , e da mesma forma 𝑖, 𝑗 tem que
aparecer na lista para 𝑘 , veja figura 24.
Figura 24 – Esquema de adjacência para um triângulo orientado.
Fonte: Disponível no trabalo de Ringel (32).
Em termos de esquema de rotação a condição de interseção diz que se a linha para
o vértice 𝑖, que equivale ao link do vértice 𝑖 na triangulação, é
𝑖 : (. . . , 𝑗, 𝑘, . . .)
então, nas linhas para 𝑗 e 𝑘 , temos que ter
𝑗 : (. . . , 𝑘, 𝑖, . . .)
𝑘 : (. . . , 𝑖, 𝑗, . . .).
Capítulo 4. Algoritmos
28
De acordo com Heffter (31) para 𝑛 = 12𝑠 + 7 onde 𝑠 ≥ 0, o esquema de rotação
para um vértice fornece cada um dos outros esquemas para os demais vértices a partir
da adição módulo 𝑛. Por exemplo, para 𝑠 = 0 se a linha para o vértice 0 for dada por
(1, 3, 2, 6, 4, 5) então a linha para o 𝑖-ésimo vértice será (1 + 𝑖, 3 + 𝑖, 2 + 𝑖, 6 + 𝑖, 4 + 𝑖, 5 + 𝑖)
com 𝑖 = 1, . . . , 6. Esta triangulação com 7 vértices é o Toro de Möbius (2) da figura 25.
Figura 25 – Esquema de rotação para 𝑠 = 0.
Fonte: Autor, 2015
Agora vamos supor que temos um esquema de rotação para 𝑛 vértices com a mesma
ideia usada para construir o Toro de Möbius,
0 : (𝑠1 , 𝑠2 , . . . , 𝑠𝑛−2 , 𝑠𝑛−1 )
e
𝑖 : (𝑠1 + 𝑖, 𝑠2 + 𝑖, . . . , 𝑠𝑛−2 + 𝑖, 𝑠𝑛−1 + 𝑖)
com 𝑖 = 1, . . . , 𝑛 − 1 e os 𝑠𝑖 fixados.
Se na linha do vértice 0 tivermos
0 : (. . . , 𝑗, 𝑘, . . .)
então a condição interseção fornece que
𝑗 : (. . . , 𝑘, 0, . . .)
𝑘 : (. . . , 0, 𝑗, . . .)
Como as linhas 𝑗 e 𝑘 são geradas por adição dos índices 𝑗 e 𝑘 a linha 0, temos que
0 : (. . . , 𝑘 − 𝑗, −𝑗, . . .)
0 : (. . . , −𝑘, 𝑗 − 𝑘, . . .).
Em outras palavras, se na vizinhança de 0, temos que "𝑘 segue 𝑗 ", então também
"−𝑗 segue 𝑘 − 𝑗 " e "𝑗 − 𝑘 segue −𝑘 ", onde todos os índices são interpretados módulo 𝑛 e
o sinal negativo indica que cada aresta no ciclo de vizinhos de 0 é percorrido duas vezes,
num sentido neste ciclo e com sentido oposto fora dele.
Capítulo 4. Algoritmos
29
Figura 26 – Condição de fluxo.
Fonte: Disponível no trabalo de Ringel (32).
A propriedade que temos descrito é a estrutura utilizada para construir um grafo
cúbico, todo vértice com valência três, em que a ordem cíclica na vizinhança de 0 pode
ser definida a partir de um caminho no grafo cujas arestas satisfazem a condição de fluxo.
Figura 27 – Grafo cúbico.
Fonte: Disponível no trabalo de Ringel (32).
A figura 27 codifica a solução completa de Ringel para o caso 𝑛 = 12𝑠 + 7. Ela
descreve um grafo cúbico com 2𝑠 + 4 vértices e 6𝑠 + 3 arestas, onde
1. Rotula as aresta com {1, 2, ..., 6𝑠 + 3} exatamente uma vez;
2. As arestas verticais são rotuladas por 1, 2, 3, . . . , 2𝑠.
3. As arestas horizontais inferiores são rotuladas uma por 2𝑠 + 1 e as demais alternadamente tomadas a partir das sequências
2𝑠 + 2, 2𝑠 + 3, 2𝑠 + 4, . . . , 3𝑠, 3𝑠 + 1, 3𝑠 + 2
e
4𝑠 + 2, 4𝑠 + 1, 4𝑠, . . . , 3𝑠 + 5, 3𝑠 + 4, 3𝑠 + 3.
4. As arestas horizontais superiores são rotuladas alternadamente tomadas a partir das
sequências
4𝑠 + 3, 4𝑠 + 4, 4𝑠 + 5, . . . , 5𝑠, 5𝑠 + 1, 5𝑠 + 2, 5𝑠 + 3
e
6𝑠 + 3, 6𝑠 + 2, 6𝑠 + 1, . . . , 5𝑠 + 6, 5𝑠 + 5, 5𝑠 + 4.
Capítulo 4. Algoritmos
30
E a regra de construção da triangulação, andando sobre este grafo, é a seguinte:
1. Em cada vértice ∙ girar à esquerda para a próxima aresta no sentido horário da
ordenação das arestas que estão adjacentes ao vértice, e para cada vértice ∘, girar à
direita;
2. Marque com positivo o rotulo de cada aresta percorrido na direção da seta, ou
negativo se for percorrido no sentido oposto da direção.
Faremos outro exemplo considerando agora quando 𝑠 = 1, e portanto esta segunda
superfície da sequência terá 19 vértices. Neste caso o grafo cúbico assume a forma como
na Figura 28.
Figura 28 – Grafo cúbico para 𝑠 = 1.
Fonte: Autor, 2015
Começamos nossa jornada na aresta 1 e avançamos na direção da seta. Assim, o
primeiro rótulo que escreveremos é 1. No vértice preto nós temos que girar em sentido horário na aresta marcada 8. Como essa trajetória esta na direção inversa, anotamos -8. Indo
assim, em um dado momento passaramos novamente pela aresta marcada 8, e desta vez
anotaremos com o sinal positivo. Continuando, como estaremos num vértice preto girando
em sentido horário retornariamos a aresta 1, e finalmente terminamos a viagem. A sequência de rotulos das arestas, será 1, −8, −5, −6, −4, 3, 8, 9, 7, 4, −2, −9, −1, 5, −3, −7, 2, 6.
Onde em módulo 19 é o mesmo que 1, 11, 14, 13, 15, 3, 8, 9, 7, 4, 17, 10, 18, 5, 16, 12, 2, 6.
Esta sequência é o esquema de rotação em torno do vértice 0, todos os outros
podem ser obtidos a partir desta por adição. Esta superfície tem 19 vértices, 171 arestas
e 114 triângulos, portanto o gênero é 20. Curiosamente nesta superfície existem mais
"buracos"do que vértices.
Este caminho leva a um único ciclo, em que cada aresta é percorrida em cada
sentido apenas uma vez, de modo que cada valor em {±1, ±2, . . . , ±(6𝑠 + 3)} ocorre
exatamente uma vez. Começando da aresta rotulada como 1, então a sequência que
seguimos será
1, −(5𝑠 + 3), −(3𝑠 + 2), −(3𝑠 + 3), −(3𝑠 + 1), −(3𝑠 + 4), 3𝑠, −(3𝑠 + 5), . . .
Capítulo 4. Algoritmos
31
para obtermos a primeira linha do esquema de rotação para a triangulação com
𝑛 = 12𝑠 + 7 vértices.
O esquema de rotação produzido por Ringel, juntamente com a condição de interseção controla o gênero, e consequentemente a superfície. Se nós tomarmos um esquema
de rotação aleatório, então isso produz superfícies aleatórias de gênero também aleatório.
4.2
Triangulação Irredutível: Triangulação com poucos vértices
Agora nós faremos uma descrição do algoritmo para obtermos triangulações irredutíveis de superfícies fechadas e orientáveis de gênero arbitrário com poucos vértices.
Primeiro nós criamos uma triangulação para a superfície com quantidade de vértices próxima a oito vezes o gênero da superfície, e numa segunda etapa aplicamos o algoritmo de
Schipper (14) para alcançarmos nosso objetivo de minimizar o número vértices.
A ideia geral do algoritmo de Schipper é colapsar arestas até não poder encontrar
uma aresta colapsável, ou seja, a triangulação resultante ser irredutível. A cada iteração
toma-se um vértice e decidi-se se existem arestas incidentes colapsáveis. Se for possível,
colapsa-se a aresta incidente sobre ele e portanto o vértice desaparece. Caso contrário, não
existem arestas incidentes colapsáveis e este será marcado como um vértice da triangulação
irredutível.
Algoritmo 1: Algoritmo de Schipper
Entrada: Triangulação 𝒯
Saída: Triangulação irredutível 𝒯 ′
início
Seja 𝐷 uma lista vazia.
para cada vértice 𝑣 em 𝒯 faça
Calcule a valência de 𝑣
Insira 𝑣 em 𝐷 usando a valência de 𝑣
fim
enquanto 𝐷 não é vazia faça
Seja 𝑣 o primeiro vértice de 𝐷
se existe uma aresta 𝑢𝑣 em 𝒯 colapsável então
Colapse 𝑢𝑣
Atualize 𝐷
fim
senão
Remova 𝑣 de 𝐷
fim
fim
fim
Capítulo 4. Algoritmos
32
Fornecendo uma triangulação de uma superfície fechada e orientável, uma triangulação irredutível é gerada eficientemente por Schipper se
1. Um acesso direto a uma aresta incidente em um vértice arbitrário ou à qualquer
aresta pertencente a uma determinada face são possíveis;
2. E adicionar ou remover arestas ou faces, bem como visitar o 𝑙𝑖𝑛𝑘 de um vértice ou
de uma aresta podem ser feitas em tempo constante.
Se a triangulação 𝒯 têm 𝑛 vértices, então o algoritmo computa em tempo 𝑂(𝑛𝑙𝑜𝑔𝑛)
a triangulação irredutível 𝒯 ′ , pois a sequência de colapsos esta definida por meio de uma
fila de prioridade.
Na figura 29 mostramos o passo a passo de como o algoritmo obtém uma triangulação irredutível para o toro com 7 vértices a partir da nossa triangulação com 12 vértices.
Observe que os vértices 𝑣5 e 𝑣10 com valência 4 e 𝑣7 e 𝑣12 valência 5 são inicialmente os
vértices de menor valência, e que no final do processo, o vértice 𝑣2 também com valência
5 é eliminado.
Figura 29 – Processo de execução do algoritmo de Schipper para uma triangulação do
toro com 12 vértices.
Fonte: Autor, 2015
Capítulo 4. Algoritmos
33
Para utilizarmos o algoritmo de Schipper é necessário construir a priori uma triangulação. Faremos isto inspirado na operação de soma conexa entre duas superfícies,
pois do ponto de vista topológico podemos construir superfícies fechadas e orientáveis de
gênero maior que um por meio de um número finito de somas conexa de toros.
Intuitivamente, considerendo que a superfície e o toro não tem pontos em comum,
recorte-se uma região circular em cada uma das duas superfícies e cole-se os bordos circulares gerados um no outro obtendo uma nova superfície.
Em termos das triangulações das superfícies também podemos efetuar esta operação. Esta é a ideia que usamos para construir uma triangulação para uma superfície de
gênero arbitrário. Nossa construção utiliza uma triangulação do toro com 12 vértices, e
faz repetidamente soma conexa com cópias deste toro transladado sempre num caminho
espiral.
Figura 30 – Triangulações de superfícies fechadas e orientáveis de gênero um a três.
(a) 𝑇1
(b) 𝑇2
(c) 𝑇3
(d) 𝑇4
Fonte: Autor, 2015
Capítulo 4. Algoritmos
34
Algoritmo 2: Triangulação de uma superfície orientável de gênero arbitrário
Entrada: O gênero 𝑔 da superfície
Saída: Triangulação irredutível com poucos vértices
início
se gênero igual a zero então
retorna Tetraedro
fim
se gênero igual a um então
retorna 𝑇1
fim
senão
Faça 𝑇 = 𝑇1
enquanto não atingir g faça
Translade 𝑇1 num movimento em espiral e faça soma conexa com 𝑇
fim
fim
Aplique o algoritmo de Schipper a triangulação criada.
fim
Na figura 31 apresentamos a triangulação obtida para o bitoro com dez vértices
utilizando este nosso algoritmo apresentado acima, em 31(a) a triangulação inicialmente
construída e em 31(b), triangulação resultante reduzido o número de vértices. Neste caso,
assim também como acontece com o toro, a triangulação gerada é a triangulação minimal
para esta superfície.
Figura 31 – Triangulação para o bitoro com dez vértices.
(a)
(b)
Fonte: Autor, 2015
35
5 Resultados
Nossa implementação foi feita utilizando a linguagem de programação C++ com
saída em OpenGL. Esta faz uso da estrutura de dados Directed Edge (33) para armazenamento e manipulação dos vértices, arestas e faces da triangulação que são fundamentais
para as operações de soma conexa e colapsos.
Na figura 32 mostramos a realização em R3 das triangulações para a esfera com 4
vértices e o toro com 7 vértices obtidas com o algoritmo. No caso do toro este difere da
realização dada por Császár em exatamente um vértice.
Figura 32 – Realização em R3 das triangulações da esfera (a) e do toro (b).
(a)
(b)
Fonte: Autor, 2015
Para comparar nosso algoritmo, na segunda etapa onde o processo de redução
do número de vértices é realizado com o algoritmo de Schipper nós o substituímos por
percorrer todas as arestas da triangulação verificando a condição de link para validar o
colapso, e se é possível colapse a aresta, caso contrário a mantenha na triangulação. Este
processo é repetido até que nenhuma aresta seja colapsável, o qual chamaremos Força
bruta.
Na tabela a seguir são apresentados como dada a triangulação inicial (INI) por
nós construída na primeira etapa do algoritmo qual a redução em relação ao número de
vértices utilizando o algoritmo de Schipper (ASH) e o algoritmo Força bruta (AFB), em
cardinalidade e em porcentagem.
Como pode ser visto na Tabela 1 o algoritmo Força bruta apresenta em média
uma redução de 34%, enquanto usando o algoritmo de Schipper atinge 51% em média.
Vale a pena notar que no caso das triangulações do toro e do bitoro o número de vértices resultante é a quantidade mínima necessária para obtermos triangulações destas
superfícies.
Capítulo 5. Resultados
36
Tabela 1 – Resultados obtidos para triangulações de superfícies de gênero 1 a 10.
Gênero
1
2
3
4
5
6
7
8
9
10
# Vértices
% Redução
INI AFB ASH AFB ASH
12
20
28
34
42
48
56
62
68
76
9
13
19
22
28
31
36
40
43
47
7
10
12
16
19
23
28
30
32
36
0.25
0.35
0.32
0.35
0.33
0.35
0.35
0.35
0.36
0.38
0.41
0.50
0.57
0.52
0.54
0.52
0.50
0.51
0.52
0.52
Fonte: Autor, 2015
Esta margem de redução da quantidade de vértices também é observada quando
aplicados às superfícies de gênero de 1 a 3500 como mostramos nos gráficos apresentados
na figura 33.
(a)
(b)
Figura 33 – Resultados obtidos para triangulações de superfícies de gênero 1 a 3500.
Fonte: Autor, 2015
37
6 Conclusão
Neste trabalho analisamos como construir do ponto de vista combinatório triangulações de superfícies fechadas e orientáveis com poucos vértices. É claro que estas
superfícies podem ser trianguladas, mas não é evidente quantos vértices seriam necessários
para isto.
Esta questão da minimilidade do número de vértices foi resolvida por Ringel ao
demostrar o Teorema Coloração de Mapas. E nos casos em que o número de vértices do
mapa é divisível por 12 ou deixa como resto 3, 4, 7 sua solução produz de imediato as
triangulações com exatamente estas quantidades de vértices, que se restringe a algumas
superfícies em termos de seu gênero. Para obtermos triangulações de superfícies de gênero
arbitrários utilizamos outra abordagem, triangulações irredutíveis, aplicando o algoritmo
devido a Schipper a triangulações por nós criadas obtendo triangulações com número de
vértices próximo a quatro vezes o gênero da superfície.
Como trabalhos futuros destacamos:
1. Obter melhorias do ponto de vista algorítmico nas interessantes construções das
triangulações minimais;
2. Obter triangulações com poucos vértices, não necessariamente irredutíveis, mas com
boas propriedades topológicas como ter todos os vértices com valência 6 ou próximo;
3. Obter realizações das triangulações em R3 , quando possível.
38
Referências
1 AHLFORS, L. V.; SARIO, L. Riemann Surfaces . Princeton: Princeton University
Press, 1960. v. 2. Citado 2 vezes nas páginas 8 e 20.
2 MöBIUS, A. F. Mittheilungen aus möbius’ nachlass: I. zur theorie der polyëder und
der elementarverwandtschaft. Gesammelte Werke II (F. Klein) , Verlag von S. Hirzel,
Leipzig, v. 1, p. 519–559, 1886. Citado 4 vezes nas páginas 8, 23, 26 e 28.
3 RAZAFINDRAZAKA, F. H. Visualization of High Genus Regular Maps . Dissertação
(Mestrado) — Freie Universitat Berlin, Berlin, Alemanha, 2012. Citado 2 vezes nas
páginas 8 e 22.
4 HEAWOOD, P. J. Map colour theorem. Quart. J. Math, v. 24, p. 332–338, 1890.
Citado 2 vezes nas páginas 8 e 16.
5 RINGEL, G.; YOUNGS, J. W. T. Solution of the heawood map-coloring problem.
Proceedings of the National Academy of Sciences of the United States of America , v. 60,
n. 2, p. 438–445, 1968. Citado 3 vezes nas páginas 9, 16 e 26.
6 APPEL, K.; HAKEN, W. Every planar map is four colourable, part i: discharging.
Illinois J. Math., v. 21, p. 429–490, 1977. Citado na página 9.
7 APPEL, K.; HAKEN, W.; KOCH, J. Every planar map is four colourable, part ii:
reducibility. Illinois J. Math., v. 21, p. 491–567, 1977. Citado na página 9.
8 CSÁSZÁR, A. A polyhedron without diagonals. Acta Univ. Szeged, Sect. Sci. Math,
v. 13, p. 140–142, 1949. Citado 3 vezes nas páginas 9, 23 e 26.
9 BARNETTE, D.; EDELSON, A. L. All 2-manifolds have finitely many minimal
triangulations. Israel Journal of Mathematics , Springer-Verlag, v. 67, n. 1, p. 123–128,
1989. ISSN 0021-2172. Disponível em: <http://dx.doi.org/10.1007/BF02764905>.
Citado 2 vezes nas páginas 10 e 24.
10 JORET, G.; WOOD, D. R. Irreducible triangulations are small. J. Comb. Theory
Ser. B, Academic Press, Inc., Orlando, FL, USA, v. 100, n. 5, p. 446–455, set. 2010. ISSN
0095-8956. Disponível em: <http://dx.doi.org/10.1016/j.jctb.2010.01.004>. Citado 3
vezes nas páginas 10, 24 e 25.
11 MASSEY, W. S. Algebraic Topology, an introduction . New York: Spriger Verlag,
1977. Citado na página 13.
12 DEY, T. K. et al. Topology preserving edge contraction. Publ. Inst. Math. (Beograd) ,
v. 66, p. 23–45, 1998. Citado na página 21.
13 NAKAMOTO, A.; OTA, K. Note on irreducible triangulations of surfaces. J. Graph
Theory, John Wiley & Sons, Inc., New York, NY, USA, v. 20, n. 2, p. 227–233, out.
1995. ISSN 0364-9024. Disponível em: <http://dx.doi.org/10.1002/jgt.3190200211>.
Citado 3 vezes nas páginas 22, 24 e 25.
Referências
39
14 SCHIPPER, H. Generating triangulations of 2-manifolds. Computational Geometry
- Methods, Algorithms and Applications , Springer Berlin Heidelberg, v. 553, p. 237–248,
1991. Disponível em: <http://dx.doi.org/10.1007/3-540-54891-2_18>. Citado 4 vezes
nas páginas 22, 24, 25 e 31.
15 JUNGERMAN, M.; RINGEL, G. Minimal triangulations on orientable surfaces.
Acta Mathematica, Springer Netherlands, v. 145, n. 1, p. 121–154, 1980. ISSN 0001-5962.
Disponível em: <http://dx.doi.org/10.1007/BF02414187>. Citado na página 23.
16 BOKOWSKI, J.; EGGERT, A. All realizations of möbius’ torus with 7 vertices.
Topologie Struct, v. 17, p. 59–78, 1991. Citado na página 23.
17 LUTZ, F. H. Enumeration and random realization of triangulated surface. Discrete
Differential Geometry , v. 38, p. 235–253, 2008. Citado na página 23.
18 BOKOWSKI, J.; BREHM, U. A polyhedron of genus 4 with minimal number of
vertices and maximal symmetry. Geom. Dedicata, v. 29, p. 53–64, 1989. Citado na
página 23.
19 BREHM, U. A maximally symmetric polyhedron of genus 3 with 10 vertices.
Mathematika, v. 34, p. 237–242, 1987. Citado na página 23.
20 HOUGARDY, S.; LUTZ, F. H.; ZELKE, M. Polyhedra of genus 3 with 10
vertices and minimal coordinates. Electronic Geometry Models , 2007. Disponível em:
<http://www.eg-models.de/2006.02.001>. Citado na página 23.
21 HOUGARDY, S.; LUTZ, F.; ZELKE, M. Surface realization with the intersection
edge functional. Experimental Math , v. 19, n. 1, p. 79–92, 2010. Citado na página 23.
22 SCHEWE, L. Satisfiability problems in discrete geometry. Technische Universität
Darmstads, 2007. Citado na página 23.
23 SCHEWE, L. Non-realizable minimal vertex triangulations of surfaces: Showing
nonrealizability using oriented matroids and satisfiability solvers. Disc. Comput. Geom ,
v. 43, p. 289–302, 2010. Citado na página 23.
24 STEINITZ, E.; RADEMACHER, H. Vorlesungenüber die theorie der polyeder.
WILEY-VCH Verlag, v. 14, n. 5, p. 318–319, 1934. ISSN 1521-4001. Disponível em:
<http://dx.doi.org/10.1002/zamm.19340140516>. Citado 2 vezes nas páginas 24 e 25.
25 LAVRENCHENKO, S. A. Irreducible triangulations of the torus. Journal of Soviet
Mathematics, Kluwer Academic Publishers-Plenum Publishers, v. 51, n. 5, p. 2537–2543,
1990. ISSN 0090-4104. Disponível em: <http://dx.doi.org/10.1007/BF01104169>.
Citado na página 24.
26 SULANKE, T. Generating irreducible triangulations of surfaces. arXiv:math/0606687, 2006. Citado na página 24.
27 GAO, Z.; RICHTER, R.; SEYMOUR, P. Irreducible triangulations of surfaces.
Journal of Combinatorial Theory, Series B , v. 68, n. 2, p. 206–217, 1996. ISSN
0095-8956. Disponível em: <http://www.sciencedirect.com/science/article/pii/
S0095895696900647>. Citado na página 24.
Referências
40
28 SULANKE, T. Irreducible triangulations of low genus surfaces. arXiv:math/0606690 ,
2006. Citado na página 25.
29 DUKE, R. A. Geometric embeddings of complexes. Amer. Math. Monthly , v. 77, p.
597–603, 1970. Citado na página 26.
30 ALTSHULER, A. Polyhedral realizations in R3 of triangulations of the torus and
2-manifolds in cyclic 4-polytopes. Discrete Math., v. 1, p. 211–238, 1971. Citado na
página 26.
31 HEFFTER, L. Ueber das problem der nachbargebiete. Math. Annalen, v. 38, p.
477–508, 1891. Citado 3 vezes nas páginas 26, 27 e 28.
32 RINGEL, G. Map Color Theorem . Berlin Heidelberg: Springer-Verlag, 1974. v. 209.
(Grundlehren der mathematischen Wissenschaften, 1). Citado 3 vezes nas páginas 26,
27 e 29.
33 CAMPAGNA, S.; KOBBELT, L.; SEIDEL, H. P. Directed edges: A scalable
representation for triangle meshes. Journal of Graphics Tools , v. 3, n. 4, p. 1–11, 1998.
Citado na página 35.
