Download PDF
ads:
Decomposi¸c˜ao e Largura em
´
Arvore de Grafos
Planares Livres de Ciclos Pares Induzidos
Este exemplar corresponde `a reda¸c˜ao final da
Disserta¸c˜ao devidamente corrigida e defendida
por Aline Alves da Silva e aprovada pela Banca
Examinadora.
Fortaleza, 27 de agosto de 2007.
Cl´audia Linhares Sales (MDCC/UFC)
Disserta¸c˜ao apresentada ao programa Mestra-
do e Doutorado em Ciˆencia da Computa¸c˜ao,
ufc, como requisito para a obten¸c˜ao do t´ıtulo
de Mestre em Ciˆencia da Computa¸c˜ao.
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Mestrado e Doutorado em Ciˆencia da Computa¸c˜ao (MDCC)
Universidade Federal do Cear´a (UFC)
Decomposi¸c˜ao e Largura em
´
Arvore de Grafos
Planares Livres de Ciclos Pares Induzidos
Aline Alves da Silva
[email protected]
Agosto de 2007
Banca Examinadora:
• Cl´audia Linhares Sales (MDCC/UFC)
• Sulamita Klein (UFRJ)
• Ricardo Cordeiro Corrˆea (MDCC/UFC)
ads:
iii
Agradecimentos
Agrade¸co, primeiramente, a Deus, pelo Seu amor incondicional por mim e por ter me
permitido chegar ao fim desse trabalho com ˆexito.
Aos meus pais Airton Felix da Silva e Maria Neide Alves da Silva por todos os
anos de dedica¸c˜ao a mim concedidos e pelos v´arias anos de trabalho a fim de me propor-
cionar o conhecimento necess´ario para que eu chegasse aqui.
Aos meus irm˜aos Alesson e Alessandra pela confian¸ca nesse trabalho.
A Cl´audia Linhares Sales pela orienta¸c˜ao desse trabalho e pelas experiˆencias com-
partilhadas.
A Ana Shirley por todo apoio e co-orienta¸c˜ao.
A todos os professores do mestrado por terem me acrescentado bastante conheci-
mento.
A Uniserpro por ter me concedido libera¸c˜ao parcial da minha jornada de trabalho
no Serpro, resultando em uma maior disponibilidade de tempo para a conclus˜ao desse
trabalho.
Aos meus amigos de mestrado, em especial, ao Italo, Edvan, Fernando e Alexsan-
dro, por toda a ajuda e momentos de entretenimento no LIA.
Aos meus amigos Elvira, Rafaela, Raquel e Raul, pela presen¸ca no dia da defesa
desta disserta¸c˜ao de mestrado.
Aos demais amigos e familiares que me apoiaram atrav´es de ora¸c˜oes ou mensagens de
otimismo.
Resumo
Os conceitos de Decomposi¸c˜ao em
´
Arvore e Largura em
´
Arvore foram introduzidos por
Robertson e Seymour em sua s´erie de artigos sobre menores de grafos, publicados ao
longo da d´ecada de 90. Sabe-se que muitos problemas N P-dif´ıceis podem ser resolvidos
polinomialmente para um grafo G, dada uma decomposi¸c˜ao em ´arvore de G de largura
limitada. Logo, limitar a largura em ´arvore de uma classe de grafos torna-se um objeto de
estudo de grande interesse. Neste contexto, a classe dos grafos planares se mostra bastante
intrigante, uma vez que, apesar de possuir outras m´etricas limitadas em valores baixos (por
exemplo, n´umero crom´atico), n˜ao possui largura em ´arvore limitada. Desta forma, uma
alternativa ´e restringir a classe estudada para uma subclasse dos grafos planares.
Neste trabalho, n´os investigamos a classe dos grafos planares livres de buracos pares.
N´os mostramos que se G ´e um grafo planar livre de buracos pares, ent˜ao ele n˜ao cont´em
uma subdivis˜ao de uma grade 10 × 10. Portanto, se os menores grades de G s˜ao obtidos
de subdivis˜oes, G tem largura em ´arvore no m´aximo 49. Al´em disso, dois algoritmos n˜ao-
exatos polinomiais para computar uma decomposi¸c˜ao em ´arvore de um grafo planar livre
de buracos pares s˜ao apresentados, ambos baseados em caracteriza¸c˜oes conhecidas de tal
classe de grafos. No primeiro algoritmo, uma decomposi¸c˜ao em ´arvore ´e constru´ıda a partir
de grafos b´asicos pela concatena¸c˜ao de decomp osi¸c˜oes em ´arvores de peda¸cos pequenos via
os cortes clique, k-estrelas (k = 1, 2, 3) e 2-join. No segundo, uma decomposi¸c˜ao em ´arvore
´e constru´ıda pela inclus˜ao dos v´ertices de G um a um, seguindo sua ordem bi-simplicial.
PALAVRAS CHAVE: Grafos planares. Grafos livres de buracos pares.
Largura em ´arvore. Teoria de Grafos.
Abstract
The definitions of tree decomposition and treewidth were introduced by Robertson and
Seymour in their series of papers on graph minors, published during the nineties. It is
known that many N P-hard problems can be polynomially solved if a tree decomposition
of bounded treewidth is given. So, it is of interest to bound the treewidth of certain classes
of graphs. In this context, the planar graphs seem to be specially challenging because,
in despite of having many known bounded metrics (for example, chromatic number), they
have unbounded treewidth. So, an alternative approach is to restrict ourselves to a subclass
of planar graphs.
In this work, we investigate the class of even-hole-free planar graphs. We show that if G
is an even-hole-free planar graph, then it does not contain a subdivision of the 10×10 grid.
So, if the grid minors of G are obtained from subdivisions, then G has treewidth at most
49. Furthermore, two polynomial, non-exact algorithms to compute a tree decomposition
of a even-hole-free planar graph are given, both based on known characterizations of even-
hole-free graphs. In the first one, a tree decomposition is built from basic graphs by
concatenating the tree decomposition of small pieces via the clique, k-stars (k = 1, 2, 3)
and 2-join cutsets. In the second one, a tree decomposition is built by including one by
one the vertices of G, following their bi-simplicial order.
KEYWORDS: Planar Graphs. Even-hole-free graphs. Treewidth. Graph
Theory.
Sum´ario
1 Introdu¸c˜ao 1
2 Conceitos Preliminares 5
2.1 Defini¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Algumas classes de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Decomposi¸c˜ao em
´
Arvore 10
3.1 Defini¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Caracteriza¸c˜oes por menores proibidos . . . . . . . . . . . . . . . . . . . . 11
3.4 Limites superiores e menores proibidos . . . . . . . . . . . . . . . . . . . . 13
4 Grafos planares 14
4.1 Defini¸c˜ao e Teorema de Kuratowski . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Menores proibidos em grafos planares . . . . . . . . . . . . . . . . . . . . . 15
5 Grafos livres de buracos pares 17
5.1 Estruturas proibidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 Teorema da Decomposi¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.3 Teorema do V´ertice Bi-simplicial . . . . . . . . . . . . . . . . . . . . . . . 26
6 Largura em ´arvore de grafos planares livres de buracos pares 27
6.1 Menor grade 3 × 3 em grafos planares livres de buracos pares . . . . . . . . 27
6.2 Um limite superior para uma subclasse . . . . . . . . . . . . . . . . . . . . 28
6.2.1 Lemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
6.2.2 Prova do Teorema 6.2.1 . . . . . . . . . . . . . . . . . . . . . . . . 32
7 Teorema da Decomposi¸c˜ao para os grafos planares 42
7.1 Grafos planares livres de buracos pares e livres de caps . . . . . . . . . . . 42
7.2 Grafos planares livres de buracos pares b´asicos . . . . . . . . . . . . . . . . 46
7.3 Grafos planares livres de buracos pares que contˆem um 2-join . . . . . . . 47
7.4 Grafos planares livres de buracos pares que cont´em corte k-estrela (k = 1, 2, 3) 48
7.5 Teorema da Decomposi¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
8 Algoritmo de decomposi¸c˜ao baseado no Teorema do V´ertice Bi-simplicial 59
8.1 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
8.2 Corretude do algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
8.3 Complexidade do algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . 65
9 Conclus˜ao e trabalhos futuros 67
viii
Lista de Figuras
2.1 Grafo completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Buraco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Grade 3 × 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 H ´e uma subdivis˜ao de G . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5 H ´e menor de G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1 Um grafo G de largura em ´arvore 2 e uma DEA ´otima de G . . . . . . . . 11
4.1 Grafo planar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.1 Estrutura ponto-ponto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.2 Estrutura triˆangulo-triˆangulo . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.3 Diamante e cap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.4 Mickey, leque, roda curta e roda gˆemea . . . . . . . . . . . . . . . . . . . . 20
5.5 Estrela, dupla-estrela e tripla-estrela . . . . . . . . . . . . . . . . . . . . . 21
5.6 2-Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.7
´
Arvore T e grafo linha de T . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.8 Grafo b´asico n˜ao-trivial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.9 Estrutura ponto-triˆangulo . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.10 V´ertices bi-simpliciais (x e y) . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.1 Grafo planar livre de buracos pares que cont´em um menor grade 3 × 3 . . . 27
6.2 Estrutura ponto-buraco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.3 Estrutura triˆangulo-buraco . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.4 Modelo de G
10×10
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
6.5 H, Modelo de G
3×2
destacado em cinza escuro e Ciclo C
em cinza claro . . 35
6.6 V´ertices x, x
, y, y
, z, z
, w, w
, x
1
, x
2
, x
3
e Ciclo C . . . . . . . . . . . . . . 36
6.7 Caso 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.8 Caso 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.9 Caso 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.1 Grafos T 1, T 2, T 3, T 4, T 5, T6, T 7 . . . . . . . . . . . . . . . . . . . . . . . 51
7.2 Grafos G1, G2, G3, G4, G5, G6, G7 . . . . . . . . . . . . . . . . . . . . . . . 56
8.1 N
G
i−1
(v
i
= n) = ∅ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
8.2 N
G
i−1
(v
i
= n) induz apenas uma clique . . . . . . . . . . . . . . . . . . . . 61
8.3 N
G
i−1
(v
i
= n) induz duas cliques que est˜ao em uma mesma componente de
G
i−1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
8.4 N
G
i−1
(v
i
= n) induz duas cliques que est˜ao em componentes distintas de G
i−1
63
x
1
Introdu¸c˜ao
Muitos problemas em grafos que modelam problemas da vida real s˜ao intrat´aveis do ponto
de vista computacional. Mais formalmente, esses problemas s˜ao N P-dif´ıceis. Uma forma
de lidar com eles ´e determinar propriedades dos grafos que os modelam que possam ser ´uteis
para encontrar um algoritmo eficiente para resolvˆe-los. Uma outra possibilidade ´e que o
problema possa ser decomposto em subproblemas que podem ser resolvidos eficientemente.
Esses dois procedimentos podem ajudar a encontrar algoritmos exatos ou aproximativos,
com ou sem garantia da qualidade da solu¸c˜ao encontrada.
Dentre as classes de grafos que s˜ao mais f´aceis de lidar, ou seja, para quais problemas
em grafos que s˜ao dif´ıceis em geral podem ser resolvidos em tempo polinomial, e at´e
mesmo em tempo linear, podemos citar as ´arvores. Por exemplo, o problema do Conjunto
Independente M´aximo ´e N P-dif´ıcil [9] em geral, mas quando o grafo de entrada ´e uma
´arvore, existe um algoritmo que resolve esse problema em tempo linear [14].
Entre 1980 e 1990, Neil Robertson e Paul Seymour definiram os parˆametros largura
em ´arvore e decomposi¸c˜ao em ´arvore de um grafo [18]. Esses conceitos foram introduzidos
no contexto de uma pesquisa fundamental sobre menores. Uma decomposi¸c˜ao em ´arvore
de um grafo procura estabelecer uma rela¸c˜ao estrutural entre as partes deste de modo
que essas sejam minimalmente conectadas, ou seja, de modo que a estrutura do grafo
assemelhe-se a uma ´arvore. A largura em ´arvore de um grafo mede a semelhan¸ca do
mesmo a uma ´arvore, de tal forma que, quanto menor for a largura em ´arvore de um
grafo, mais semelhante este ´e a uma ´arvore; e vice-versa, quanto maior for a largura em
´arvore de um grafo, menos semelhante este ´e a uma ´arvore. A no¸c˜ao de largura em ´arvore
tem sido alvo de interesse de pesquisadores por causa de suas v´arias aplica¸c˜oes, inclusive
1. Introdu¸c˜ao
em aplica¸c˜oes n˜ao necessariamente relacionadas `a teoria de grafos, como, por exemplo,
em redes probabil´ısticas (usadas por sistemas especialistas) ou computa¸c˜oes de matrizes
esparsas [11].
A largura em ´arvore de uma decomposi¸c˜ao em ´arvore de um grafo G ´e igual ao tamanho
da maior parte dessa decomposi¸c˜ao menos um. Como um mesmo grafo pode ser decomposto
em ´arvore de v´arias maneiras distintas, a largura em ´arvore de um grafo ´e igual `a menor
largura dentre todas as decomposi¸c˜oes em ´arvore desse grafo. Um grafo G tem largura em
´arvore no m´aximo k se a ele pode ser associada uma ´arvore T tal que cada n´o representa
um subgrafo de G com no m´aximo k + 1 v´ertices, de tal forma que todos os v´ertices e
arestas de G s˜ao representados em pelo menos um n´o de T e para cada v´ertice v de G, os
n´os de T que contˆem v induzem uma sub´arvore de T .
Algumas classes de grafos tˆem largura em ´arvore conhecida, por exemplo: todo ciclo
sem cordas tem largura em ´arvore igual a 2; a largura em ´arvore de todo K
n
´e igual a n−1;
todo grafo cordal tem largura em ´arvore igual ao tamanho de sua maior clique menos 1;
toda grade k × k tem largura em ´arvore exatamente igual a k [6][8]; entre outras.
Arnborg, Corneil e Proskurowski mostraram em [2] que determinar a largura em ´arvore
de um grafo qualquer ´e N P-dif´ıcil. Por outro lado, o problema de decidir, para k fixo, se
um grafo G = (V, E) qualquer possui largura em ´arvore no m´aximo k pertence a P.
Muitos problemas N P-dif´ıceis podem ser resolvidos eficientemente em grafos com
largura em ´arvore p equena atrav´es de algoritmos que utilizam t´ecnicas como Divis˜ao e
Conquista ou Programa¸c˜ao Dinˆamica [1][3][13]. Dentre tais problemas, podemos citar:
Conjunto Independente M´aximo, Ciclo Hamiltoniano, Colora¸c˜ao de V´ertices,
´
Arvore de
Steiner. Para resolver tais problemas, ´e necess´ario encontrar, primeiramente, uma decom-
posi¸c˜ao em ´arvore do grafo de largura pequena. Felizmente, para cada inteiro positivo k,
existe um algoritmo de tempo linear que, dado um grafo, encontra uma decomposi¸c˜ao em
´arvore de largura no m´aximo k do grafo, se ela existe (este algoritmo ´e exponencial em k)
[5]. Diante disso, limitar a largura em ´arvore de uma classe de grafos tem se tornado uma
tarefa de grande interesse em Teoria dos Grafos.
Um resultado bastante simples na teoria de decomposi¸c˜ao em ´arvore ´e o fato de que,
para todo grafo G, a largura em ´arvore de todo subgrafo de G ´e no m´aximo a largura em
´arvore de G. Portanto, n˜ao ´e p oss´ıvel estabelecer um limite superior para a largura em
´arvore da classe dos grafos planares, pois o fato de toda grade k ×k ser planar e ter largura
em ´arvore exatamente igual a k, implica que se um grafo planar G tem uma grade k × k
2
1. Introdu¸c˜ao
como subgrafo, ent˜ao a largura em ´arvore de G ´e pelo menos k.
Robertson, Seymour e Thomas garantem um limite superior de 6k−5 para a largura em
´arvore de grafos planares sem menor isomorfo a uma grade k × k [20]. Um limite superior
melhor de 5k − 1 foi encontrado pelos mesmos autores, por´em, tal resultado ainda n˜ao foi
publicado [24].
Diante da impossibilidade de limitar a largura em ´arvore da classe dos grafos planares,
nesta disserta¸c˜ao, estudamos o problema de determina¸c˜ao da largura em ´arvore e da de-
composi¸c˜ao em ´arvore dos grafos planares livres de buracos pares (em toda disserta¸c˜ao,
representaremos tal classe de grafos por Γ).
A principal contribui¸c˜ao desta disserta¸c˜ao de mestrado ´e o incremento da classe de
menores topol´ogicos proibidos de Γ, atrav´es da prova de que todo grafo pertencente a
Γ n˜ao possui uma grade 10 × 10 como menor topol´ogico. Tal resultado, junto com o
Teorema de Robertson, Seymour e Thomas mencionado anteriormente, nos garante um
limite superior de 49 para a largura em ´arvore de G ∈ Γ tal que todo menor grade k × k
de G pode ser obtido por uma subdivis˜ao da grade.
Al´em disso, nesta disserta¸c˜ao, o problema de gerar uma decomposi¸c˜ao em ´arvore qual-
quer para um grafo de Γ foi abordado de duas maneiras distintas. Na primeira, o Teorema
da Decomposi¸c˜ao dos grafos sem buracos pares de Conforti et al [10] foi estudado e uma
vers˜ao desse teorema foi produzida para os grafos planares. O resultado principal desse
estudo foi a limita¸c˜ao da cardinalidade dos cortes da ´arvore de decomposi¸c˜ao de Conforti
et al [10] e uma caracteriza¸c˜ao precisa dos grafos b´asicos.
Na segunda abordagem, estudamos o Teorema Estrutural dos grafos livres de buracos
pares de Chudnovsky et al [7] (doravante denominado Teorema do V´ertice Bi-simplicial)
e apresentamos um algoritmo para obter uma decomposi¸c˜ao em ´arvore de qualquer grafo
livre de buracos pares a partir desse resultado.
Esta disserta¸c˜ao est´a dividida como segue. O Cap´ıtulo 2 introduz os conceitos b´asicos
necess´arios em teoria dos grafos para o entendimento deste texto. No Cap´ıtulo 3, s˜ao
apresentadas as defini¸c˜oes formais de decomposi¸c˜ao em ´arvore e largura em ´arvore, assim
como algumas propriedades importantes de decomposi¸c˜ao em ´arvore, uma introdu¸c˜ao `a
caracteriza¸c˜ao de menores proibidos e alguns resultados importantes envolvendo largura em
´arvore. O Cap´ıtulo 4 apresenta alguns menores proibidos em grafos planares. O Cap´ıtulo
5 ´e dedicado aos grafos livres de buracos pares, apresentando as estruturas proibidas em
tal classe de grafos, o Teorema da Decomposi¸c˜ao e o Teorema do V´ertice Bi-simplicial.
3
1. Introdu¸c˜ao
No cap´ıtulo 6, ´e apresentado o resultado principal desta disserta¸c˜ao, ou seja, um limite
superior para a largura em ´arvore de G ∈ Γ tal que todo menor grade k × k de G pode
ser obtido por uma subdivis˜ao da grade. O Cap´ıtulo 7 apresenta uma vers˜ao do Teorema
da Decomposi¸c˜ao para os grafos planares. No Cap´ıtulo 8, ´e mostrado um algoritmo para a
obten¸c˜ao de uma decomposi¸c˜ao em ´arvore para todo grafo G ∈ Γ baseado no Teorema do
V´ertice Bi-simplicial. Finalmente, no Cap´ıtulo 9, apresentamos as conclus˜oes e os trabalhos
futuros.
4
2
Conceitos Preliminares
O objetivo deste cap´ıtulo ´e apresentar os conceitos b´asicos a serem utilizados ao longo do
texto, bem como a nota¸c˜ao a ser utilizada.
2.1. Defini¸c˜oes
Um grafo G ´e um par (V, E), onde V denota o conjunto de v´ertices e E o conjunto
de arestas de G. Cada aresta ´e um par n˜ao-ordenado de v´ertices u, v ∈ V , denotada por
(u, v).
Dizemos que dois v´ertices u e v s˜ao adjacentes se a aresta e = (u, v) ∈ E. Dizemos
ainda que u e v s˜ao as extremidades da aresta e e que a aresta e ´e incidente aos v´ertices
u e v. Um la¸co ´e uma aresta (u, v) onde u = v, e arestas que compartilham os mesmos
v´ertices, ou seja, e
1
, · · · , e
k
= (u, v), s˜ao chamadas arestas m´ultiplas entre u e v. Um
grafo simples G ´e um grafo sem la¸cos e sem arestas m´ultiplas.
Um grafo finito ´e um grafo tal que seus conjuntos de v´ertices e arestas s˜ao finitos. Ao
longo desta disserta¸c˜ao, um grafo refere-se a um grafo simples finito.
Os conjuntos de v´ertices e arestas de um grafo G s˜ao denotados, respectivamente, por
V (G) e E(G). Caso n˜ao haja ambiguidade, denotaremos |V | por n e |E| por m.
Uma representa¸c˜ao gr´afica de um grafo consiste de um desenho geom´etrico onde
os v´ertices s˜ao representados por pontos no plano e uma aresta e = (x, y) ´e representada
por uma linha unindo os v´ertices x e y.
Um grafo H ´e um subgrafo de G (denotamos por H ⊆ G) se V (H) ⊆ V (G) e E(H) ⊆
E(G). Quando H ⊆ G, mas H = G, n´os denotamos por H ⊂ G e chamamos H um
2. Conceitos Preliminares
subgrafo pr´oprio de G. Se H ´e um subgrafo de G, G ´e um supergrafo de H. Um
subgrafo gerador de G ´e um subgrafo H com V (H) = V (G). Suponha que V
´e um
subconjunto n˜ao-vazio de V . O subgrafo de G tal que o conjunto de v´ertices ´e V
e o
conjunto de arestas ´e o conjunto daquelas arestas de G que tem ambas as extremidades
em V
´e chamado o subgrafo induzido por V
e ´e denotado por G[V
].
Um grafo G cont´em um grafo H se H ´e um subgrafo de G, e um grafo G ´e livre de
H se G n˜ao possui H como subgrafo induzido.
Dois v´ertices s˜ao conectados em um grafo G se existe um caminho entre eles. Um
grafo G ´e dito conexo se todo par de v´ertices de G ´e conectado. Caso contr´ario, G ´e dito
desconexo. Uma componente (conexa) C de G ´e um subgrafo conexo maximal de G.
Dado um subconjunto de v´ertices S de um grafo G, G\S denota o subgrafo de G obtido
pela remo¸c˜ao de S. Um subconjunto de v´ertices S de um grafo conexo G ´e um corte de
v´ertices de G se G \ S ´e desconexo. Similarmente, um subconjunto S de arestas de um
grafo conexo G ´e um corte de arestas de G se o grafo obtido de G pela remo¸c˜ao de S ´e
desconexo.
A vizinhan¸ca de um v´ertice v ´e o conjunto N(v) = {u ∈ V : (u, v) ∈ E}, e a
vizinhan¸ca fechada N[v] de v ´e N[ v] = N(v) ∪ {v}. Da mesma forma, para todo
subconjunto U ⊆ G, utilizamos N(U) para denotar o conjunto dos v´ertices de G \ U que
s˜ao adjacentes a pelo menos um v´ertice de U e utilizamos N[U] para denotar N(U) ∪ U.
Al´em disso, dado dois subconjuntos disjuntos U, H ⊂ G, denotamos por N
H
(U) o conjunto
de v´ertices de H que tem pelo menos um vizinho em U.
Seja G = (V, E) um grafo simples qualquer. O grau d(v) de um v´ertice v ∈ V (G) ´e o
n´umero de arestas incidentes a v. Denotamos por δ(G) o grau m´ınimo e por ∆(G) o grau
m´aximo dos v´ertices de G.
Um grafo G = (V, E) ´e denominado completo se ∀a, b ∈ V (G), temos que e = (a, b) ∈
E(G), ou seja, N[v] = V para todo v ∈ V . Denotamos por K
n
o grafo completo com n
v´ertices.
Seja C ⊆ V . Se G[C] ´e um grafo completo, dizemos que C ´e uma clique de G. O
tamanho da maior clique de um grafo G ´e denotado por ω(G).
6
2. Conceitos Preliminares
Figura 2.1. Grafo completo
Um caminho entre dois v´ertices u e v de um grafo G = (V, E) ´e uma sequˆencia
de v´ertices distintos v
1
= u, v
2
, · · · , v
q
= v de tal forma que (v
i
, v
i+1
) ∈ E, para i =
1, · · · , q − 1. Tal caminho ´e dito ser sem cordas se o grafo induzido pelos v´ertices do
caminho possui apenas as arestas do caminho, ou seja, E[G[{v
1
, · · · , v
q
}]] = {(v
i
, v
i+1
) :
1 ≤ i < q}. O comprimento de um caminho ´e o n´umero de arestas que ele cont´em.
Um ciclo ´e um caminho no qual todos os v´ertices s˜ao distintos com exce¸c˜ao das ex-
tremidades, ou seja, apenas o primeiro e o ´ultimo v´ertices s˜ao iguais.
Um grafo G ´e dito acicl´ıco se n˜ao cont´em ciclos. Um grafo ´e dito triangularizado
(ou cordal), se todo ciclo de tamanho maior ou igual a quatro possui pelo menos uma
corda (aresta unindo dois v´ertices n˜ao-consecutivos do ciclo).
2.2. Algumas classes de grafos
Defini¸c˜ao 2.2.1 (Buracos). Um buraco ´e um ciclo induzido de tamanho pelo menos 4.
Denotamos por C
k
um buraco de tamanho k (k v´ertices ou arestas). Chamamos tal buraco
de k-buraco.
Figura 2.2. Buraco
Dizemos que C
k
´e um buraco par se k ´e par; por outro lado, C
k
´e ´ımpar se k ´e ´ımpar.
7
2. Conceitos Preliminares
Defini¸c˜ao 2.2.2 (
´
Arvores). Um grafo T ´e uma floresta se T ´e ac´ıclico. Um grafo T ´e
uma ´arvore se T ´e ac´ıclico e conexo. Seja T uma ´arvore. Um sub´arvore de T ´e qualquer
subgrafo de T que tamb´em ´e uma ´arvore.
Uma ´arvore T = (V, E) ´e dita enraizada quando um v´ertice ´e escolhido como especial.
Esse v´ertice ´e chamado raiz. Denotamos uma ´arvore enraizada em um v´ertice r por T
r
.
Sejam v e w dois v´ertices de uma ´arvore T enraizada de raiz r. Suponha que v perten¸ca
ao caminho de r a w em T. Ent˜ao, v ´e ancestral de w, sendo w descendente de v. Al´em
disso, se v ´e diferente de w, v ´e ancestral pr´oprio de w, e este descendente pr´oprio
de v. Se (v, w) ´e uma aresta de T , ent˜ao v ´e pai de w, sendo w filho de v. Dois v´ertices
que possuem o mesmo pai s˜ao chamados irm˜aos. A raiz de uma ´arvore n˜ao possui pai, e
todo v´ertice v diferente de r, p ossui um ´unico pai. Uma folha ´e um v´ertice que n˜ao possui
filhos.
Defini¸c˜ao 2.2.3 (Grafo Linha). Dado um grafo G, seu grafo linha tem conjunto de
v´ertices E(G) e conjunto de arestas A, onde a = e
1
e
2
∈ A se e somente se e
1
e e
2
tˆem uma
extremidade comum em G.
Um grafo G = (V, E) ´e bipartite se V (G) admite uma biparti¸c˜ao, ou seja, V (G) =
V
1
∪ V
2
e V
1
∩ V
2
= ∅, tal que se (a, b) ∈ E(G), temos que a ∈ V
1
e b ∈ V
2
ou a ∈ V
2
e
b ∈ V
1
.
Um grafo G ´e bipartite completo se ele ´e bipartite e, al´em disso, para todo u em V
1
e todo v em V
2
, (u, v) ´e uma aresta de G.
Denotamos por K
r,s
o grafo bipartite completo com |V
1
| = r e |V
2
| = s.
Defini¸c˜ao 2.2.4 (Grades). Uma grade k × l ´e um grafo G = (V, E) onde V (G) =
{(i, j) : 1 ≤ i ≤ k , 1 ≤ j ≤ l; i, j ∈ } e E(G) = {(i, j)(i
, j
) : |i − i
| + |j − j
| = 1}.
Figura 2.3. Grade 3 × 3
Em toda a disserta¸c˜ao, denotaremos uma grade k × l por G
k×l
.
8
2. Conceitos Preliminares
Uma subdivis˜ao de uma aresta e = (u, v) de um grafo G = (V, E) ´e o grafo obtido
pela troca dessa aresta por um caminho de tamanho 2, formado pelo acr´escimo de um novo
v´ertice ao grafo adjacente `as extremidades da aresta original. Uma subdivis˜ao de um
grafo G ´e um grafo obtido a partir de G por uma sequˆencia finita de subdvis˜oes de arestas.
N´os dizemos que G cont´em uma subdivis˜ao de H se existe um subgrafo de G isomorfo a
uma subdivis˜ao de H.
G
H
a
a
b
b
c
c
d d
Figura 2.4. H ´e uma subdivis˜ao de G
Se (x, y) ´e uma aresta de um grafo G, n´os denotamos por G
xy
o grafo obtido pela
contra¸c˜ao de (x, y) a um v´ertice x ∗ y; ent˜ao, V (G
xy
) = (V (G) \ {x, y}) ∪ { x ∗ y} e
E(G
xy
) = E(G) \ {x, y}) ∪ {(x ∗ y)z : xz ou yz ∈ E(G)}. Na figura 2.5, o v´ertice b ∗ d do
grafo H foi obtido atrav´es da contra¸c˜ao da aresta (b, d) do grafo G.
Defini¸c˜ao 2.2.5 (Menores). H ´e um menor de G se pode ser obtido de G por uma
sequˆencia de remo¸c˜oes de arestas, contra¸c˜oes de arestas ou remo¸c˜oes de v´ertices. Se H ´e
um menor de G, n´os dizemos que G tem um H-menor. H ´e um menor topol´ogico de G
se G cont´em uma subdivis˜ao de H como subgrafo.
a b
c
d
e
f
a
c
b*d
f
G
H
Figura 2.5. H ´e menor de G
´
E f´acil observarmos que se um grafo H ´e uma subdivis˜ao de um grafo G, G ´e um menor
de H (Figura 2.4).
9
3
Decomposi¸c˜ao em
´
Arvore
Neste cap´ıtulo, definimos formalmente decomposi¸c˜ao em ´arvore e largura em ´arvore, apre-
sentamos algumas propriedades da decomposi¸c˜ao em ´arvore que ser˜ao ´uteis nos pr´oximos
cap´ıtulos, introduzimos a caracteriza¸c˜ao de grafos por menores proibidos e, por ´ultimo, ap-
resentamos alguns resultados envolvendo menores proibidos e largura limitada de grafos.
3.1. Defini¸c˜oes
Decomposi¸c˜ao em ´arvore e largura em ´arvore podem ser definidas formalmente como:
Defini¸c˜ao 3.1.1 (Decomposi¸c˜ao em ´arvore). Uma decomposi¸c˜ao em ´arvore (DEA) D
de um grafo G = (V, E) ´e um par (X = {X
i
: i ∈ I}, T = (I, F )), sendo {X
i
: i ∈ I} uma
fam´ılia de subconjuntos de V , um para cada n´o de T , e T uma ´arvore, tais que:
•
i∈I
X
i
= V ;
• Para toda aresta (v, w) ∈ E, existe um i ∈ I tal que v ∈ X
i
e w ∈ X
i
;
• Para todo i, j, k ∈ I, se j est´a no caminho entre i e k, ent˜ao X
i
∩ X
k
⊆ X
j
.
Pela terceira propriedade da defini¸c˜ao de decomposi¸c˜ao em ´arvore acima, podemos
observar que para todo x ∈ V , os v´ertices i ∈ I tal que x ∈ X
i
induzem uma sub´arvore de
T .
Defini¸c˜ao 3.1.2 (Largura em ´arvore). A largura em ´arvore de uma decomposi¸c˜ao D =
(X = {X
i
: i ∈ I}, T = (I, F )) ´e definida como LA
G
(D) = max
i∈I
{|X
i
| − 1}. A largura
3. Decomposi¸c˜ao em
´
Arvore
em ´arvore de um grafo G ´e a largura m´ınima dentre todas as decomposi¸c˜oes em ´arvore
poss´ıveis de G, ou seja, LA(G) = min{LA
G
(D): D ´e uma decomposi¸c˜ao em ´arvore de G}.
a b c d
e
f
g
h
i
j
k
G
ab bc
dfcd
def
dfi
fi fhi fgh
dik
ijk
DEA(G)
Figura 3.1. Um grafo G de largura em ´arvore 2 e uma DEA ´otima de G
3.2. Propriedades
O objetivo desta se¸c˜ao ´e apresentar algumas propriedades de decomposi¸c˜ao em ´arvore. As
provas de todas estas propriedades podem ser encontradas em [6].
Propriedade 3.2.1. Seja G um grafo e H um subgrafo de G. Ent˜ao, LA(H) ≤ LA(G).
Propriedade 3.2.2. A largura em ´arvore de um grafo G ´e a m´axima largura em ´arvore
das componentes de G .
Propriedade 3.2.3. Seja G um grafo e H um menor de G. Ent˜ao, LA(H) ≤ LA(G).
Propriedade 3.2.4. Seja D = (X = {X
i
: i ∈ I}, T = (I, F )) uma decomposi¸c˜ao em
´arvore de G = (V, E) e seja W ⊆ G tal que W induz uma clique em G. Ent˜ao, existe um
i ∈ I tal que W ⊆ X
i
.
Propriedade 3.2.5. Seja W um corte clique de um grafo G = (V, E). Ent˜ao, LA(G) =
max{LA(G[X ∪ W ]) : X ´e uma componente de G \ W }.
3.3. Caracteriza¸c˜oes por menores proibidos
Sejam G e H grafos quaisquer. Suponhamos que H ´e um menor de G. Uma classe de
grafos C ´e fechada sobre menores se para todo grafo G e todo menor H de G, se G ∈ C,
11
3. Decomposi¸c˜ao em
´
Arvore
ent˜ao H ∈ C. Note que, para todo inteiro k ≥ 1, a classe de grafos de largura em ´arvore
no m´aximo k ´e fechada sobre menores, pela Propriedade 3.2.3.
Um outro exemplo de classe de grafos fechada sobre menores ´e a classe dos grafos
planares, pois, claramente, se um grafo G ´e planar, temos que todo subgrafo de G tamb´em
´e planar, al´em do mais, dado um desenho de G no plano, n´os podemos obter um desenho
de G
xy
, para alguma aresta (x, y), colocando x e y juntos na aresta. Robertson e Seymour
estabeleceram resultados profundos sobre menores em sua s´erie de artigos [1983-1996]. O
seguinte Teorema ´e o resultado mais importante provado por Robertson e Seymour em
[19]:
Teorema 3.3.1. Seja G
1
, G
2
, · · · uma sequˆencia cont´avel de grafos. Ent˜ao, existem´ındices
i e j, 1 ≤ i < j, tal que G
i
´e menor de G
j
.
O enunciado do Teorema 3.3.1 era formalmente conhecido como Conjectura de Wagner
[25]. Seja C uma classe de grafos fechada sobre menores (ou seja, para todo G ∈ C e H
menor de G, H ∈ C). Se um grafo H ´e tal que H ∈ C, ent˜ao cada grafo que tem H como
menor n˜ao est´a em C, pois, caso contr´ario, H estaria em C. Nesse caso, dizemos que H ´e
um menor proibido para C. Se, al´em disso, todo menor de H pertence a C, dizemos que H
´e minimal. O conjunto de menores proibidos minimais de C ´e o conjunto de obstru¸c˜oes de
C e ´e denotado por M. O Teorema 3.3.1 imediatamente implica o seguinte resultado.
Corol´ario 3.3.2. Para cada classe de grafos C fechada sobre menores, o conjunto de ob-
stru¸c˜oes tem cardinalidade finita.
Note que o Corol´ario 3.3.2 mostra que para cada k ≥ 1 fixo, a classe de grafos de
largura em ´arvore no m´aximo k tem um conjunto de obstru¸c˜oes finito.
Robertson e Seymour [1985] mostraram que para um grafo fixo H, ´e poss´ıvel checar se
H ´e um menor de um grafo G em tempo O(n
3
), onde n = |V (G)|.
Esses resultados implicam que existem algoritmos de reconhecimento de tempo O(n
3
)
para toda classe de grafos fechada sobre menores: basta testar para um grafo dado se ele
tem um menor no conjunto de obstru¸c˜oes da classe de grafos.
Infelizmente, os resultados de Robertson e Seymour somente provam a existˆencia de
um conjunto de obstru¸c˜oes finito, mas n˜ao providenciam nenhum m´etodo para obter o
conjunto de obstru¸c˜oes. Tamb´em, o algoritmo de teste dos menores tem v´arias constantes
12
3. Decomposi¸c˜ao em
´
Arvore
escondidas, o que pode tornar tal algoritmo impratic´avel. Al´em disso, o tamanho de um
conjunto de obstru¸c˜oes pode ser muito grande.
Muitos esfor¸cos tˆem sido feitos para encontrar conjuntos de obstru¸c˜oes de uma classe de
grafos fechada sobre menores. Por exemplo, Arnborg e Proskurowski [1986] encontraram o
conjunto obstru¸c˜oes das classes de grafos de largura em ´arvore no m´aximo um, dois e trˆes.
Lema 3.3.3 (Arnborg e Proskurowski, 1986). Um grafo tem largura em ´arvore no
m´aximo um se e somente se ele n˜ao tem K
3
como um menor, e largura em ´arvore no
m´aximo 2 se e somente se ele n˜ao tem K
4
como um menor.
3.4. Limites superiores e menores proibidos
Seja h(G) o maior inteiro k tal que G tem um menor grade k × k. Em [17], Robertson e
Seymour obtiveram um limite superior para LA(G) em termos de h(G):
Teorema 3.4.1. LA(G) ≤ 2
20h(G)
5
.
Em [20], Robertson, Seymour e Thomas provaram que se um grafo G planar n˜ao possui
um menor grade k × k , ent˜ao G tem largura em ´arvore no m´aximo 6k − 5. Esse limite
superior foi melhorado pelos mesmos autores para 5k − 1, por´em, tal resultado ainda n˜ao
foi publicado [24].
Teorema 3.4.2. Todo grafo planar com nenhum menor isomorfo a uma grade k × k tem
largura em ´arvore menor ou igual a 5k − 1.
Recentemente, em [4], Birmel´e, Bondy e Reed provaram um limite superior ainda mel-
hor para os grafos sem menores grade 3 × 3:
Teorema 3.4.3. Seja G um grafo sem um menor grade 3 × 3. Ent˜ao, LA(G) ≤ 7.
13
4
Grafos planares
Neste cap´ıtulo, definimos grafos planares e apresentamos alguns corol´arios do Teorema
de Kuratowski [12] que ser˜ao bastante ´uteis na demonstra¸c˜ao do principal resultado desta
disserta¸c˜ao. Tais corol´arios identificam em uma grade quais situa¸c˜oes resultam nos menores
proibidos de Kuratowski.
4.1. Defini¸c˜ao e Teorema de Kuratowski
Defini¸c˜ao 4.1.1 (Grafos planares). Um grafo G = (V, E) ´e planar se G admite uma
representa¸c˜ao gr´afica no plano sem cruzamento de arestas chamada representa¸c˜ao planar
de G.
Todos os subgrafos de um grafo planar s˜ao planares e qualquer subdivis˜ao de um grafo
n˜ao planar ´e n˜ao planar. Ao longo de toda esta disserta¸c˜ao, consideramos todos os grafos
planares em suas representa¸c˜oes gr´aficas planares. Seja G = (V, E) um grafo planar. As
arestas e os v´ertices de G dividem o plano em ´areas que s˜ao chamadas faces. Denotamos
por f(G) o n´umero de faces de G. A ´area infinita do plano ´e chamada face infinita do grafo.
Dada uma representa¸c˜ao planar de G, G admite v´arias outras representa¸c˜oes planares, onde
qualquer face de G torna-se a face infinita.
4. Grafos planares
Figura 4.1. Grafo planar
A classe dos grafos planares foi caracterizada por Kuratowski em 1930 [12], conforme
pode ser visto no teorema que segue:
Teorema 4.1.2 (Kuratowski). As seguintes afirma¸c˜oes s˜ao equivalentes para todo grafo
G:
(i) G ´e um grafo planar;
(ii) G n˜ao cont´em o K
5
ou o K
3,3
como menor;
(iii) G n˜ao cont´em o K
5
ou o K
3,3
como menor topol´ogico.
4.2. Menores proibidos em grafos planares
Corol´ario 4.2.1. Se G = (V, E) ´e um grafo planar, ent˜ao o grafo H abaixo ´e um menor
proibido de G.
d
f
cb
a
e
g
h
i
j
l
Prova: Suponhamos, por absurdo, que H ´e um menor de um grafo planar G. Seja H
o
grafo obtido a partir de H pela seguinte sequˆencia de remo¸c˜oes e contra¸c˜oes de arestas:
remove-se a aresta (f, g); contrai-se a aresta (a, d), obtendo-se o v´ertice a ∗ d; contrai-se
a aresta (a ∗ d, i), obtendo-se o v´ertice a ∗ d ∗ i; contrai-se a aresta (g, h), obtendo-se o
v´ertice g ∗ h; contrai-se a aresta (c, g ∗ h), obtendo-se o v´ertice c ∗ g ∗ h e contrai-se a aresta
(c ∗ g ∗ h, l), obtendo-se o v´ertice c ∗ g ∗ h ∗ l.
15
4. Grafos planares
Observe que H
´e isomorfo ao grafo bipartite completo K
3,3
onde H = V
1
∪V
2
, V
1
∩V
2
=
∅, V
1
= {b, e, j} e V
2
= {a ∗ d ∗ i, f, c ∗ g ∗ h ∗ l}. Portanto, pelo Teorema 4.1.2, conclu´ımos
que G n˜ao ´e um grafo planar, um absurdo. Logo, se G ´e um grafo planar, o grafo H acima
´e um menor proibido de G. ✷
Corol´ario 4.2.2. Se G = (V, E) ´e um grafo planar, ent˜ao o grafo H abaixo ´e um menor
proibido de G.
cb
a
l
d
e
f
g
i
j
k
Prova: Suponhamos, por absurdo, que H ´e um menor de um grafo planar G. Seja H
o
grafo obtido a partir de H pela seguinte sequˆencia de remo¸c˜oes e contra¸c˜oes de arestas:
remove-se as arestas (g, k) e (g, i), contrai-se o caminho induzido pelo conjunto de v´ertices
{e, j, k, l, i, c, b} a uma aresta (e, b ∗c∗i∗ l ∗k ∗j) (tal contra¸c˜ao ´e obtida por uma sequˆencia
sucessiva de contra¸c˜oes de arestas).
Observe que H
´e isomorfo ao grafo bipartite completo K
3,3
onde V
1
∪V
2
= H, V
1
∩V
2
=
∅, V
1
= {d, f, b ∗ c ∗ i ∗ l ∗ k ∗ j} e V
2
= {a, g, e}. Portanto, pelo Teorema 4.1.2, conclu´ımos
que G n˜ao ´e um grafo planar, um absurdo. Logo, se G ´e um grafo planar, o grafo H acima
´e um menor proibido de G. ✷
16
5
Grafos livres de buracos pares
Um grafo livre de buracos pares ´e um grafo que n˜ao cont´em, como um subgrafo induzido,
um buraco de comprimento par. Em [15], Porto apresenta um algoritmo polinomial para
reconhecer a classe de grafos Γ. A classe dos grafos livres de buracos pares foi estudada
sob as duas seguintes abordagens: na busca da constru¸c˜ao de grafos livre de buracos pares
a partir de grafos b´asicos (Teorema da Decomposic˜ao [10]) e na busca por propriedades
gerais comuns a qualquer grafo livre de buracos pares (Teorema do V´ertice Bi-simplicial
[7]). Neste cap´ıtulo, apresentamos esses dois resultados principais, os quais ser˜ao usados
para o estudo da decomposi¸c˜ao em ´arvore de grafos em Γ. Al´em disso, apresentamos duas
estruturas proibidas, j´a conhecidas na literatura, para a classe de grafos livres de buracos
pares.
5.1. Estruturas proibidas
Nesta se¸c˜ao, apresentamos duas estruturas proibidas, j´a conhecidas na literatura de Teoria
dos Grafos, para os grafos livres de buracos pares. Tais estruturas ser˜ao usadas na prova
do teorema principal desta disserta¸c˜ao no Cap´ıtulo 6.
Estrutura ponto-ponto
Tal estrutura consiste de dois v´ertices u e v unidos por 3 caminhos induzidos P
1
, P
2
e P
3
,
obedecendo `as seguintes restri¸c˜oes:
• Cada um dos caminhos P
1
, P
2
e P
3
tem comprimento pelo menos 2;
5. Grafos livres de buracos pares
• Os caminhos P
1
, P
2
e P
3
s˜ao disjuntos internamente em v´ertices;
• N˜ao existem cordas unindo dois caminhos P
i
e P
j
, para todo inteiro 1 ≤ i < j ≤ 3.
Com certeza, pelo menos dois desses caminhos P
1
, P
2
e P
3
tˆem a mesma paridade.
Portanto, considerando as trˆes restri¸c˜oes acima, conclu´ımos que h´a a presen¸ca de pelo
menos um buraco par nessa estrutura. Por exemplo, se P
1
e P
2
tˆem a mesma paridade,
temos que o buraco induzido por esses dois caminhos ´e um buraco par. Dessa forma,
conclu´ımos que grafos livres de buracos pares n˜ao apresentam uma estrutura ponto-ponto
como subgrafo induzido.
P
1
P
2
P
3
Figura 5.1. Estrutura ponto-ponto
Estrutura triˆangulo-triˆangulo
Tal estrutura consiste de dois triˆangulos ligados por 3 caminhos induzidos P
1
, P
2
e P
3
,
obedecendo `as seguintes restri¸c˜oes:
• Os caminhos P
1
, P
2
e P
3
s˜ao disjuntos em v´ertices;
• N˜ao existem arestas unindo dois caminhos P
i
e P
j
, para todo inteiro 1 ≤ i < j ≤ 3,
al´em das arestas dos triˆangulos.
Com o mesmo argumento utilizado com a estrutura p onto-ponto, podemos concluir
que a estrutura triˆangulo-triˆangulo cont´em pelo menos um buraco par, o que inviabiliza a
presen¸ca de tal estrutura em grafos livres de buracos pares.
Figura 5.2. Estrutura triˆangulo-triˆangulo
18
5. Grafos livres de buracos pares
5.2. Teorema da Decomposi¸c˜ao
Iniciamos esta se¸c˜ao com a introdu¸c˜ao de v´arias defini¸c˜oes necess´arias para o entendimento
do teorema da decomposi¸c˜ao, apresentado por Kapoor, Cornu´ejols, Vuskˇovi`c e Conforti em
[10]. Tal teorema resulta numa caracteriza¸c˜ao estrutural para os grafos livres de buracos
pares.
Defini¸c˜ao 5.2.1 (Leque). Um leque ´e um grafo com cinco v´ertices, tal que quatro dos
v´ertices induzem um caminho de comprimento trˆes e o quinto v´ertice ´e adjacente a todos
os v´ertices desse caminho (Figura 5.4).
Defini¸c˜ao 5.2.2 (Mickey). Um Mickey, denotado por M(xyz, H
1
, H
2
), ´e um grafo in-
duzido pelo conjunto de v´ertices V (H
1
) ∪ V (H
2
) satisfazendo:
• o conjunto {x, y, z} induz uma clique;
• H
1
´e um buraco que cont´em a aresta xy, mas n˜ao cont´em o v´ertice z;
• H
2
´e um buraco que cont´em a aresta xz, mas n˜ao cont´em o v´ertice y;
• o conjunto de v´ertices V (H
1
) ∪ V (H
2
) induz um ciclo com exatamente duas cordas,
xy e xz.
(Figura 5.4)
Um diamante ´e um ciclo de comprimento quatro com uma ´unica corda. Um cap ´e
um ciclo de comprimento maior que quatro com uma ´unica corda que forma um triˆangulo
com duas arestas do ciclo (Figura 5.10).
Cap
Diamante
Figura 5.3. Diamante e cap
Uma roda, denotada por (H, x), ´e um grafo induzido por um buraco H e um v´ertice
x /∈ V (H) tendo pelo menos trˆes vizinhos em H, digamos x
1
, · · · , x
n
. O v´ertice x ´e o centro
19
5. Grafos livres de buracos pares
da roda. O buraco H ´e chamado o aro da roda. Um subcaminho de H conectando x
i
e x
j
´e um setor se ele n˜ao cont´em v´ertice intermedi´ario x
l
, i ≤ l ≤ j, adjacente a x. Um
setor curto ´e um setor de comprimento 1 (isto ´e, ele consiste de uma aresta), e um setor
longo ´e um setor de comprimento pelo menos 2. Uma roda ´e par se ela cont´em um n´umero
par de setores. Uma roda com k-setores ´e chamada uma k-roda.
Defini¸c˜ao 5.2.3 (Roda gˆemea, Roda curta, Roda pr´opria). Uma roda gˆemea ´e
uma 3-roda com exatamente dois setores curtos. Uma roda ´e pr´opria se ela n˜ao ´e uma
roda gˆemea. Uma roda curta ´e uma 3-roda com exatamente dois setores longos (Figura
5.4).
Leque Mickey
Roda curta
Roda gemea
Figura 5.4. Mickey, leque, roda curta e roda gˆemea
Uma k-estrela ´e um grafo formado de uma clique C de tamanho k e um subconjunto
dos v´ertices que possuem pelo menos um vizinho em C. N´os nos referimos `a 1-estrela
como estrela, 2-estrela como dupla-estrela e 3-estrela como tripla-estrela. Em um
grafo conexo G, um corte k-estrela ´e um conjunto de v´ertices S ⊆ V (G) que induz uma
k-estrela e cuja remo¸c˜ao desconecta G.
20
5. Grafos livres de buracos pares
1−estrela
2−estrela
3−estrela
Figura 5.5. Estrela, dupla-estrela e tripla-estrela
Defini¸c˜ao 5.2.4 (2-Join). Um grafo conexo G tem um 2-join, denotado por H
1
|H
2
,
com conjuntos especiais A
1
,B
1
,A
2
,B
2
, n˜ao-vazios e disjuntos, se os v´ertices de G p odem ser
particionados em conjuntos H
1
e H
2
tal que A
1
, B
1
⊆ H
1
, A
2
, B
2
⊆ H
2
, todos os v´ertices
de A
1
s˜ao adjacentes a todos os v´ertices de A
2
, todos os v´ertices de B
1
s˜ao adjacentes a
todos os v´ertices de B
2
e estas s˜ao as ´unicas adjacˆencias entre H
1
e H
2
. Ademais, para
i = 1, 2, |H
i
| > 2, e se A
1
e B
1
(respectivamente A
2
e B
2
) s˜ao ambos de cardinalidade 1,
ent˜ao o grafo induzido por H
1
(respectivamente H
2
) n˜ao ´e um caminho sem cordas.
A_1
B_1
A_2
B_2
H_2H_1
Figura 5.6. 2-Join
Seja L o grafo linha de uma ´arvore qualquer (Defini¸c˜ao 2.2.3). As observa¸c˜oes que
faremos a seguir sao ´uteis para a defini¸c˜ao da classe de grafos b´asicos n˜ao-triviais do
teorema da decomposi¸c˜ao. Como trata-se de uma ´arvore, observe que toda aresta de L
pertence a exatamente uma clique maximal e todo v´ertice de L pertence a no m´aximo duas
clique maximais. Os v´ertices de L que pertencem a exatamente uma clique maximal s˜ao
chamados v´ertices folhas. Uma clique de L ´e grande se ela tem tamanho pelo menos 3.
No grafo obtido de L pela remo¸c˜ao de todas as arestas em cliques grandes, as componentes
21
5. Grafos livres de buracos pares
conexas s˜ao caminhos sem cordas (possivelmente de comprimento zero). Um caminho P ´e
um segmento interno se ele tem suas extremidades em cliques grandes distintas (quando P
´e de comprimento zero, ele ´e chamado um segmento interno quando o v´ertice de P pertence
a duas cliques grandes). Os outros caminhos de P s˜ao chamados segmentos folhas. Note
que uma das extremidade de um segmento folha ´e um v´ertice folha.
a
b
c
d
e
f
a
d
e
b
c
f
LG(T)T
Figura 5.7.
´
Arvore T e grafo linha de T
Defini¸c˜ao 5.2.5 (Grafo b´asico n˜ao-trivial). Um grafo R ´e b´asico n˜ao-trivial se R
cont´em dois v´ertices adjacentes x e y, chamados v´ertices especiais, de forma que o grafo
linha L induzido por R \ {x, y} ´e um grafo linha de uma ´arvore e cont´em pelo menos duas
cliques grandes. Al´em disso, as seguintes condi¸c˜oes devem ser satisfeitas:
• Em R, cada v´ertice folha de L ´e adjacente a exatamente um dos dois v´ertices especiais,
e nenhum outro v´ertice de L ´e adjacente aos n´os especiais.
• Cada dois segmentos folhas de L com seus respectivos v´ertices folhas adjacentes a um
mesmo v´ertice especial, n˜ao possuem suas outras extremidades numa mesma clique
grande.
22
5. Grafos livres de buracos pares
x
y
Figura 5.8. Grafo b´asico n˜ao-trivial
Pode-se estender a nota¸c˜ao de
L
a
R
, dizendo que os segmentos internos de
R
s˜ao os
segmentos internos de L, e os segmentos folhas de R s˜ao os segmentos folhas de L junto
com o v´ertice em {x, y} para o qual o segmento folha ´e adjacente.
Defini¸c˜ao 5.2.6 (Estrutura ponto-triˆangulo). Dado um triˆangulo {x, z, w} e um v´ertice
y adjacente a no m´aximo um v´ertice de {x, z, w}, uma estrutura ponto-triˆangulo ´e
um grafo induzido por trˆes caminhos sem cordas P
x
= x, · · · , y, P
z
= z, · · · , y e
P
w
= w , · · · , y de tal forma que esses caminhos se intersectam dois a dois apenas no
v´ertice y e as ´unicas adjacˆencias entre os n´os de P
x
\ y, P
z
\ y e P
w
\ y s˜ao as arestas do
triˆangulo {x, z, w}.
Figura 5.9. Estrutura ponto-triˆangulo
Um grafo b´asico trivial ´e um grafo isomorfo a uma estrutura ponto-triˆangulo. Um
grafo ´e b´asico se ele ´e uma grafo b´asico trivial ou um grafo b´asico n˜ao-trivial.
O Teorema da Decomposi¸c˜ao foi feito para uma classe de grafos mais geral do que a
classe de grafos livres de buracos pares. Tal classe consiste nos grafos ´ımpar-rotul´aveis.
Um grafo ´e rotulado pela atribui¸c˜ao de pesos 0,1 as suas arestas de tal forma que, para
todo triˆangulo no grafo, a soma dos pesos das arestas de tal triˆangulo ´e ´ımpar. Um grafo
´e ´ımpar-rotul´avel se existe uma rotula¸c˜ao de suas arestas de tal forma que, para todo
23
5. Grafos livres de buracos pares
buraco em G, a soma dos p esos de suas arestas ´e ´ımpar. De fato, um grafo n˜ao possui
buracos pares se e somente se ele ´e ´ımpar-rotulado quando todas as arestas recebem r´otulo
1 [10]. Isso implica que para todo grafo livre de buracos pares, existe uma rotula¸c˜ao ´ımpar
adequada e, p ortanto, essa classe est´a estritamente contida na classe dos grafos ´ımpar-
rotul´aveis. Nesta disserta¸c˜ao, estamos interessados na classe dos grafos livres de buracos
pares, portanto, o Teorema da Decomposi¸c˜ao, provado por Kapoor, Cornu´ejols, Vuskˇovi`c
e M. Conforti em [10], ser´a enunciado em termos dessa classe de grafos.
Teorema 5.2.7 (Teorema da Decomposi¸c˜ao). Seja G um grafo livre de buracos pares
conexo. Ent˜ao, ou G ´e b´asico ou livre de cap, ou ele tem um 2-join ou ele tem um corte
estrela, dupla-estrela ou tripla-estrela.
A demonstra¸c˜ao do Teorema da Decomposi¸c˜ao, que n˜ao ser´a explorada aqui, implica
que a todo grafo livre de buracos pares pode ser associada uma ´arvore de decomposi¸c˜ao
enraizada obtida como apresentado no Algoritmo 1.
24
5. Grafos livres de buracos pares
Algoritmo 1 Construir a ´arvore de decomposi¸c˜ao T de G sem buracos pares
Entrada: Grafo G livre de buracos pares
Sa´ıda:
´
Arvore de Decomposi¸c˜ao T de G
Considere r a raiz da ´arvore T
Seja H
r
representado por r em T
H
r
← G
V (T ) ← {r}
E(T ) ← ∅
Seja Q uma fila
Insira r em Q
enquanto Q = ∅ fa¸ca
Seja x o primeiro v´ertice da fila Q
Seja H
x
o subgrafo de G representado por x em T
se H
x
tem um corte-estrela, dupla-estrela ou tripla-estrela ent˜ao
Seja C um corte de H
x
de tal tipo
para cada componente S de H
x
\ C fa¸ca
V (T ) ← V (T ) ∪ {s}
Seja H
s
o subgrafo de G representado por s em T
H
s
← S ∪ C
Insira s em Q
E(T ) ← E(T ) ∪ {sx}
fim para
sen˜ao
se H
x
tem um 2-join ent˜ao
Seja J um 2-join de H
x
para cada bloco B de J fa¸ca
V (T ) ← V (T ) ∪ {b}
Seja H
b
o subgrafo de G representado por b em T
H
b
← B
Insira b em Q
E(T ) ← E(T ) ∪ {bx}
fim para
sen˜ao
x ´e uma folha da ´arvore T , ou seja, H
x
´e um grafo b´asico ou ´e livre de cap
fim se
fim se
Retirar x de Q
fim enquanto
25
5. Grafos livres de buracos pares
5.3. Teorema do V´ertice Bi-simplicial
Seja G um grafo qualquer. Um v´ertice ´e bi-simplicial em G se a sua vizinhan¸ca pode ser
particionada em duas cliques. Tais cliques n˜ao s˜ao necessariamente n˜ao-vazias.
Seja v um v´ertice bi-simplicial em G. Seja Q
1
e Q
2
as duas cliques em que os vizinhos
de v s˜ao particionados.
´
E poss´ıvel que haja arestas unindo Q
1
e Q
2
.
x
y
Figura 5.10. V´ertices bi-simpliciais (x e y)
Em [16], Bruce Reed conjecturou que todo grafo livre de buracos pares tem um v´ertice
bi-simplicial. Tal conjectura foi provada em [7] por Addario-Berry, Chudnovsky, Havet,
Reed e Seymour e consiste no Teorema do V´ertice Bi-simplicial.
´
E f´acil vermos que se G ´e um grafo livre de buracos pares, ent˜ao todo subgrafo induzido
de G tamb´em ´e livre de buracos pares, logo, todo subgrafo induzido de G tamb´em tem
um v´ertice bi-simplicial. Dessa forma, conclu´ımos que G possui uma ordem de elimina¸c˜ao
v
n
, v
n−1
, · · · , v
2
, v
1
por v´ertices bi-simpliciais, ou seja, em tal ordem, o v´ertice v
i
´e bi-
simplicial em G
i
= G[v
i
, v
i−1
, · · · , v
1
] (chamaremos tal ordem de ordem de elimina¸c˜ao
bi-simplicial). Observe que cada subgrafo G
i
de G n˜ao ´e necessariamente conexo, mesmo
que G
1
= G seja conexo.
Se um grafo G tem uma ordem de elimina¸c˜ao bi-simplicial, n˜ao necessariamente G ´e
um grafo livre de buracos pares. Como contra-exemplo trivial, podemos citar qualquer
buraco par.
Teorema 5.3.1 (Teorema do V´ertice Bi-simplicial). Todo grafo livre de buracos pares
n˜ao-nulo tem um v´ertice bi-simplicial.
26
6
Largura em ´arvore de grafos planares livres de
buracos pares
Neste cap´ıtulo, provamos que todo grafo G de Γ n˜ao possui um menor topol´ogico grade
10 × 10. A partir desse ´ultimo resultado, usando o Teorema 3.4.2, podemos afirmar que
se todos os menores grade de G em Γ s˜ao menores topol´ogicos, ent˜ao G possui largura em
´arvore no m´aximo 49.
6.1. Menor grade 3 × 3 em grafos planares livres de buracos pares
Uma poss´ıvel abordagem para limitar o tamanho da menor grade de um grafo G ∈ Γ ´e
tentar construir grafos livres de buracos pares com grandes menores de grades. Um grafo
da classe Γ que possui um menor grade 3 × 3 ´e apresentado na Figura 6.3.
Figura 6.1. Grafo planar livre de buracos pares que cont´em um menor grade 3 × 3
Esse grafo tem exatamente um buraco de tamanho 15 e trˆes buracos de tamanho 5
como subgrafos induzidos. Para obter-se um menor grade 3 × 3, basta remover as arestas
tra¸cadas diagonalmente e aplicar em seguida uma seq¨uˆencia de contra¸c˜oes de arestas.
6. Largura em ´arvore de grafos planares livres de buracos pares
6.2. Um limite superior para uma subclasse
Nesta se¸c˜ao, provamos o seguinte teorema:
Teorema 6.2.1. Se G ´e um grafo planar livre de buracos pares, ent˜ao G n˜ao possui uma
grade 10 × 10 como menor topol´ogico.
Os Teoremas 3.4.2 e 6.2.1 tˆem como conseq¨uˆencia o seguinte corol´ario:
Corol´ario 6.2.2. Seja G um grafo planar livre de buracos pares. Se todo menor grade
k × k de G ´e obtido por uma subdivis˜ao da grade, ent˜ao LA(G) ≤ 49.
As seguintes defini¸c˜oes ser˜ao usadas na prova do Teorema 6.2.1. Durante toda a prova,
G ´e um grafo planar, em sua representa¸c˜ao planar, e livre de buracos pares.
Defini¸c˜ao 6.2.3 (Estrutura ponto-buraco). Uma estrutura ponto-buraco ´e formada
por um v´ertice, x, um buraco, H, x /∈ H, e trˆes caminhos induzidos, P
1
, P
2
e P
3
, unindo x
e H, disjuntos dois a dois (coincidem somente no v´ertice x), sem cordas entre si e tais que
para cada caminho P
i
, 1 ≤ i ≤ 3, o n´umero de v´ertices internos de P
i
que possui vizinhos
em H ´e exatamente igual a um.
H
P1 P2 P3
x
x1
x2
x3
Figura 6.2. Estrutura ponto-buraco
Defini¸c˜ao 6.2.4 (Estrutura triˆangulo-buraco). Uma estrutura triˆangulo-buraco ´e for-
mada por um K
3
, x, y, z, um buraco, H, x, y, z /∈ H, e trˆes caminhos induzidos, P
x
, P
y
,
P
z
, unindo x, y, z a H, respectivamente. Al´em disso, P
x
, P
y
e P
z
s˜ao disjuntos dois a dois,
sem cordas entre si e tais que para cada um dos caminhos P
x
, P
y
, P
z
, o n´umero de v´ertices
internos que possuem vizinhos em H ´e exatamente igual a um.
28
6. Largura em ´arvore de grafos planares livres de buracos pares
H
zx
y
Px
Py
Pz
Figura 6.3. Estrutura triˆangulo-buraco
Seja G um grafo qualquer que cont´em um menor topol´ogico G
k×l
. Dizemos que H ´e
um modelo de G
k×l
em G se H ´e um subgrafo minimal induzido de G que cont´em uma
subdivis˜ao de G
k×l
. Observe que H n˜ao ´e necessariamente uma subdivis˜ao de G
k×l
(Figura
6.4).
Seja H um modelo de G
k×l
. Temos que H possui k ∗ l v´ertices prim´arios, representados
por v
i,j
, 1 ≤ i ≤ k e 1 ≤ j ≤ l, que obedecem `as seguintes restri¸c˜oes (Figura 6.4):
1. Para o v´ertice v
1,1
, existem os caminhos L
1
[1, 2] e C
1
[1, 2] unindo v
1,1
e os v´ertices
v
1,2
, v
2,1
, respectivamente, e interceptando-se somente no v´ertice v
1,1
;
2. Para o v´ertice v
1,l
, existem os caminhos L
1
[l − 1, l ] e C
l
[1, 2] unindo v
1,l
e os v´ertices
v
1,l−1
, v
2,l
, respectivamente, e interceptando-se somente no v´ertice v
1,l
;
3. Para o v´ertice v
k,1
, existem os caminhos L
k
[1, 2] e C
1
[k −1, k] unindo v
k,1
e os v´ertices
v
k,2
, v
k−1,1
, respectivamente, e interceptando-se somente no v´ertice v
k,1
;
4. Para o v´ertice v
k,l
, existem os caminhos L
k
[l − 1, l] e C
l
[k − 1, k] unindo v
k,l
e os
v´ertices v
k,l−1
, v
k−1,l
, respectivamente, e interceptando-se somente no v´ertice v
k,l
;
5. Para todo v´ertice v
i,j
, onde 1 < i < k e 1 < j < l, existem caminhos L
i
[j − 1, j],
L
i
[j, j + 1], C
j
[i − 1, i] e C
j
[i, i + 1] unindo v
i,j
e os v´ertices v
i,j−1
, v
i,j+1
, v
i−1,j
, v
i+1,j
,
respectivamente, e interceptando-se dois a dois somente no v´ertice v
i,j
;
6. Para todo v´ertice v
i,j
, onde i = 1 e 1 < j < l, existem caminhos L
i
[j − 1, j],
L
i
[j, j + 1] e C
j
[i, i + 1] unindo v
i,j
e os v´ertices v
i,j−1
, v
i,j+1
, v
i+1,j
, respectivamente,
e interceptando-se dois a dois somente no v´ertice v
i,j
;
29
6. Largura em ´arvore de grafos planares livres de buracos pares
7. Para todo v´ertice v
i,j
, onde i = k e 1 < j < l, existem caminhos L
i
[j − 1, j],
L
i
[j, j + 1] e C
j
[i − 1, i] unindo v
i,j
e os v´ertices v
i,j−1
, v
i,j+1
, v
i−1,j
, respectivamente,
e interceptando-se dois a dois somente no v´ertice v
i,j
;
8. Para todo v´ertice v
i,j
, onde 1 < i < k e j = 1, existem caminhos C
j
[i − 1, i],
C
j
[i, i + 1] e L
i
[j, j + 1] unindo v
i,j
e os v´ertices v
i−1,j
, v
i+1,j
, v
i,j+1
, respectivamente,
e interceptando-se dois a dois somente no v´ertice v
i,j
;
9. Para todo v´ertice v
i,j
, onde 1 < i < k e j = l, existem caminhos C
j
[i − 1, i],
C
j
[i, i + 1] e L
i
[j − 1, j] unindo v
i,j
e os v´ertices v
i−1,j
, v
i+1,j
, v
i,j−1
, respectivamente,
e interceptando-se dois a dois somente no v´ertice v
i,j
;
10. N˜ao h´a interse¸c˜ao entre cada dois caminhos definidos nos itens anteriores al´em das
interse¸c˜oes j´a destacadas;
11. Para todo inteiro i, 1 ≤ i ≤ k, consideramos o caminho L
i
=
l−1
j=1
L
i
[j, j + 1] a
i-´esima linha principal de H;
12. De maneira an´aloga, para todo inteiro j, 1 ≤ j ≤ l, consideramos o caminho C
j
=
k−1
i=1
C
j
[i, i + 1] a j-´esima coluna principal de H.
Os demais v´ertices de H s˜ao chamamos secund´arios. Denotamos por L
i
[u, v], 1 ≤ i ≤ k,
u, v ∈ L
i
, o caminho entre u e v contendo somente v´ertices de L
i
. Utilizamos |L
i
[u, v]|
para representar o comprimento do caminho L
i
[u, v]. De maneira an´aloga, denotamos por
C
j
[u, v], 1 ≤ j ≤ l, u, v ∈ C
j
, o caminho entre u e v contendo somente v´ertices de C
j
.
Utilizamos |C
j
[u, v]| para representar o comprimento do caminho C
j
[u, v]. Para 1 ≤ i ≤ k
e 1 ≤ r < s ≤ l, denotamos por L
i
[r, s] o caminho entre os v´ertices prim´arios v
i,r
e v
i,s
contendo somente v´ertices de L
i
. Da mesma forma, para 1 ≤ j ≤ l e 1 ≤ r < s ≤ k,
denotamos por C
j
[r, s] o caminho entre os v´ertices prim´arios v
r,j
e v
s,j
contendo somente
v´ertices de C
j
. Utilizamos parˆenteses ao inv´es de colchetes quando nos referirmos ao
caminho sem tal extremidade, por exemplo, L
1
[3, 5) representa o caminho entre os v´ertices
prim´arios v
1,3
e v
1,5
em L
1
de H, incluindo v
1,3
e excluindo v
1,5
.
Na Figura 6.4, as linhas representam caminhos. Na mesma figura, os v´ertices v
1,1
, v
4,8
,
v
4,9
, v
6,5
, v
9,8
e v
10,10
s˜ao prim´arios e os v´ertices x, y e z s˜ao secund´arios.
30
6. Largura em ´arvore de grafos planares livres de buracos pares
v1,1
x
y
v6,5
z
v4,8
v4,9
v9,8
v10,10
Figura 6.4. Modelo de G
10×10
6.2.1. Lemas
O objetivo dessa subse¸c˜ao ´e apresentar um lema e duas observa¸c˜oes que ser˜ao utilizados
na prova do Teorema 6.2.1.
Lema 6.2.5. Se P = v
1
, v
2
, · · · , v
k−1
, v
k
´e um caminho com cordas entre um v´ertice v
1
e um v´ertice v
k
em um grafo G = (V, E) qualquer, k ≥ 3, ent˜ao P cont´em um caminho
induzido P
entre os v´ertices v
1
e v
k
.
A Observa¸c˜ao 6.2.6 ´e conseq¨uˆencia direta dos Corol´arios 4.2.1 e 4.2.2:
Observa¸c˜ao 6.2.6. Seja G = (V, E) um grafo planar qualquer que cont´em um menor
topol´ogico G
k×l
e seja H um modelo de G
k×l
em G. Ent˜ao, em H, para 1 < i < k e
1 ≤ j < l, a vizinhan¸ca de L
i
(j, j + 1) est´a contida em L
i−1
[j, j + 1] ∪ L
i+1
[j, j + 1] ∪ C
j
[i −
1, i + 1] ∪ C
j+1
[i − 1, i + 1]. Analogamente, para 1 < j < l e 1 ≤ i < k, a vizinhan¸ca de
C
j
(i, i + 1) est´a contida em C
j−1
[i, i + 1] ∪ C
j+1
[i, i + 1] ∪ L
i
[j − 1, j + 1] ∪ L
i+1
[j − 1, j + 1].
31
6. Largura em ´arvore de grafos planares livres de buracos pares
A Observa¸c˜ao 6.2.7 ´e conseq¨uˆencia direta do fato de um modelo H em um grafo G
ser um subgrafo minimal induzido com rela¸c˜ao `a propriedade de conter uma subdivis˜ao de
G
k×l
:
Observa¸c˜ao 6.2.7. Seja G = (V, E) um grafo planar qualquer que cont´em um menor
topol´ogico G
k×l
e seja H um modelo de G
k×l
em G. Ent˜ao, em H, para 1 ≤ i ≤ k e
1 ≤ j ≤ l − 1, L
i
[j, j + 1] ´e um caminho induzido. Analogamente, para 1 ≤ j ≤ l e
1 ≤ i ≤ k − 1, C
j
[i, i + 1] ´e um caminho induzido.
6.2.2. Prova do Teorema 6.2.1
Seja G um grafo de Γ. Nesta subse¸c˜ao, vamos provar que G n˜ao possui uma grade 10 × 10
como menor topol´ogico.
A prova do Teorema 6.2.1 ser´a feita em duas etapas: a primeira etapa consiste em
mostrar que se G ´e um grafo de Γ, ent˜ao G ´e livre de determinadas estruturas (Lema 6.2.8).
A segunda etapa consiste em mostrar que um modelo de G
10×10
possui necessariamente
tais estruturas (Lema 6.2.9). Os Lemas 6.2.8 e 6.2.9 implicam o Teorema 6.2.1.
Lema 6.2.8. Se G ´e um grafo planar livre de buracos pares, ent˜ao G ´e livre de estruturas
ponto-buraco e triˆangulo-buraco, em que os caminhos tˆem comprimento pelo menos dois
e as vizinhan¸cas dos caminhos no buraco s˜ao separadas por pelo menos um v´ertice.
Prova: Denotemos por P
1
, P
2
e P
3
os caminhos da estrutura em quest˜ao e por H, o buraco.
Analisamos os seguintes casos:
(i) Existem P
i
, P
j
tais que |N
H
(P
i
)| ≥ 3 e |N
H
(P
j
)| ≥ 3: Sejam x
i
e x
j
os v´ertices
internos de P
i
e P
j
vizinhos a H, respectivamente (note que s˜ao ´unicos, devido `as
defini¸c˜oes de estrutura ponto-buraco e triˆangulo-buraco). Numere os v´ertices de H,
v
1
, · · · , v
q
, de forma que todos os vizinhos de x
i
ocorram antes de todos os vizinhos
de x
j
(note que isso ´e poss´ıvel, pois o grafo ´e planar). Sejam v
e
i
o vizinho de x
i
mais `a esquerda na ordem e v
d
i
, o mais `a direita. Defina v
e
j
e v
d
j
com rela¸c˜ao a x
j
analogamente. Nesse caso, temos uma contradi¸c˜ao, devido `a existˆencia da estrutura
ponto-ponto unindo os v´ertices x
i
e x
j
formada pelos seguintes caminhos: caminho
unindo v
e
i
e v
d
j
em H que n˜ao passa por v
d
i
e v
e
j
; caminho unindo v
d
i
e v
e
j
em H que
n˜ao passa por v
e
i
e v
d
j
; e caminho formado pela uni˜ao dos caminhos P
i
e P
j
, passando
32
6. Largura em ´arvore de grafos planares livres de buracos pares
pelo v´ertice ou triˆangulo (dependendo de qual estrutura se trata, se ponto-buraco ou
triˆangulo-buraco). Note que, se N
H
(P
i
) = {v, v
}, por´em v ∈ N(v
), ainda ´e poss´ıvel
tomar os caminhos descritos anteriormente. O mesmo ocorre pra P
j
, obviamente.
(ii) Existem P
i
, P
j
tais que N
H
(P
i
) = {v
i
} e N
H
(P
j
) = {v
j
}: nesse caso, ´e f´acil vermos
que temos uma estrutura ponto-ponto unindo os v´ertices v
i
e v
j
, formada pelos trˆes
seguintes caminhos: dois deles definidos por H (cada caminho ter´a pelo menos um
v´ertice intermedi´ario, devido `a premissa) e o terceiro caminho definido pela uni˜ao
dos caminhos P
i
e P
j
(caso se trate de uma estrutura triˆangulo-buraco, o caminho
conter´a tamb´em a aresta do triˆangulo unindo os caminhos P
i
e P
j
).
(iii) N
H
(P
i
) = {v
1
, v
2
}, N
H
(P
j
) = {u
1
, u
2
}: nesse caso, vamos mostrar que (v
1
, v
2
) e
(u
1
, u
2
) s˜ao obrigatoriamente arestas de H. Sem perda de genaralidade, suponhamos
por absurdo, que (v
1
, v
2
) n˜ao ´e uma aresta de H. Logo, ´e f´acil vermos que o grafo
possui uma estrutura ponto-ponto unindo os v´ertices v
1
e v
2
(dois dos caminhos
dessa estrutura est˜ao em H e o outro ´e formado por {v, v
1
, v
2
} onde v ∈ P
i
´e o
v´ertice adjacente a v
1
e v
2
). Agora, sabendo que (v
1
, v
2
), (u
1
, u
2
) ∈ E(H), sejam
v ∈ P
i
\{v
1
, v
2
} e u ∈ P
j
\{u
1
, u
2
} vizinhos de H (s˜ao unicamente definidos, devido `as
defini¸c˜oes das estruturas ponto-buraco e triˆangulo-buraco). Numere os v´ertices de H
a partir de v
1
e suponha, sem perda de generalidade, que v
1
, v
2
, u
1
, u
2
aparecem nesta
mesma ordem ap´os a numera¸c˜ao. Logo, nesse caso, temos uma estrutura triˆangulo-
triˆangulo no grafo formada pelos dois K
3
, v
1
, v
2
, v e u
1
, u
2
, u, e caminhos entre v
1
e u
2
, v
2
e u
1
contidos em H, e entre u e v definido pela uni˜ao dos caminhos P
i
e P
j
passando pelo v´ertice ou triˆangulo da estrutura.
(iv) |N
H
(P
i
)| ≥ 3 e N
H
(P
j
) = {v}: numere os v´ertices de H a partir de v e seja x
i
o v´ertice
interno de P
i
que possui um vizinho em H, e v
e
i
e v
d
i
, o vizinho mais `a esquerda de x
i
na
ordem e o mais `a direita, respectivamente. Temos uma estrutura ponto-ponto unindo
os v´ertices x
i
e v e formada pelos trˆes seguintes caminhos induzidos, de comprimento
pelo menos dois, disjuntos e sem cordas entre si: subcaminho v = v
1
, · · · , v
e
i
, x
i
de H na ordem dada; subcaminho x
i
, v
d
i
, · · · , v
|H|
, v
1
= v de H na ordem dada; e
caminho entre v e x
i
passando somente pelos v´ertices dos caminhos P
i
e P
j
.
Note que, pelos itens (i) a (iii), a ´unica possibilidade de existˆencia da estrutura descrita
no teorema ´e que um dentre os caminhos P
1
,P
2
e P
3
possua exatamente um vizinho em
33
6. Largura em ´arvore de grafos planares livres de buracos pares
H, um possua exatamente dois vizinhos em H e o ´ultimo possua trˆes ou mais vizinhos em
H, por´em, pelo item (iv), isso tamb´em n˜ao ´e poss´ıvel. Logo, G n˜ao possui como subgrafo
induzido uma estrutura ponto-buraco ou triˆangulo-buraco como descrita no enunciado do
lema.
✷
A partir de agora, consideramos uma estrutura proibida em um grafo G de Γ, uma
estrutura ponto-buraco ou triˆangulo-buraco descrita como no Lema 6.2.8.
Lema 6.2.9. Se G cont´em um menor topol´ogico G
10×10
, ent˜ao G possui uma estrutura
proibida como subgrafo induzido.
Prova: Seja H um modelo de G
10×10
de G. Em toda a prova, considere a nota¸c˜ao anterior-
mente introduzida para os v´ertices de H. A prova ser´a feita por constru¸c˜ao e dividida em
duas partes, onde a primeira parte consiste em apresentar o buraco C que ser´a utilizado
para induzir uma estrutura proibida em G e a segunda parte consiste em provar que existe
um v´ertice x ou um K
3
em H e trˆes caminhos P
1
, P
2
e P
3
partindo de x ou do K
3
de tal
forma que P
1
∪ P
2
∪ P
3
∪ C induzem uma estrutura proibida em H.
Parte 1: Considere o ciclo C
= L
3
[5, 9] ∪ C
9
[3, 7] ∪ L
7
[5, 9] ∪ C
5
[3, 7]. A Figura 6.5
representa H, onde o ciclo destacado em cinza claro representa C
. Observe que C
n˜ao
´e necessariamente um ciclo induzido, pois podem existir arestas entre C
5
(3, 4] e L
3
(5, 6],
C
9
(3, 4] e L
3
[8, 9), C
5
[6, 7) e L
7
(5, 6] ou C
9
[6, 7) e L
7
[8, 9). Al´em disso, pela Observa¸c˜ao
6.2.6, essas s˜ao as ´unicas poss´ıveis cordas de C
. Dessa forma, a fim de obtermos um ciclo
induzido C contido em C
, considere os seguintes v´ertices:
1. Seja x o v´ertice de C
5
[3, 4] mais pr´oximo do v´ertice prim´ario v
4,5
que ´e adjacente a
pelo menos um v´ertice de L
3
(5, 6];
2. Seja x
o v´ertice de L
3
(5, 6] mais pr´oximo do v´ertice prim´ario v
3,6
que ´e adjacente ao
v´ertice x;
3. Seja y o v´ertice de C
9
[3, 4] mais pr´oximo do v´ertice prim´ario v
4,9
que ´e adjacente a
pelo menos um v´ertice de L
3
[8, 9);
4. Seja y
o v´ertice de L
3
[8, 9) mais pr´oximo do v´ertice prim´ario v
3,8
que ´e adjacente ao
v´ertice y;
34
6. Largura em ´arvore de grafos planares livres de buracos pares
5. Seja z o v´ertice de C
9
[6, 7] mais pr´oximo do v´ertice prim´ario v
6,9
que ´e adjacente a
pelo menos um v´ertice de L
7
[8, 9);
6. Seja z
o v´ertice de L
7
[8, 9) mais pr´oximo do v´ertice prim´ario v
7,8
que ´e adjacente ao
v´ertice z;
7. Seja w o v´ertice de C
5
[6, 7] mais pr´oximo do v´ertice prim´ario v
6,5
que ´e adjacente a
pelo menos um v´ertice de L
7
(5, 6];
8. Seja w
o v´ertice de L
7
(5, 6] mais pr´oximo do v´ertice prim´ario v
7,6
que ´e adjacente ao
v´ertice w.
12345678910
1
2
3
4
5
6
7
8
9
10
Figura 6.5. H, Modelo de G
3×2
destacado em cinza escuro e Ciclo C
em cinza claro
Pelas Observa¸c˜oes 6.2.6 e 6.2.7 e pelas escolhas dos v´ertices x, x
, y, y
, z, z
, w, w
, con-
clu´ımos que C = L
3
[x
, y
] ∪C
9
[y, z] ∪ L
7
[w
, z
] ∪C
5
[x, w] ´e um ciclo induzido com tamanho
pelo menos 10.
O ciclo C e os v´ertices x, x
, y, y
, z, z
, w, w
s˜ao representados na Figura 6.6.
35
6. Largura em ´arvore de grafos planares livres de buracos pares
12345678910
1
2
3
4
5
6
7
8
9
10
P´1
P´3
P´2
X
2
X
X’
Y
Y’
W
W’
Z
Z’
X
3
X
1
C
Figura 6.6. V´ertices x, x
, y, y
, z, z
, w, w
, x
1
, x
2
, x
3
e Ciclo C
Parte 2: O objetivo da segunda parte da prova ´e encontrar um v´ertice x ou um K
3
x, y, z e trˆes caminhos P
1
, P
2
e P
3
partindo de x (ou do K
3
) que juntos ao buraco C
definido acima, formam uma estrutura ponto-buraco ou triˆangulo-buraco proibida em H
(Lema 6.2.8). Considere, primeiramente, os seguintes v´ertices de H:
1. Seja x
1
o v´ertice de L
5
[4, 5] mais pr´oximo do v´ertice prim´ario v
5,4
que tem pelo menos
um vizinho em C;
2. Seja x
2
o v´ertice de C
8
[2, 3] mais pr´oximo do v´ertice prim´ario v
2,8
que tem pelo menos
um vizinho em C;
3. Seja x
3
o v´ertice de C
8
[7, 8] mais pr´oximo do v´ertice prim´ario v
8,8
que tem pelo menos
um vizinho em C.
Observe os v´ertices x
1
, x
2
, x
3
tamb´em representados na Figura 6.6.
Pela Observa¸c˜ao 6.2.6, temos que N
C
(x
1
) ⊆ C
6
[4, 6], N
C
(x
2
) ⊆ L
3
[7, 9] e N
C
(x
3
) ⊆
L
7
[7, 9]. Logo, para 1 ≤ i < j ≤ 3, a vizinhan¸ca de x
i
e x
j
em H ´e separada por pelo
menos um v´ertice. Dessa forma, agora temos um buraco C e trˆes v´ertices x
1
, x
2
, x
3
em H
de tal forma que se x
i
u
i
e x
j
u
j
s˜ao arestas de H, onde i = j e u
i
, u
j
∈ C, ent˜ao u
i
n˜ao ´e
adjacente a u
j
em C. Isto satisfaz mais uma restri¸c˜ao de uma estrutura ponto-buraco ou
triˆangulo-buraco proibida.
36
6. Largura em ´arvore de grafos planares livres de buracos pares
Agora, s´o nos resta encontrar um v´ertice x ou um K
3
x, y, z e trˆes caminhos P
i
,
1 ≤ i ≤ 3, em H, de tal forma que P
i
´e um caminho induzido entre o v´ertice x (ou o
caminho K
3
) e x
i
, al´em disso, para 1 ≤ i < j ≤ 3, P
i
e P
j
s˜ao disjuntos internamente em
v´ertices e sem cordas entre si.
Seja P
1
= L
5
[v
5,3
, x
1
] o caminho entre v
5,3
e x
1
em H. Pelas Observa¸c˜oes 6.2.6 e 6.2.7,
temos que P
1
´e um caminho induzido. Considere, agora, o caminho P
2
= C
2
[1, 4]∪L
1
[2, 8]∪
C
8
[v
1,8
, x
2
] unindo os v´ertices v
4,2
e x
2
em H. Observe que P
2
n˜ao ´e necessariamente um
caminho induzido, por´em, pelo Lema 6.2.5, P
2
cont´em um caminho induzido entre v
4,2
e x
1
,
que chamaremos de P
2
. Por ´ultimo, considere o caminho P
3
= C
2
[6, 9]∪L
9
[2, 8]∪C
8
[x
3
, v
9,8
]
unindo os v´ertices v
6,2
e x
3
em H. Seja P
3
o caminho induzido entre v
6,2
e x
3
contido em
P
3
. Observe que, pela Observa¸c˜ao 6.2.6, n˜ao existem cordas entre os caminhos P
i
e P
j
,
1 ≤ i < j ≤ 2.
Para finalizarmos a prova, basta provarmos que existe um v´ertice x (ou um K
3
x, y, z)
e trˆes caminhos P

1
, P

2
e P

3
disjuntos internamente em v´ertices (no caso de ser um K
3
,
disjuntos em v´ertices) e sem cordas entre si de tal forma que P

1
, P

2
e P

3
s˜ao caminhos
unindo x (ou o K
3
) aos v´ertices v
5,3
, v
4,2
e v
6,2
, respectivamente. Al´em disso, x (ou K
3
) e
os caminhos P

1
, P

2
, P

3
est˜ao contidos em C
2
[4, 6] ∪ L
5
[2, 3].
Para provarmos o fato acima, provamos o seguinte fato mais geral: se H ´e um modelo
de G
k×l
, onde k ≥ 5 e l ≥ 4 e H
´e um modelo de G
3×2
contido em H que n˜ao possui
v´ertices das linhas principais L
1
e L
k
nem das colunas principais C
1
e C
l
de H, e al´em
disso, ´e formado por v´ertices de colunas e linhas principais consecutivas de H, ent˜ao H
cont´em um v´ertice v ou um K
3
denotado por ∆ = x, y, z, e trˆes caminhos induzidos e
sem cordas entre si, unindo v (ou cada um dos v´ertices de ∆), aos v´ertices v
1,1
, v
3,1
e v
2,2
de H
. No que segue, os v´ertices, linhas e colunas rotulados se referem ao modelo H
.
Na demonstra¸c˜ao, os seguintes quatro casos ser˜ao analisados:
1. N˜ao existem arestas entre os caminhos L
2
(1, 2] e C
1
[1, 2), nem entre os caminhos
L
2
(1, 2] e C
1
(2, 3] em H
;
2. Existem arestas somente entre os caminhos L
2
(1, 2] e C
1
[1, 2) em H
;
3. Existem arestas somente entre os caminhos L
2
(1, 2] e C
1
(2, 3] em H
;
4. Existem arestas entre os caminhos L
2
(1, 2] e C
1
[1, 2) e entre os caminhos L
2
(1, 2] e
C
1
(2, 3] em H
.
37
6. Largura em ´arvore de grafos planares livres de buracos pares
Caso 1: N˜ao existem arestas entre L
2
(1, 2] e C
1
[1, 2), nem entre L
2
(1, 2] e C
1
(2, 3] (caso
representado pela Figura 6.7): nesse caso, a estrutura ser´a formada pelo v´ertice v
2,1
e pelos
caminhos P
1
= L
2
[1, 2], P
2
= C
1
[1, 2] e P
3
= C
1
[2, 3].
v
1,1
v
3,1
v
2,2
P
1
P
2
P
3
v
1,1
Figura 6.7. Caso 1
Caso 2: Existem arestas somente entre L
2
(1, 2] e C
1
[1, 2) (caso representado pela Figura
6.8): sejam u
1
, · · · , u
q
os v´ertices de C
1
[1, 2] numerados a partir de v
2,1
at´e v
1,1
; e sejam
v
1
, · · · , v
r
os v´ertices de L
2
[1, 2] numerados a partir de v
2,1
at´e v
2,2
. Seja (u
i
, v
j
) a aresta
entre L
2
(1, 2] e C
1
[1, 2) tal que i e j s˜ao m´aximos. Certamente, i > 1 e j > 1. Considere
os seguintes subcasos:
Subcaso 2.1 (u
i
, v
l
) ∈ E(H), para qualquer 1 ≤ l < j (subcaso representado pela Figura
6.8(a)): nesse subcaso, tomamos o v´ertice v
j
e os caminhos P
1
= v
j
, · · · , v
r
, P
2
=
v
j
, u
i
, · · · , u
q
e P
3
= v
j
, v
j−1
, · · · v
1
∪ C
1
(2, 3] unindo v
j
e os v´ertices prim´arios
v
2,2
, v
1,1
, v
3,1
, respectivamente. Observe que n˜ao existem arestas entre P
1
e P
3
, pela
Observa¸c˜ao 6.2.7 e devido ao fato de n˜ao existirem arestas entre L
2
(1, 2] e C
1
(2, 3].
Al´em disso, n˜ao existem arestas entre P
1
e P
2
devido `a escolha da aresta (u
i
, v
j
). Por
´ultimo, n˜ao existem arestas entre P
2
e P
3
, pela Observa¸c˜ao 6.2.6, pelo Corol´ario 4.2.2
e devido ao fato de que u
i
n˜ao possui vizinhos em v
1
, · · · , v
j−1
.
Subcaso 2.2 Existe v
l
∈ N(u
i
), onde 1 ≤ l < j: nesse subcaso, considere v
k
, onde k ´e
m´ınimo e (u
i
, v
k
) ∈ H. Se k = j −1 (subcaso representado pela Figura 6.8(b)), temos
que u
i
, v
k
, v
j
induzem um K
3
e, nesse caso, tomamos u
i
, v
k
, v
j
e os caminhos
P
1
= v
j
, · · · , v
r
, P
2
= u
i
, · · · , u
q
e P
3
= v
k
, · · · , v
1
∪ C
1
[2, 3] formando a
38
6. Largura em ´arvore de grafos planares livres de buracos pares
estrutura desejada. Observe que n˜ao existem arestas entre P
1
e P
2
devido `a escolha de
u
i
e v
j
, n˜ao existem arestas entre P
2
e P
3
pela Observa¸c˜ao 6.2.6, pelo Corol´ario 4.2.2
e pela escolha de v
k
, al´em disso, n˜ao existem arestas entre P
1
e P
3
pela Observa¸c˜ao
6.2.7 e pelo fato de n˜ao existirem arestas entre L
2
(1, 2] e C
1
(2, 3]. Se k < j − 1
(subcaso representado pela Figura 6.8(c)), consideramos o v´ertice u
i
e os caminhos
e P
1
= u
i
, v
j
, · · · , v
r
, P
2
= u
i
, · · · , u
q
e P
3
= u
i
, v
k
, · · · , v
1
∪ C
1
[2, 3] formando
a estrutura desejada. Pelos mesmos argumentos do subcaso em que k = j − 1, os
caminhos P
1
, P
2
, P
3
s˜ao disjuntos internamente em v´ertices e sem cordas entre si.
v =u
1,1
q
v =v =u
2,1
1 1
v
3,1
v =v
2,2
r
v
j
u
i
P
1
P
2
P
3
(a) Subcaso 2.1
v =u
1,1
q
v
3,1
v =v
2,2
r
u
i
P1
P
2
P3
v
k
v
j
v =v =u
2,1
1 1
(b) Subcaso 2.2 com k = j −1
v =u
1,1
q
v
3,1
v =v
2,2
r
v
j
u
i
P1
P2
P3
v
k
v =v =u
2,1
1 1
(c) Subcaso 2.2 com k < j −1
Figura 6.8. Caso 2
Caso 3: Existem arestas somente entre L
2
(1, 2] e C
1
(2, 3]: esse caso ´e an´alogo ao anterior.
Caso 4: Existem arestas entre L
2
(1, 2] e C
1
[1, 2) e entre L
2
(1, 2] e C
1
(2, 3] (caso repre-
sentado pela Figura 6.9): nesse caso, considere a numera¸c˜ao dos v´ertices dos caminhos
C
1
[1, 2] e L
2
[1, 2] como no caso 2. Al´em disso, considere w
1
, · · · , w
s
uma numera¸c˜ao dos
v´ertices de C
1
[2, 3] a partir do v´ertice prim´ario v
2,1
. Sejam (u
i
, v
j
), (w
f
, v
g
) ∈ E(H) tais
que i, j, f, g s˜ao m´aximos. Analisamos os seguintes subcasos:
Subcaso 4.1 g = j (subcaso representado pela Figura 6.9(a)): nesse subcaso, consider-
amos o v´ertice v
g
e os caminhos P
1
= v
g
, u
i
, · · · , u
q
, P
2
= v
g
, · · · , v
r
e P
3
=
v
g
, w
f
, · · · , w
s
unindo v
g
e os v´ertices prim´arios v
1,1
, v
2,2
e v
3,1
, respectivamente.
Observe que n˜ao existem arestas entre P
1
e P
2
, pela escolha de i e j, nem entre P
2
e
P
3
pela escolha de f e g e nem entre P
1
e P
3
pela Observa¸c˜ao 6.2.6.
39
6. Largura em ´arvore de grafos planares livres de buracos pares
Subcaso 4.2 g > j: Suponhamos, primeiramente, que n˜ao existem arestas unindo w
f
e
v
j
, · · · , v
g−1
(subcaso representado pela Figura 6.9(b)). Consideramos, nesse caso,
o v´ertice v
g
e os caminhos P
1
= v
g
, · · · , v
r
, P
2
= v
g
, v
g−1
, · · · , v
j
, u
i
, · · · , u
q
e
P
3
= v
g
, w
f
, · · · , w
s
. Observe que n˜ao existem arestas entre P
1
e P
3
devido `a
escolha de v
g
e w
f
, n˜ao existem arestas entre P
1
e P
2
devido `a escolha de u
i
e v
j
e
pela Observa¸c˜ao 6.2.7 e n˜ao existem arestas entre P
2
e P
3
, pelo Corol´ario 4.2.2, pela
Observa¸c˜ao 6.2.6 e pelo fato de n˜ao existirem arestas unindo w
f
e v
j
, · · · , v
g−1
.
Logo, temos uma estrutura como desejada.
Suponhamos, agora, que existe pelo menos uma aresta unindo w
f
e v
j
, · · · , v
g−1
(subcaso representado pela Figura 6.9(c)). Consideramos, nesse caso, o v´ertice w
f
e os caminhos P
1
= w
f
, v
g
, · · · , v
r
, P
2
= w
f
, w
f−1
, · · · , w
1
= u
1
, · · · , u
q
e P
3
=
w
f
, · · · , w
s
. Observe que n˜ao existem arestas entre P
1
e P
3
devido `a escolha de
w
f
e v
g
e n˜ao existem arestas entre P
2
e P
3
, pelas Observa¸c˜oes 6.2.6 e 6.2.7. Al´em
disso, observe que devido `a aresta (u
i
, v
j
) e ao fato de existir uma aresta unindo w
f
e
v
j
, · · · , v
g−1
, o Corol´ario 4.2.2 implica que n˜ao existem arestas unindo os caminhos
w
f−1
, · · · , w
1
= u
1
, · · · , u
i−1
e v
g
, · · · , v
r
. Devido `a escolha de u
i
e v
j
, n˜ao existem
arestas unindo u
i
, · · · , u
q
e v
g
, · · · , v
r
e devido `a escolha de w
f
e v
g
, n˜ao existem
arestas unindo w
f
e v
g+1
, · · · , v
r
. Portanto, tamb´em n˜ao existem arestas unindo os
caminhos P
1
e P
2
. Logo, nesse caso, tamb´em temos uma estrutura como a desejada.
Subcaso 4.3 g < j: esse subcaso ´e an´alogo ao subcaso anterior.
v =v
2,2
r
v
j
u
i
v
g
w
f
P1
P2
P3
v =w
3,1
s
v =u
1,1
q
v =u =w
1 1 1
(a) Subcaso 4.1
v =v
2,2
r
v
j
u
i
v
g
w
f
P1
P2
P3
v =w
3,1
s
v =u
1,1
q
v =u =w
1 1 1
(b) Subcaso 4.2 sem arestas
entre w
f
e v
j
, · · · , v
g −1
v =u
1,1
q
v =v
2,2
r
v
j
u
i
v
g
w
f
P1
P2
P3
v =w
3,1
s
v =u =w
1 1 1
(c) Subcaso 4.2 com arestas
entre w
f
e v
j
, · · · , v
g −1
Figura 6.9. Caso 4
40
6. Largura em ´arvore de grafos planares livres de buracos pares
Considere H
= L
4
[2, 3] ∪ L
6
[2, 3] ∪ C
2
[4, 6] ∪ C
3
[4, 6] um modelo de G
3,2
contido em H
(modelo de 10 × 10). Conclu´ımos que existe um v´ertice x ou um K
3
x, y, z contido em
H
e trˆes caminhos P

1
, P

2
e P

3
unindo x ou o K
3
, respectivamente, aos v´ertices v
5,3
, v
4,2
e v
6,2
. Considere P
1
= P
1
∪ P

1
, P
2
= P
2
∪ P

2
e P
3
= P
3
∪ P

3
(P
1
, P
2
, P
3
definidos em H
anteriormente). Logo, temos que P
1
∪ P
2
∪ P
3
∪ C induz uma estrutura proibida em H.
✷
41
7
Teorema da Decomposi¸c˜ao para os grafos
planares
O objetivo deste cap´ıtulo ´e apresentarmos uma vers˜ao do Teorema da Decomposi¸c˜ao (Teo-
rema 5.2.7) para os grafos de Γ. Mais precisamente, dado G ∈ Γ, analisamos a estrutura de
um corte minimal contido em um corte k-estrela (k = 1, 2, 3) de G (Se¸c˜ao 7.4) e a estrutura
de um 2-join em G (Se¸c˜ao 7.3). Al´em disso, caracterizamos G no caso em que G ´e b´asico
(Se¸c˜ao 7.2) e no caso em que G ´e livre de caps (Se¸c˜ao 7.1)·
7.1. Grafos planares livres de buracos pares e livres de caps
Nesta se¸c˜ao, mostramos como ´e a estrutura dos grafos de Γ livres de caps que n˜ao possuem
cortes k-estrela (k = 1, 2, 3) e 2-join. Como conseq¨uˆencia desse resultado, obtemos que a
largura em ´arvore de tais grafos ´e no m´aximo 3 se eles tamb´em n˜ao cont´em cortes clique.
Em [10], ´e provado que se um grafo G livre de buracos pares possui um leque, um Mickey,
uma roda curta ou uma roda pr´opria (Defini¸c˜oes 5.2.1, 5.2.2, 5.2.3), ent˜ao G possui um
corte k-estrela (k = 1, 2, 3), logo, no Lema que segue, assumimos que G n˜ao possui roda
pr´opria, Mickey ou leque.
Lema 7.1.1. Se G ´e um grafo planar livre de buracos pares, de cortes estrela, dupla-
estrela, tripla-estrela, 2-join, de cortes clique, de cap e de ro da pr´opria, ent˜ao G ´e um
buraco ´ımpar ou G ´e cordal.
Prova: Suponha que G n˜ao ´e cordal. Logo, existe pelo menos um buraco em G (obviamente,
todo buraco de G ´e ´ımpar). Seja C um deles. Suponha, por contradi¸c˜ao, que G \ C = ∅.
7. Teorema da Decomposi¸c˜ao para os grafos planares
Seja, ent˜ao, H, uma componente conexa de G\C. As proposi¸c˜oes que seguem ser˜ao usadas
na prova do lema.
Proposi¸c˜ao 7.1.2. Para todo v ∈ H, |N
C
(v)| ≤ 1.
Prova: Obviamente, |N
C
(v)| ≤ 3, pois G n˜ao possui rodas pr´oprias. Suponha, por absurdo,
que existe v ∈ H tal que |N
C
(v)| = 3. Como G n˜ao possui rodas pr´oprias, temos que os
vizinhos de v em C induzem um caminho. Denotemos N
C
(v) por N
v
= {v
1
, v
2
, v
3
}, onde
v
1
, v
2
, v
3
´e um caminho induzido. Note que deve existir algum outro caminho ligando
v ao ciclo C que n˜ao passa por N
v
, pois, caso contr´ario, N
v
seria um corte estrela. Seja
P = v = w
0
, w
1
, · · · , w
q
um caminho unindo v e C \ N
v
que seja m´ınimo (obviamente,
w
q
= v
i
, para i = 1, 2, 3). Note que q ≥ 2 e que n˜ao existem cordas entre os v´ertices
internos do caminho P e C, com exce¸c˜ao de poss´ıveis cordas entre P e N
v
e entre w
q−1
e
os dois vizinhos de w
q
em C. Abaixo, analisamos os poss´ıveis casos.
1. Existem arestas entre P e N
v
: Por planaridade, tal aresta ´e para v
1
ou v
3
. Logo,
se (w
i
, v
j
) ´e uma corda, w
i
∈ P , ent˜ao j = 1 ou j = 3 (w
i
n˜ao pode estar ligado a
ambos, pois casos contr´ario, {v
1
, v
2
, v
3
, w
i
} induziria um C
4
, um absurdo, pois G ´e
livre de buracos pares). Tomemos, ent˜ao, uma aresta entre P e N
v
, (w
i
, v
j
), tal que
i ´e m´ınimo. Suponhamos, sem perda de generalidade, que j = 3. Temos que i = 1,
pois, caso contr´ario, ter´ıamos que v
2
, v = w
0
, w
1
, · · · , w
i
, v
3
, v
2
´e um cap (corda
w
0
v
3
). Al´em disso, note que N
C
(w
1
) = {v
3
} ou N
C
(w
1
) = {v
3
, x, y}. No ´ultimo
caso, temos que ((C \ {v
2
, x}) ∪ {w
0
, w
1
}) ´e um cap (corda w
0
w
1
). No primeiro caso,
temos que (C \ {v
2
}) ∪ {w
0
, w
1
} tamb´em ´e um cap (corda w
0
v
3
), absurdo.
2. N˜ao existem arestas entre P e N
v
. Agora, temos os dois seguintes subcasos:
(i) N
C
(w
q−1
) = {w
q
}: nesse caso, sejam P
1
o (v
1
, w
q
)-caminho passando por C \
{v
2
, v
3
} e P
3
o (v
3
, w
q
)-caminho passando por C \{v
1
, v
2
}. Note que P
1
e P
3
tˆem
tamanho pelo menos um, j´a que w
q
= v
1
, v
2
, v
3
, e s˜ao disjuntos. Logo, P
1
∪{w
0
},
P
3
∪ {w
0
} e P formam uma estrutura ponto-ponto unindo os v´ertices w
0
e w
q
,
absurdo.
(ii) G[N
C
(w
q−1
)] = u
1
, u
2
, u
3
: note que C define dois caminhos disjuntos entre
as extremidades dos caminhos v
1
, v
2
, v
3
e u
1
, u
2
, u
3
, P
1
e P
2
. Suponha, sem
perda de generalidade, que P
1
une os v´ertices v
1
e u
1
e P
2
une os v´ertices v
3
e
43
7. Teorema da Decomposi¸c˜ao para os grafos planares
u
3
. Como provamos no caso anterior que n˜ao pode existir cordas unindo P e N
v
,
temos que v
1
= u
1
e v
3
= u
3
. Sendo v
1
= u
1
, temos que v
2
, v
1
, P
1
, u
1
, w
q−1
, P, w
0
, v
2
´e um cap (corda v
1
w
0
); um absurdo.
Suponha finalmente que existe v tal que |N
C
(v) = 2| e N
C
(v) = {u, w}. Se (u, w) ∈
E(G), temos um cap e, caso contr´ario, temos uma estrutura ponto-ponto unindo os v´ertices
u e w, uma contradi¸c˜ao em ambos os casos. Isso encerra a prova da proposi¸c˜ao.
Proposi¸c˜ao 7.1.3. N
C
(H) induz um grafo conexo.
Prova: Queremos provar que N
C
(H) induz um caminho em C ou ´e igual a C. Suponha
o contr´ario. Considere uma representa¸c˜ao planar de G e seja v ∈ C \ N
C
(H). Como G
´e conexo e n˜ao possui cortes clique, existem pelo menos dois v´ertices em N
C
(H). Sejam
v
L
, v
R
∈ N
C
(H) mais pr´oximos de v `a esquerda e `a direita, respectivamente. Seja P =
v
0
= v
L
, v
1
, · · · , v
k
= v
R
um caminho m´ınimo entre v
L
e v
R
cujos v´ertices internos est˜ao
contidos em H (certamente, tal caminho existe, pois v
L
, v
R
∈ N
C
(H) e H ´e conexo).
Considere v
L
Cv
r
o caminho entre v
L
e v
R
em C que passa por v e v
L
Cv
r
o caminho
entre v
L
e v
R
em C que n˜ao passa por v. Assuma que v
L
= w
0
, w
1
, · · · , w
q
= v
R
´e uma
ordena¸c˜ao dos v´ertices de v
L
Cv
r
, seguindo o desenho planar.
Observe que |P | ≥ 3. Observe, tamb´em, que n˜ao existem arestas entre P \ {v
L
, v
R
}
e v
L
Cv
R
devido `as escolhas de v
L
e v
R
. Logo, existe pelo menos uma aresta entre
P \{v
L
, v
1
, v
R
, v
k−1
} e C \{v
L
, v
R
} (pela proposi¸c˜ao 7.1.2, v
1
e v
k−1
n˜ao tˆem outros vizinhos
em C al´em de v
L
e v
R
, respectivamente), caso contr´ario os caminhos v
L
Cv
R
, v
L
Cv
R
e
P definiriam uma estrutura ponto-ponto unindo v
L
e v
R
, absurdo. Seja (v
i
, w
j
) essa aresta
escolhida de forma que j seja m´ınimo e que em seguida, i seja m´ınimo.
Observe que n˜ao existem arestas entre os caminhos v
0
= v
L
, · · · , v
i
e v
L
Cv
R
al´em
da aresta (v
i
, w
j
), pela planaridade de G, pelas escolhas de v
i
e w
j
e pelo fato de |N
C
(v)| ≤
1, para todo v ∈ H. Se w
j
n˜ao ´e adjacente a v
L
, ent˜ao os caminhos definidos por C,
juntamente com o caminho v
L
= v
0
, · · · , v
i
, w
j
entre v
L
e w
j
definem uma estrutura
ponto-ponto, um absurdo. Logo, w
j
´e o vizinho esquerdo de v
L
, ou seja, j = 1. Considere,
agora, P
= w
1
= v
0
, · · · , v
k
, v
R
o caminho m´ınimo entre w
1
e v
R
cujos v´ertices internos
estejam contidos em P (tal caminho existe, devido `a existˆencia da aresta (v
i
, w
1
)). Defina
w
j
Cv
R
o caminho entre w
1
e v
R
em C contendo v e w
j
Cv
R
o caminho entre w
j
e
v
R
em C que n˜ao cont´em v. Observe que n˜ao existem arestas entre P
\ {w
1
, v
i
, v
k
, v
R
}
44
7. Teorema da Decomposi¸c˜ao para os grafos planares
e w
1
Cv
r
, devido `a minimalidade de P
e `as escolhas de v
L
e v
R
anteriormente. Dessa
forma, p odemos aplicar um racioc´ınio an´alogo ao anterior (aplicado para os v´ertices v
L
,
v
R
e o caminho P ) aos v´ertices w
1
, v
R
e caminho P
= v
0
= w
1
, v
i
, · · · , v
k
= v
R
para
encontrar uma estrutura ponto-ponto entre w
1
e v
L
ou uma aresta entre P
e w
2
. Como
C ´e finito e assumimos que G[N
C
(H)] ser desconexo, terminaremos por encontrar um w
m
,
com m < q − 1, e uma estrutura ponto-ponto formada por v
R
e w
m
, um absurdo.
Para completar a prova do Lema, iremos mostrar que G = C. Pela proposi¸c˜ao 7.1.3,
N
C
(H) induz um caminho ou um ciclo. Como G n˜ao possui cortes clique, corte estrela e
corte dupla-estrela, temos que |N
C
(H)| ≥ 5. Sejam v
1
, v
2
, . . . , v
l
∈ N
C
(H) numerados no
sentido hor´ario (logo l ≥ 5 e talvez v
l
= v
1
).
Seja P = v
1
= w
0
, w
1
, · · · , v
l
= w
k
um caminho m´ınimo entre v
1
e v
l
em H que
maximiza o n´umero de arestas entre P e C (tal caminho existe, pois H ´e conexo). Vamos
provar primeiro que cada v´ertice de {v
2
, · · · , v
l−1}
vˆe pelo menos um v´ertice de P . Observe
primeiro que pela planaridade de G, n˜ao existem ´ındices i
1
, i
2
, j
1
, j
2
, com i
1
< i
2
e j
1
< j
2
tais que ambos (w
i
1
, v
j
2
) e (w
i
2
, v
j
1
) sejam arestas.
Agora, suponha que existe i, 1 < i < l, tal que v
i
n˜ao ´e adjacente `a nenhum v´ertice em
P . Sejam v
i
a
e v
i
p
os v´ertices de C imediatamente anterior e posterior a v
i
tal que existem
arestas de P para v
i
a
e v
i
p
(como C tem pelo menos 5 v´ertices, v
i
a
e v
i
p
s˜ao distintos e
n˜ao adjacentes). Sejam w
i
a
e w
i
p
os vizinhos de v
i
a
e v
i
p
, respectivamente, em P tais que
P
= v
i
a
, w
i
a
, w
i
a
+1
, . . . , w
i
p
, v
i
p
´e um caminho induzido entre v
i
a
e v
i
p
com os v´ertices
internos contidos em P . Pelas escolhas de P , v
i
a
, v
i
p
e P
, temos uma estrutura ponto-ponto
entre v
i
a
e v
i
p
, um absurdo. Logo, cada v
i
, 1 < i < l, vˆe um ou mais v´ertices de P . Agora,
considerando v
i
, com 1 < i < l, v
i−1
, v
i+1
e fazendo P
= v
i
i−1
, w
i
a
, w
i
a
+1
, . . . , w
i
p
, v
i+1
ser o caminho induzido entre v
i−1
e v
i+1
com os v´ertices internos contidos em P , temos que
(P
∪ C) \ { v
i
} ´e um buraco C
e v
i
vˆe pelo menos trˆes v´ertices de C
, uma contradi¸c˜ao,
pois G n˜ao possui rodas pr´oprias. Ent˜ao, conclu´ımos que se G possui um buraco ´ımpar C,
G \ C n˜ao pode possuir uma componente H, logo, G ´e um buraco ´ımpar ou G ´e cordal. ✷
A partir de agora, denominamos grafo livre de cap especial um grafo livre de cap
que induz um buraco ´ımpar ou ´e cordal. O Lema 7.1.4 limita a largura em ´arvore da classe
dos grafos livre de cap especial.
Lema 7.1.4. Se G ´e um grafo livre de cap especial sem cortes clique, ent˜ao LA(G) ≤ 3.
45
7. Teorema da Decomposi¸c˜ao para os grafos planares
Prova: Se G ´e um buraco ´ımpar, temos que LA(G) = 2 ([6]). Observe que se G tiver um
K
4
, G ´e um pr´oprio K
4
, pois G n˜ao possui cortes clique. Dessa forma, se G ´e um grafo
cordal, como ´e planar, pelo Teorema de Kuratowski (Teorema 4.1.2), temos que o tamanho
da clique m´axima de G ´e no m´aximo 3, logo, LA(G) ≤ 2, pois ´e conhecido que a largura
em ´arvore de todo grafo cordal ´e igual ao tamanho de sua clique m´axima menos 1 ([6]). ✷
7.2. Grafos planares livres de buracos pares b´asicos
Nesta se¸c˜ao, analisamos as estruturas dos grafos de Γ b´asicos trivial e n˜ao-trivial. Seja G
um grafo de Γ que ´e grafo b´asico n˜ao-trivial (Defini¸c˜ao 5.2.5). Considere x e y os v´ertices
especiais de G.
´
E f´acil observarmos que G \ {x, y} ´e um grafo cordal. Como G ´e planar
e n˜ao possui cortes clique, temos que o tamanho da maior clique de G ´e no m´aximo 3. O
Lema 7.2.1 limita a largura em ´arvore dos grafos de Γ que s˜ao b´asicos n˜ao-triviais.
Lema 7.2.1. Seja G um grafo de Γ sem cortes clique e b´asico n˜ao-trivial. Ent˜ao, LA(G) ≤
4.
Prova: Considere x e y os v´ertices especiais de G. Como G \ {x, y} ´e um grafo cordal,
temos que G \ {x, y} admite uma decomposi¸c˜ao em ´arvore ´otima D = (X , T), onde cada
X ∈ X cont´em uma clique maximal de G \ {x, y} ([6]). Como o tamanho da maior clique
de G\{x, y} ´e no m´aximo 3, conclu´ımos que LA(G\{x, y}) ≤ 2. Podemos obter uma DEA
de G a partir da DEA D de G \ {x, y} apenas incluindo os v´ertices x, y em todo X ∈ X .
Logo, conclu´ımos que LA(G) ≤ 4. ✷
O Lema 7.2.2 limita a largura em ´arvore dos grafos de Γ que s˜ao b´asicos triviais, ou
seja, de toda estrutura ponto-triˆangulo.
Lema 7.2.2. Seja G uma estrutura ponto-triˆangulo formada por um v´ertice y, um triˆangulo
x
1
, z
1
, w
1
e trˆes caminhos P
x
= x
1
, · · · , x
l
x
+1
, P
z
= z
1
, · · · , z
l
z
+1
e P
w
= w
1
, · · · , w
l
w
+1
(l
x
, l
z
e l
w
representam o comprimento dos caminhos P
x
, P
z
, P
w
) unindo o v´ertice y aos
v´ertices x, z, w respectivamente. Ent˜ao, LA(G) ≤ 3.
Prova: Considere a seguinte DEA D = (X , T) de G de largura em ´arvore igual a 4:
acrescente uma parte X
p
= {x
1
, z
1
, w
1
, y} em X e um n´o t
p
representando X
p
em T . Para
todo inteiro i, 1 ≤ i ≤ l
x
, acrescente uma parte X
x
i
= {x
i
, x
i+1
, y} em X e um v´ertice
t
x
i
em T representando X
x
i
. Para todo inteiro j, 1 ≤ j ≤ l
z
, acrescente uma parte
46
7. Teorema da Decomposi¸c˜ao para os grafos planares
X
z
j
= {z
j
, z
j+1
, y} em X e um v´ertice t
z
j
em T representando X
z
j
. Para todo inteiro
k, 1 ≤ k ≤ l
w
, acrescente uma parte X
w
k
= {w
k
, w
k+1
, y} em X e um v´ertice t
w
k
em T
representando X
w
k
. Fa¸ca o n´o t
p
adjacente aos n´os t
x
1
, t
z
1
e t
w
1
; o n´o t
x
i
adjacente ao
n´o t
x
i+1
, para todo inteiro 1 ≤ i < l
x
; o n´o t
z
j
adjacente ao n´o t
z
j+1
, para todo inteiro
1 ≤ j < l
z
e o n´o t
w
k
adjacente ao n´o t
w
k+1
, para todo inteiro 1 ≤ k < l
w
.
Observe que o procedimento descrito acima constr´oi uma DEA para qualquer estru-
tura ponto-triˆangulo, pois todo v´ertice e toda aresta s˜ao cobertos por uma parte da de-
composi¸c˜ao D retornada, todo v´ertice dos caminhos P
x
, P
z
, P
w
diferente de y aparece em
exatamente duas partes de D e os v´ertices de T representando tais partes s˜ao adjacentes,
al´em disso, o v´ertice y est´a em todas as partes de D.
✷
Os Lemas 7.2.1 e 7.2.2 implicam que se G ´e um grafo de Γ sem cortes clique e b´asico,
ent˜ao LA(G) ≤ 4. Al´em disso, os Lemas 7.1.4, 7.2.1, 7.2.2 e o Teorema da Decomposi¸c˜ao
implicam que dada uma ´arvore de decomposi¸c˜ao de um grafo G de Γ, a largura em ´arvore
de todos os subgrafos de G representados pelas folhas de tal ´arvore ´e no m´aximo 4.
A partir de agora, chamamos de grafo b´asico especial todo grafo que ´e isomorfo a
uma estrutura ponto-triˆangulo ou que ´e um grafo b´asico n˜ao-trivial onde o tamanho da
maior clique ´e no m´aximo 3.
7.3. Grafos planares livres de buracos pares que contˆem um 2-join
Seja G um grafo planar livre de buracos pares que cont´em um 2-join (Defini¸c˜ao 5.2.4).
Seja V
1
|V
2
o 2-join J de G com conjuntos especiais (A
1
, A
2
, B
1
, B
2
), A
i
, B
i
⊂ V
i
. Como
todo v´ertice de A
1
´e adjacente a todo v´ertice de A
2
e todo v´ertice de B
1
´e adjacente a
todo v´ertice de B
2
, conclu´ımos que min(|A
1
|, |A
2
|) ≤ 2 e min(|B
1
|, |B
2
|) ≤ 2, pois caso
contr´ario, G teria um menor K
3,3
como subgrafo, um absurdo, pois G ´e planar (Teorema
4.1.2).
Um 2-join J com conjuntos especiais (A
1
, A
2
, B
1
, B
2
), A
i
, B
i
⊂ V
i
´e um 2-join especial
se min(|A
1
|, |A
2
|) ≤ 2 e min(|B
1
|, |B
2
|) ≤ 2.
47
7. Teorema da Decomposi¸c˜ao para os grafos planares
7.4. Grafos planares livres de buracos pares que cont´em corte k-estrela
(k = 1, 2, 3)
Em [10], a prova do Teorema da Decomposi¸c˜ao ´e dividida em 3 partes, onde a primeira
parte consite em provar que quando um grafo G livre de buracos pares cont´em um subgrafo
induzido isomorfo a um leque, um Mickey ou a uma roda pr´opria (Defini¸c˜oes 5.2.1, 5.2.2,
5.2.3), ent˜ao G tem um corte estrela, dupla-estrela ou tripla-estrela.
Nesta se¸c˜ao, estudamos os grafos de Γ que cont´em um leque, um Mickey ou uma roda
pr´opria, analisando os cortes estrela, dupla-estrela ou tripla-estrela de tais grafos. Os cortes
apresentados em [10] n˜ao s˜ao necessariamente minimais, por outro lado, com o objetivo de
limitar o tamanho dos cortes da decomposi¸c˜ao, estudamos os cortes minimais contidos em
tais cortes k-estrela, k = 1, 2, 3.
Em [10], s˜ao provados os seguintes fatos para todo grafo livre de buracos pares G:
1. Se G possui um leque G = {x
1
, x
2
, x
3
, x
4
, x
5
}, onde P = x
1
, x
2
, x
3
, x
4
´e um caminho
sem cordas e x
5
´e adjacente a todos os v´ertices do caminho P , ent˜ao C = N(x
2
) ∪
N(x
3
) ∪ N(x
5
) \ {x
1
, x
4
} ´e um corte tripla-estrela que separa x
1
de x
4
;
2. Se G possui um Mickey M = (xyz, H
1
, H
2
) onde H
1
cont´em x, y e H
2
cont´em x, z,
ent˜ao C = N(x)∪N(y) ∪ N(z) \ {y
1
, z
2
} ´e um corte tripla-estrela que separa V (H
1
) \
{y, x, x
1
} de V (H
2
) \ {z, x, x
2
};
3. Se G possui uma roda curta B = (H, x), ent˜ao C = N (x) ∪ N(y) ´e um corte dupla-
estrela que separa H
1
de H
2
, sendo que y ´e o v´ertice de H que est´a entre os dois
setores longos, H
1
e H
2
, de B;
4. Se G n˜ao possui um leque, um Mickey ou uma roda curta, mas possui uma roda
pr´opria, ent˜ao G cont´em uma roda pr´opria W = (H, x) com pelo menos trˆes setores
longos, al´em disso, C = N(x) ´e um corte estrela que separa os setores longos de W.
Seja G um grafo de Γ que cont´em um leque, um Mickey, uma roda pr´opria ou uma
roda curta e seja C um corte k-estrela de G. Suponhamos que C separa dois conjuntos de
v´ertices H
1
e H
2
contidos em G. Sejam G
1
e G
2
as componentes de G \ C que cont´em os
conjuntos H
1
e H
2
, respectivamente. Como C separa G
1
de G
2
, todo caminho entre G
1
e
G
2
tem pelo menos um v´ertice de C.
48
7. Teorema da Decomposi¸c˜ao para os grafos planares
Considere os seguintes conjuntos de v´ertices contidos em C:
1. [C]: Centro da k-estrela C;
2. N
∗
= N (G
1
) ∩ N(G
2
) onde N(G
i
) ´e a vizinhan¸ca de G
i
em C;
3. N
∗
1
= {u ∈ N(G
1
) \ (N
∗
∪ [C])|existe um caminho entre u e a componente G
2
que
n˜ao passa por (N(G
1
) ∪ [C])};
4. N
∗
2
= {u ∈ N(G
2
) \ (N
∗
∪ [C])|existe um caminho entre u e a componente G
1
que
n˜ao passa por (N(G
2
) ∪ [C])}.
Pelas defini¸c˜oes dos conjuntos acima, note que que o conjunto de v´ertices [C]∩N
∗
pode
ser diferente de vazio. Observe que todos os caminhos P entre G
1
e G
2
s˜ao de um dos
seguintes tipos:
1. P passa pelo centro [C] da k-estrela;
2. P n˜ao passa pelo centro [C] da k-estrela e tem comprimento exatamente igual a 2;
3. P n˜ao passa pelo centro [C] da k-estrela e tem comprimento maior do que 2.
Observe que G \ ([C] ∪ N
∗
) n˜ao cont´em caminhos do tipo 1 nem caminhos do tipo 2
entre G
1
e G
2
. Podemos observar, tamb´em, que todo caminho do tipo 3 m´ınimo unindo
G
1
e G
2
em G \ ([C] ∪ N
∗
) tem exatamente um v´ertice x de N
∗
1
e exatamente um v´ertice
y de N
∗
2
, logo, se retirarmos ou x ou y de G \ ([C] ∪ N
∗
), tal caminho n˜ao existir´a mais.
Dessa forma, podemos obter um corte C
de G contido em C e que separa G
1
de G
2
da
seguinte forma: primeiramente, adicionamos [C] ∪ N
∗
em C
a fim de que n˜ao exista mais
caminhos dos tipos 1 e 2 entre G
1
e G
2
. Depois, realizamos a seguinte opera¸c˜ao at´e que
n˜ao haja nenhum outro caminho entre G
1
e G
2
em G \ C
: escolhemos o caminho m´ınimo
entre G
1
e G
2
em G \ C
e acrescentamos ou o v´ertice x ou o v´ertice y de G no corte C
(x
e y como definidos anteriormente). Dessa forma, conclu´ımos que tanto C
= [C] ∪ N
∗
∪ N
∗
1
quanto C
= [C]∪N
∗
∪N
∗
2
s˜ao cortes de G que ainda separam G
1
de G
2
, portanto, tamb´em
separam H
1
de H
2
. No que segue, consideremos o corte C
= [C] ∪ N
∗
∪ N
∗
1
. Observe que
tal corte C
tamb´em ´e um corte k-estrela de G e defina G
1
a componente de G \ C
que
cont´em H
1
e G
2
a componente de G \ C
que cont´em H
2
.
49
7. Teorema da Decomposi¸c˜ao para os grafos planares
Lema 7.4.1. Seja C
o corte como definido anteriormente contido no corte k-estrela de
G ∈ Γ. Para todo v ∈ [C], |N
C
(v) ∩ (N
∗
∪ N
∗
1
)| ≤ 2.
Prova: Seja x ∈ [C]. Suponhamos, por absurdo, que |N
C
(x) ∩ (N
∗
∪ N
∗
1
)| > 2. Dessa
forma, sejam x
1
, x
2
, x
3
∈ (N
C
(x) ∩ (N
∗
∪ N
∗
1
)). Temos que G tem um menor K
3,3
com
parti¸c˜oes V
1
= {x, g
1
, g
2
} e V
2
= {x
1
, x
2
, x
3
}, onde g
1
e g
2
s˜ao os v´ertices obtidos pelas
contra¸c˜oes de G
1
e G
2
respectivamente, contradizendo a planaridade de G.
✷
Lema 7.4.2. Se C
´e um corte como definido anteriormente contido no corte k-estrela de
G ∈ Γ, ent˜ao |(N
∗
∪ N
∗
1
) \ [C]| ≤ 2.
Prova: Suponhamos, por absurdo, que |(N
∗
∪N
∗
1
)\[C]| > 2. Dessa forma, sejam x
1
, x
2
, x
3
∈
(N
∗
∪ N
∗
1
) \ [C]. Temos que G tem um menor K
3,3
com parti¸c˜oes V
1
= {g
1
, g
2
, g
3
} e
V
2
= {x
1
, x
2
, x
3
}, onde g
1
, g
2
, g
3
s˜ao os v´ertices obtidos pela contra¸c˜oes de G
1
, G
2
e [C]
respectivamente.
✷
Mostraremos em seguida que os cortes C
, obtidos a partir dos cortes k-estrela C (k =
1, 2, 3) como definidos anteriormente, s˜ao isomorfos a um dos seguintes grafos abaixo:
T1 V (C
) = {x
1
, x
2
, x
3
} e E(C
) = {x
1
x
2
, x
2
x
3
}, ou seja, C
induz um P
3
;
T2 V (C
) = {x
1
, x
2
, x
3
, x
4
} e E(C
) = {x
1
x
2
, x
2
x
3
, x
3
x
4
}, ou seja, C
induz um P
4
;
T3 V (C
) = {x
1
, x
2
, x
3
, x
4
} e E(C
) = {x
1
x
2
, x
1
x
3
, x
1
x
4
};
T4 V (C
) = {x
1
, x
2
, x
3
, x
4
} e E(C
) = {x
1
x
2
, x
1
x
3
, x
2
x
3
, x
3
x
4
};
T5 V (C
) = {x
1
, x
2
, x
3
, x
4
} e E(C
) = {x
1
x
2
, x
1
x
3
, x
2
x
3
, x
1
x
4
, x
2
x
4
};
T6 V (C
) = {x
1
, x
2
, x
3
, x
4
, x
5
} e E(C
) = {x
1
x
2
, x
1
x
3
, x
2
x
3
, x
1
x
4
, x
2
x
5
};
T7 V (C
) = {x
1
, x
2
, x
3
, x
4
, x
5
} e E(C
) = {x
1
x
2
, x
1
x
3
, x
2
x
3
, x
2
x
4
, x
3
x
4
, x
1
x
5
}.
50
7. Teorema da Decomposi¸c˜ao para os grafos planares
x_1 x_1
x_1 x_1
x_1 x_1
x_1
x_2 x_2
x_2
x_2
x_2 x_2 x_2
x_3 x_3
x_3
x_3
x_3
x_3
x_3
x_4
x_4
x_4
x_4
x_4
x_4
x_5
x_5
T1 T2
T3
T4
T5
T6
T7
Figura 7.1. Grafos T 1, T 2, T 3, T 4, T 5, T6, T 7
Suponhamos que G ´e um grafo planar, sem cortes clique, livre de buracos pares e
que cont´em um leque. Seja G = {x
1
, x
2
, x
3
, x
4
, x
5
} o leque contido em G, onde P =
x
1
, x
2
, x
3
, x
4
´e um caminho sem cordas e x
5
´e adjacente a todos os v´ertices do caminho
P .
Seja C = (N(x
2
) ∪ N(x
3
) ∪ N(x
5
)) \ {x
1
, x
4
} o corte tripla-estrela de G separando x
1
de x
4
. Seja G
1
a componente de G \ C que cont´em o v´ertice x
1
e seja G
4
a componente de
G \ C que cont´em o v´ertice x
4
. Seja C
= [C] ∪ N
∗
∪ N
∗
1
o corte de G, definido como no
in´ıcio da se¸c˜ao, que continua separando x
1
de x
4
. Considere G
1
a componente de G \ C
que cont´em x
1
e G
4
a componente de G \ C
que cont´em x
4
.
Lema 7.4.3. Seja G um grafo de Γ que cont´em um leque. Considere o corte tripla-estrela
C de G e C
⊆ C como definido anteriormente. Ent˜ao:
(1) |N
C
(x
2
) \ {x
3
, x
5
}| ≤ 1;
(2) |N
C
(x
3
) \ {x
2
, x
5
}| ≤ 1;
(3) |N
C
(x
5
) \ {x
2
, x
3
}| ≤ 1;
(4) Se y
2
∈ (C
\ [C]) ∩ N(x
2
), ent˜ao n˜ao existe y
3
= y
2
tal que y
3
∈ (C
\ [C]) ∩ N(x
3
).
Prova:
(1) Como x
5
∈ N
∗
, pelo Lema 7.4.1, conclu´ımos que |N
C
(x
2
) \ {x
3
, x
5
}| ≤ 1;
51
7. Teorema da Decomposi¸c˜ao para os grafos planares
(2) Assim como no item anterior, como x
5
∈ N
∗
, pelo Lema 7.4.1, conclu´ımos que
|N
C
(x
3
) \ {x
2
, x
5
}| ≤ 1;
(3) Como podemos contrair a aresta x
2
x
3
a um ´unico v´ertice v que ´e adjacente aos
v´ertices x
1
,x
4
e x
5
, com uma prova an´aloga `a prova do Lema 7.4.1, conclu´ımos que
|N
C
(x
5
) \ {x
2
, x
3
}| ≤ 1;
(4) Suponhamos, por absurdo, que existe y
3
= y
2
tal que y
3
∈ (C
\ [C]) ∩ N(x
3
). Como
x
5
∈ N
∗
, contraindo a aresta x
2
x
3
a um v´ertice adjacente aos v´ertices y
2
, y
3
, x
5
, assim
como no Lema 7.4.1, podemos obter um menor K
3,3
de G, um absurdo, pois G ´e um
grafo planar.
✷
Lema 7.4.4. Se G ´e um grafo de Γ que cont´em um leque e n˜ao cont´em cortes clique, ent˜ao
C’ ´e isomorfo a T4, T5, T6 ou T7.
Prova: Como G n˜ao possui cortes clique, temos que |(N
∗
∪ N
∗
1
) \ [C]| ≥ 1. Primeiramente,
suponhamos que |(N
∗
∪ N
∗
1
) \ [C]| = 1. Nesse caso, seja z ∈ (N
∗
∪ N
∗
1
) \ [C]. Como G
n˜ao possui cortes clique, temos que z ´e adjacente a no m´aximo dois dos v´ertices x
2
, x
3
, x
5
.
Logo, nesse caso, C
´e isomorfo a T4 ou T5.
Agora, suponhamos que|(N
∗
∪N
∗
1
)\[C]| = 2. Nesse caso, sejam z
1
, z
2
∈ (N
∗
∪N
∗
1
)\[C].
Pelo Lema 7.4.3, um dos v´ertices z
1
, z
2
´e adjacente somente ao v´ertice x
5
e o outro ´e
adjacente a pelo menos um dos v´ertices x
2
, x
3
e n˜ao ´e adjacente ao v´ertice x
5
. Sem perda
de generalidade, assumamos que z
1
´e adjacente a x
5
e z
2
´e adjacente a pelo menos um dos
v´ertices x
2
, x
3
. Observe que z
1
n˜ao ´e adjacente a z
2
, pois G ´e livre de buracos pares. Se
z
2
´e adjacente somente a um dos v´ertices x
2
, x
3
, C
´e isomorfo a T6. Se z
2
´e adjacente aos
dois v´ertices x
2
, x
3
, C
´e isomorfo a T7. ✷
Agora, suponhamos que G ´e um grafo planar, sem cortes clique, livre de buracos pares
e que cont´em uma roda curta. Dado uma roda curta (H, x) de G, seja y, x
1
e x
2
os vizinhos
de x em H onde x
1
e x
2
s˜ao adjacentes, enquanto y n˜ao ´e adjacente a x
1
ou x
2
. Seja H
1
o
buraco contendo x
1
, x, y e H
2
o buraco contendo x
2
, x, y. Finalmente, seja y
1
, y
2
os vizinhos
de y em H
1
, H
2
respectivamente, distintos de x.
Chamemos V (H
1
) \ {y
1
, y, x, x
1
} de H
1
e V (H
2
) \ {y
2
, y, x, x
2
} de H
2
. Seja C = N(x) ∪
N(y) o corte dupla-estrela separando H
1
de H
2
. Considere C
= {x, y} ∪ N
∗
∪ N
∗
1
o corte
52
7. Teorema da Decomposi¸c˜ao para os grafos planares
de G contido em C como definido no in´ıcio da se¸c˜ao que ainda separa H
1
de H
2
. Seja G
1
a componente de G \ C
que cont´em H
1
e G
2
a componente de G \ C
que cont´em H
2
.
Lema 7.4.5. Seja G um grafo de Γ que cont´em uma roda curta (H, x). Considere o corte
dupla-estrela C de G e C
⊆ C como definidos anteriormente. Ent˜ao:
(1) |N
C
(x) \ {y}| ≤ 1;
(2) |N
C
(y) \ { x}| ≤ 2;
(3) |(N
∗
∪ N
∗
1
) ∩ {x
1
, x
2
}| ≥ 1.
Prova:
(1) Como y ∈ N(x) e y ∈ (N
∗
∪N
∗
1
), pelo Lema 7.4.1, conclu´ımos que |N
C
(x)\{y}| ≤ 1;
(2) Como x n˜ao pertence necessariamente a ( N
∗
∪ N
∗
1
), pelo Lema 7.4.1, conclu´ımos que
|N
C
(y) \ { x}| ≤ 2;
(3) Observe que pelo menos um dos v´ertices x
1
, x
2
∈ (N
∗
∪ N
∗
1
), pois caso contr´ario, C
n˜ao separaria H
1
de H
2
.
✷
Lema 7.4.6. Se G ´e um grafo de Γ que cont´em uma roda curta e n˜ao cont´em cortes clique,
ent˜ao C’ ´e isomorfo T1, T2, T3, T4 ou T5.
Prova: Como G n˜ao possui cortes clique, temos que |(N
∗
∪ N
∗
1
) \ [C]| ≥ 1. Primeiramente,
suponhamos que |(N
∗
∪N
∗
1
)\[C]| = 1. Nesse caso, seja z ∈ (N
∗
∪N
∗
1
)\[C]. Pelo item 3 do
Lema 7.4.5, z ∈ {x
1
, x
2
}. Como G n˜ao possui cortes clique, temos que z n˜ao ´e adjacente
a y. Logo, nesse caso, C
´e isomorfo a T1.
Agora, suponhamos que|(N
∗
∪N
∗
1
)\[C]| = 2. Nesse caso, sejam z
1
, z
2
∈ (N
∗
∪N
∗
1
)\[C].
Suponhamos, sem perda de generalidade, que z
1
´e adjacente a x. Se cada um dos v´ertices
z
1
, z
2
´e adjacente a apenas um dos v´ertices x, y e ao mesmo v´ertice, temos que C
´e isomorfo
a T3 (se z
1
n˜ao ´e adjacente a z
2
) ou C
´e isomorfo a T4 (se z
1
´e adjacente a z
2
). Se z
1
e z
2
s˜ao adjacentes a apenas um dos v´ertices de {x, y} e tais v´ertices s˜ao distintos, temos que
z
1
n˜ao ´e adjacente a z
2
, pois G ´e livre de buracos pares. Logo nesse caso, C
´e isomorfo a
T2. Se um dos v´ertices de {z
1
, z
2
} ´e adjacente a ambos x e y e o outro v´ertice ´e adjacente
53
7. Teorema da Decomposi¸c˜ao para os grafos planares
somente ao v´ertice y (n˜ao pode ser adjacente somente ao v´ertice x, pelo item 1 do Lema
7.4.5), temos que C
´e isomorfo a T4 (se z
1
n˜ao ´e adjacente a z
2
) ou C
´e isomorfo a T5
(se z
1
´e adjacente a z
2
). Observe que os v´ertices z
1
, z
2
n˜ao podem ser ambos adjacentes
aos v´ertices x, y, pelo item 1 do Lema 7.4.5. ✷
Suponhamos, agora, que G ´e um grafo de Γ sem cortes clique, que n˜ao cont´em leque,
Mickey ou roda curta, e cont´em uma roda pr´opria.
Seja W = (H, x) uma roda pr´opria de G com pelo menos trˆes setores longos. Al´em
disso, seja C = N(x) o corte estrela separando os setores longos de W. Sejam H
1
e H
2
os n´os intermedi´arios de dois setores longos distintos de (H, x). Considere, tamb´em, G
1
a
componente de G \ N(x) que cont´em H
1
, G
2
a componente de G \ N(x) que cont´em H
2
e
C
= {x} ∪ N
∗
∪ N
∗
1
o corte de G como definido anteriormente que continua separando H
1
de H
2
.
Lema 7.4.7. |N
C
(x) ∩ (N
∗
∪ N
∗
1
)| = 2.
Prova: Como G n˜ao possui cortes clique, temos que |N
C
(x) ∩ (N
∗
∪ N
∗
1
)| > 1. Pelo Lema
7.4.1, temos que |N
C
(x)∩(N
∗
∪N
∗
1
)| ≤ 2. Logo, conclu´ımos que |N
C
(x)∩(N
∗
∪N
∗
1
)| = 2.
✷
Lema 7.4.8. Se G ´e um grafo de Γ que cont´em uma roda pr´opria, mas n˜ao cont´em leque,
Mickey, roda curta nem cortes clique, ent˜ao C’ ´e isomorfo a T1.
Prova: Sejam x
1
, x
2
∈ N
C
(x). Como G n˜ao possui cortes clique, x
1
n˜ao ´e adjacente a x
2
.
Logo, C
´e isomorfo a T1. ✷
Por ´ultimo, suponhamos que G ´e um grafo de Γ, sem cortes clique e que G cont´em um
Mickey M(xyz, H
1
, H
2
). Considere x
1
e x
2
os vizinhos de x em H
1
e H
2
, respectivamente,
que s˜ao distintos de y e z. Denote por y
1
o vizinho de y em H
1
e z
2
o vizinho de z em
H
2
, y
1
, z
2
= x. Chamamos V (H
1
) \ {x, y, x
1
} de H
1
e V (H
2
) \ {z, x, x
2
} de H
2
. Seja
C = (N(x) ∪ N(y) N(z)) \ {y
1
, z
2
} o corte tripla-estrela separando H
1
de H
2
. Denote por
C
= N
∗
1
∪ N
∗
∪ [C] o corte de G contido em C que tamb´em separa H
1
de H
2
.
Chamemos V (H
1
) \ {x, y, x
1
} de H
1
e V (H
2
) \ {z, x, x
2
} de H
2
. Seja C = (N(x) ∪
N(y) N(z)) \ {y
1
, z
2
} o corte tripla-estrela separando H
1
de H
2
. Consideremos C
=
N
∗
1
∪ N
∗
∪ [C] o corte de G contido em C que tamb´em separa H
1
de H
2
. No Lema 7.4.9,
considere G
1
a componente de G \ C
que cont´em H
1
e G
2
a componente de G \ C
que
cont´em H
2
.
54
7. Teorema da Decomposi¸c˜ao para os grafos planares
Lema 7.4.9. Se G ´e um grafo planar livre de buracos pares que cont´em um Mickey, ent˜ao:
(1) |N
C
(y) \ { x, z}| ≤ 1;
(2) |N
C
(z) \ {x, y}| ≤ 1;
(3) |N
C
(x) \ {y, z}| ≤ 1;
(4) Se y
∈ (( N
∗
1
∪ N
∗
) ∩ N(y)) \ [C], ent˜ao n˜ao existe z
= y
tal que z
∈ ((N
∗
1
∪ N
∗
) ∩
N(z)) \ [C].
Prova:
(1) Se x
1
∈ G
1
e x
2
∈ G
2
, temos que x ∈ N
∗
. Nesse caso, como x ∈ N(y), pelo
Lema 7.4.1, conclu´ımos que |N
C
(y) \ {x, z}| ≤ 1. Se x
1
∈ C
ou x
2
∈ C
, temos
que |(N
∗
∪ N
∗
1
) \ [C]| ≥ 1, logo, pelo Lema 7.4.2 e pelo fato dos v´ertices x
1
, x
2
n˜ao
pertencerem `a N(y), conclu´ımos que |N
C
(y) \ {x, z}| ≤ 1.
(2) A prova desse item ´e an´aloga `a prova do item 1.
(3) Suponhamos, por absurdo, que |N
C
(x) \ {y, z}| > 1. Dessa forma, sejam x
1
, x
2
∈
N
C
(x) \ {y, z}. Podemos contrair a aresta yz a um ´unico v´ertice x
3
que ´e adjacente
aos v´ertices x, y
1
, z
2
. Podemos contrair G
1
a um ´unico v´ertice g
1
que ´e adjacente aos
v´ertices x
1
, x
2
, x
3
. Podemos tamb´em contrair G
2
e os caminhos unindo os v´ertices
x
1
, x
2
, x
3
e G
2
a um ´unico v´ertice g
2
que ´e adjacente aos v´ertices x
1
, x
2
, x
3
. Portanto,
podemos obter um menor K
3,3
de G com parti¸c˜oes V
1
= {x
1
, x
2
, x
3
} e V
2
= {x, g
1
, g
2
},
um absurdo.
(4) A prova desse item ´e an´aloga `a prova do ´ultimo item do Lema 7.4.3.
✷
Lema 7.4.10. Se G ´e um grafo planar de Γ que cont´em um Mickey e n˜ao cont´em cortes
clique, ent˜ao C’ ´e isomorfo a um dos grafos T4, T5, T6, T7
Prova: A prova desse lema ´e an´aloga `a prova do Lema 7.4.4. ✷
Seja G um grafo de Γ que n˜ao cont´em cortes clique e cont´em um corte k-estrela C
(k = 1, 2, 3). J´a mostramos que G cont´em um corte C
contido em C que ´e isomorfo a
55
7. Teorema da Decomposi¸c˜ao para os grafos planares
um dos grafos T 1 a T 7. Mostraremos, agora, quais s˜ao as poss´ıveis estruturas do corte
minimal C
∗
contido em C
. Por ´ultimo, apresentamos alguns lemas que envolvem grafos
planares e cortes minimais.
Mais especificamente, vamos provar que C
∗
´e isomorfo a um dos grafos abaixo:
G1 V (G1) = {x
1
, x
2
} e E(G1) = ∅
G2 V (G2) = {x
1
, x
2
, x
3
} e E(G2) = {x
1
x
2
, x
2
x
3
}, ou seja, G2 induz um P
3
;
G3 V (G3) = {x
1
, x
2
, x
3
} e E(G3) = ∅;
G4 V (G4) = {x
1
, x
2
, x
3
} e E(G4) = {x
1
x
2
};
G5 V (G5) = {x
1
, x
2
, x
3
, x
4
} e E(G5) = {x
1
x
2
, x
2
x
3
, x
3
x
4
}, ou seja, G5 induz um P
4
;
G6 V (G6) = {x
1
, x
2
, x
3
, x
4
} e E(G6) = {x
1
x
2
, x
2
x
3
};
G7 V (G7) = {x
1
, x
2
, x
3
, x
4
} e E(G7) = {x
1
x
2
, x
1
x
3
, x
2
x
3
}.
x_1 x_2
G1
x_1 x_3x_2
G2
x_1 x_2 x_3
G3
x_1 x_2 x_3
G4
x_1 x_2 x_3 x_4
G5
x_1 x_2 x_3 x_4
G6
x_1
x_3
x_2
x_4
G7
Figura 7.2. Grafos G1, G2, G3, G4, G5, G6, G7
Lema 7.4.11. Seja G um grafo planar livre de buracos pares e C um corte de v´ertices
minimal de G. Temos que |N
C
(v)| ≤ 2, para todo v ∈ C.
Prova: Suponhamos, por contradi¸c˜ao, que existe v ∈ C tal que |N
C
(v)| > 2. Sejam
v
1
, v
2
, v
3
∈ N
C
(v). Como C ´e um corte, existem pelo menos duas componentes conexas,
G
1
e G
2
, em G\C. Al´em disso, como C ´e minimal, cada v´ertice em C possui pelo menos um
vizinho em G
1
e pelo menos um vizinho em G
2
. Podemos reduzir G
1
a um ´unico v´ertice g
1
que ´e adjacente aos v´ertices v
1
, v
2
, v
3
, al´em disso, podemos reduzir G
2
a um ´unico v´ertice
56
7. Teorema da Decomposi¸c˜ao para os grafos planares
g
2
que tamb´em ´e adjacente aos v´ertices v
1
, v
2
, v
3
. Dessa forma, obtemos um K
3×3
com
parti¸c˜oes {g
1
, g
2
, v} e {v
1
, v
2
, v
3
}, um absurdo, pois G ´e um grafo planar. ✷
Como T 1, T 2, T 4 s˜ao isomorfos a subgrafos induzidos de T 6 e T 5 ´e isomorfo a um
subgrafo induzido de T 7, conclu´ımos que o corte minimal C
∗
´e isomorfo a um subgrafo
induzido dos grafos T 3, T 6 ou T 7. No Lema 7.4.12, com a ajuda do Lema 7.4.11, mostramos
quais s˜ao os poss´ıveis subgrafos induzidos H de T 3, T 6 ou T 7 tal que C
∗
pode ser isomorfo
a H.
Lema 7.4.12. C
∗
´e isomorfo a um dos grafos G1, G2, G3, G4, G5, G6, G7.
Prova: Suponhamos, primeiramente, que C
∗
´e isomorfo a um subgrafo induzido de T3.
Nesse caso, pelo Lema 7.4.11, C
∗
possui no m´aximo 3 v´ertices. Como G n˜ao possui cortes
clique, conclu´ımos que C
∗
´e isomorfo a G1, G2 ou G3. Suponhamos, agora, que C
∗
´e
isomorfo a um subgrafo induzido de T6 diferente de G1, G2 ou G3. Pelo Lema 7.4.11,
C
∗
tem no m´aximo 4 v´ertices. Como G n˜ao possui cortes clique, se C
∗
tem 3 v´ertices, C
∗
´e
isomorfo a G4 e se C
∗
tem 4 v´ertices, ´e f´acil observarmos que C
∗
´e isomorfo a G5 ou G6.
Por ´ultimo, suponhamos que C
∗
´e isomorfo a um subgrafo induzido de T7 diferente de
G1, G2, G3, G4, G5 ou G6. Nesse caso, pelo Lema 7.4.11 e pelas afirma¸c˜oes anteriores,
´e f´acil observarmos que C
∗
tem exatamente 4 v´ertices e ´e isomorfo a G7. ✷
Os Lemas 7.4.13 e 7.4.14 limitam o n´umero de componentes de todo corte minimal C
de um grafo planar livre de buracos pares que ´e isomorfo ao grafo T 1 ou possui pelo menos
trˆes v´ertices.
Lema 7.4.13. Seja G um grafo planar e C
∗
um corte minimal de G tal que |C
∗
| ≥ 3,
ent˜ao, G \ C
∗
tem exatamente duas componentes.
Prova: Suponhamos, por absurdo, que G \ C
∗
tem trˆes componentes G
1
, G
2
, G
3
. Seja
c
1
, c
2
, c
3
∈ C
∗
. Como C
∗
´e um corte minimal de G, p odemos reduzir cada componente
G
i
, i = 1, 2, 3, a um ´unico v´ertice g
i
que ´e adjacente aos v´ertices c
1
, c
2
, c
3
. Dessa forma,
obtemos um K
3,3
com parti¸c˜oes V
1
= {c
1
, c
2
, c
3
} e V
2
= {g
1
, g
2
, g
3
}, um absurdo, pois G ´e
um grafo planar. ✷
Lema 7.4.14. Seja G um grafo planar livre de buracos pares e C
∗
um corte minimal de
G isomorfo ao grafo G
1
, ent˜ao, G \ C
∗
tem exatamente duas componentes.
57
7. Teorema da Decomposi¸c˜ao para os grafos planares
Prova: Suponhamos, p or absurdo, que G \ C
∗
tem trˆes componentes G
1
, G
2
, G
3
. Para cada
componente G
i
, i = 1, 2, 3, seja P
i
um caminho induzido unindo os v´ertices x
1
e x
2
de
C
∗
que passa somente pelos v´ertices de G
i
. Tais caminhos existem, pois C
∗
´e um corte
minimal. Al´em disso, o comprimento de cada caminho P
i
´e maior ou igual a 2. Temos que
P
1
∪ P
2
∪ P
3
induz uma estrutura ponto-ponto unindo os v´ertices x
1
e x
2
, um absurdo, pois
G ´e livre de buracos pares. ✷
Os lemas 7.4.13 e 7.4.14 implicam que se C
∗
´e um corte minimal de um grafo G planar
livre de buracos pares isomorfo a um dos grafos G1 a G7, ent˜ao, o n´umero de componentes
de G \ C ´e exatamente igual a 2.
Denominamos corte especial um corte minimal de um grafo G que ´e isomorfo a um
dos grafos G1 a G7.
7.5. Teorema da Decomposi¸c˜ao
Nesta se¸c˜ao, apenas apresentamos uma vers˜ao do Teorema da Decomposi¸c˜ao para os grafos
planares livres de buracos pares. Tal teorema ´e conseq¨uˆencia direta dos resultados apre-
sentados nas quatro se¸c˜oes anteriores.
Seja G um grafo planar livre de buracos pares que n˜ao cont´em um corte clique. Se G
cont´em um leque, um Mickey ou uma roda pr´opria, ent˜ao G possui um corte isomorfo a
um dos grafos G1 a G7 (um corte especial).
Teorema 7.5.1. Seja G um grafo planar livre de buracos pares que n˜ao cont´em um corte
clique. Ent˜ao, ou G ´e um grafo b´asico especial, ou ´e um grafo livre de cap especial, ou ele
tem um 2-join especial ou ele tem um corte especial.
58
8
Algoritmo de decomposi¸c˜ao baseado no
Teorema do V´ertice Bi-simplicial
Neste cap´ıtulo, apresentamos um algoritmo para decompor em ´arvore um grafo livre de
buracos pares qualquer. Tal algoritmo ´e baseado no Teorema do V´ertice Bi-simplicial.
Primeiramente, apresentamos o algoritmo numa vis˜ao intuitiva e, por ´ultimo, o apresenta-
mos na linguagem algor´ıtmica, analisando a corretude e complexidade do mesmo.
8.1. Algoritmo
Seja G um grafo livre de buracos pares e v
n
, v
n−1
, · · · , v
1
uma ordem de elimina¸c˜ao bi-
simplicial de G (o Teorema do V´ertice Bi-simplicial garante a existˆencia de tal ordem).
Considere N
G
i
(v
i
) a vizinhan¸ca do v´ertice v
i
em G
i
= G[v
i
, v
i−1
, · · · , v
1
].
Observe que G
i
n˜ao ´e necessariamente um grafo conexo, logo, n˜ao podemos construir
uma DEA de G obtendo, a cada passo, uma DEA de G
i
. Para superar esse problema
te´orico, introduzimos a no¸c˜ao de Decomposi¸c˜ao em Floresta (DEF) de um grafo H qualquer
(conexo ou desconexo) cuja defini¸c˜ao segue.
Seja H um grafo qualquer e H
1
, · · · , H
r
as componentes de H (observe que r = 1 caso
H seja um grafo conexo). Uma decomposi¸c˜ao em floresta (DEF) de H ´e um par
(X , F) com X = {X
1
, · · · , X
r
} e F = {T
1
, · · · , T
r
} onde (X
i
, T
i
) ´e uma DEA de H
i
, para
todo 1 ≤ i ≤ r.
A partir da ordem de elimina¸c˜ao bi-simplicial v
n
, v
n−1
, · · · , v
1
de um grafo G livre de
buracos pares, uma DEF de G pode ser constru´ıda recursivamente da seguinte forma:
8. Algoritmo de decomposi¸c˜ao baseado no Teorema do V´ertice Bi-simplicial
1. Caso base, ou seja, i = 1: Observe que G
1
´e um grafo trivial, logo, uma DEF ( X , F )
de G
1
´e tal que F consiste de uma ´unica ´arvore T
v
1
= ({v
1
, ∅}) e X ´e formado por
um ´unico conjunto X
v
1
= {X} onde X = v
1
. Observe que (X
v
1
, T
v
1
) ´e trivialmente
uma DEA de G
1
.
2. Passo da indu¸c˜ao, i > 1: Seja (X , F ) uma DEF de G
i−1
. Considere o v´ertice v
i
e
N
G
i
(v
i
). Queremos obter uma DEF de G
i
a partir da DEF de G
i−1
j´a obtida. Temos
os seguintes casos:
(i) N
G
i
(v
i
) = ∅ (Figura 8.1). Nesse caso, G
i
´e um grafo desconexo. Portanto, basta
acrescentar uma DEA para a componente de G
i
que ´e formada pelo v´ertice v
i
.
Mais formalmente, criamos uma ´arvore T
v
i
= ({v
i
}, ∅), uma parte X = {v
i
}
e um conjunto X
v
i
= {X} e fazemos X
= X ∪ X
v
i
, F
= F ∪ T
v
i
, obtendo
claramente uma DEF (X
, F
) de G
i
.
a
b c
d
e f
g
h
j
k
l m
abc
n
bcd
jkl lm
eih
feh
hi gfh
i
(a) G
i
e DEA de G
i−1
(G
i
\ n)
a
b c
d
e f
g
h
j
k
l m
abc
n
bcd
jkl lm
eih
feh
hi gfh
i
ihn
(b) G
i
e DEA de G
i
(v
i
= n)
Figura 8.1. N
G
i−1
(v
i
= n) = ∅
(ii) N
G
i
(v
i
) = Q
1
(Figura 8.2). Seja H a componente de G
i−1
que cont´em Q
1
e seja
(X
H
, T
H
) a DEA de H contida na DEF (X , F ) de G
i−1
. Vamos transformar
60
8. Algoritmo de decomposi¸c˜ao baseado no Teorema do V´ertice Bi-simplicial
(X
H
, T
H
) em uma DEA de H ∪ {v
i
}, criando uma parte X = Q
1
∪ {v
1
}, um
v´ertice t
X
e fazendo V (T
H
) = V (T
H
) ∪ {t
X
}, E(T
H
) = E(T
H
) ∪ {(t
X
, t)}, onde
X
t
∈ X
H
cont´em a clique Q
1
, e por ´ultimo, X
H
= X
H
∪ {X}. Observe que as
´unicas novas arestas de G
i
com respeito a G
i−1
s˜ao cobertas pela parte X e uma
´unica parte de (X
H
, T
H
) cont´em v
i
e Q
1
foi acrescentada `a parte X representada
por uma folha t
X
, adjacente `a um v´ertice t
Q
1
que representa uma parte X
Q
1
que
j´a continha Q
1
. Portando, claramente vemos que (X
H
, T
H
) ´e uma DEA de
H ∪ {v
i
}, logo, (X , F ) ´e uma DEF de G
i
.
a
b c
d
e f
g
h
j
k
l m
abc
n
bcd
jkl lm
eih
feh
hi gfh
i
(a) G
i
e DEA de G
i−1
(G
i
\ n)
a
b c
d
e f
g
h
j
k
l m
abc
n
bcd
jkl lm
eih
feh
hi gfh
i
ihn
(b) DEA de G
i
(v
i
= n)
Figura 8.2. N
G
i−1
(v
i
= n) induz apenas uma clique
(iii) N
G
i
(v
i
) = Q
1
∪Q
2
. Observe que Q
1
e Q
2
podem ou n˜ao pertencer a uma mesma
componente de G
i−1
. No primeiro caso (Figura 8.3), seja H a componente de
G
i−1
que cont´em Q
1
e Q
2
. Como no caso anterior, defina (X
H
, T
H
). Al´em
disso, considere X
Q
1
, X
Q
2
∈ X
H
contendo as cliques Q
1
, Q
2
respectivamente.
Novamente, precisamos apenas modificar (X
H
, T
H
) para obter uma DEA de
H ∪{v
i
}. Para tanto, considere um caminho qualquer em T
H
entre t
Q
1
e t
Q
2
(t
Q
1
e t
Q
2
representando X
Q
1
e X
Q
2
respectivamente em T
H
). Para X
Q
1
, X
Q
2
e X
j
61
8. Algoritmo de decomposi¸c˜ao baseado no Teorema do V´ertice Bi-simplicial
tal que t
j
pertence a esse caminho, fazemos X
Q
1
= X
Q
1
∪{v
i
}, X
Q
2
= X
Q
2
∪{v
i
}
e X
j
= X
j
∪{v
i
}. Observe que as ´unicas novas arestas de G
i
com respeito a G
i−1
s˜ao cobertas pelas partes X
Q
1
e X
Q
2
. Al´em disso, todas as partes que cont´em v
i
formam um caminho em T
H
. Portando, claramente vemos que (X
H
, T
H
) ´e uma
DEA de H ∪ {v
i
}, logo, (X , F ) ´e uma DEF de G
i
.
a
b c
d
e f
g
h
j
k
l m
abc
n
bcd
jkl lm
eih
feh
hi gfh
i
(a) G
i
e DEA de G
i−1
(G
i
\ n)
a
b c
d
e f
g
h
j
k
l m
abc
n
bcd
jkl lm
hi gfh
i
eihn fehn
(b) DEA de G
i
(v
i
= n)
Figura 8.3. N
G
i−1
(v
i
= n) induz duas cliques que est˜ao em uma mesma componente de
G
i−1
No segundo caso, ou seja, quando Q
1
e Q
2
pertencem a componentes distintas H
1
e H
2
de G
i−1
respectivamente (Figura 8.4), temos que em G
i
uma componente
H existe tal que H = H
1
∪ H
2
∪ {v
i
}. Dessa forma, vamos fazer a uni˜ao das
DEA de H
1
e H
2
contidas em (X , F ), modificando-as ligeiragemente, a fim de
obtermos uma DEA de H. Consideramos, portanto, (X
H
1
, T
H
1
) uma DEA de
H
1
e (X
H
2
, T
H
2
) uma DEA de H
2
contidas em (X , F ). Portanto, criamos as
partes X
v
i
= {v
i
}, X
Q
1
= Q
1
∪ {v
i
} e X
Q
2
= Q
2
∪ {v
i
} e fazemos X
H
= X
H
1
∪
X
H
2
∪ {X
v
i
, X
Q
1
, X
Q
2
}, V (T
H
) = V (T
H
1
) ∪ V (T
H
2
) ∪ {t
v
i
, t
Q
1
, t
Q
2
} e E(T
H
) =
E(T
H
1
) ∪ E(T
H
2
) ∪ {(t
v
i
, t
Q
1
), (t
v
i
, t
Q
2
), (t
Q
1
, t
Q
1
), (t
Q
2
, t
Q
2
)} onde X
Q
1
∈ X
H
1
,
X
Q
2
∈ X
H
2
s˜ao quaisquer partes de (X
H
1
, T
H
1
) e (X
H
2
, T
H
2
) que cont´em Q
1
e Q
2
62
8. Algoritmo de decomposi¸c˜ao baseado no Teorema do V´ertice Bi-simplicial
respectivamente. Observe que as ´unicas arestas de G
i
com respeito a G
i−1
s˜ao
cobertas pelas partes X
Q
1
e X
Q
2
e as ´unicas trˆes partes que cont´em v
i
em X
H
formam um caminho de tamanho 2. Logo, claramente, (X , F) ´e uma DEF de
G
i
.
a
b
d
e f
g
h
j
k
l m
abc
n
bcd
jkl lm
hi gfh
i
eih feh
c
(a) G
i
e DEA de G
i−1
(G
i
\ n)
a
b
d
e f
g
h
j
k
l m
abc
n
bcd
jkl lm
hi gfh
i
eih feh
c
cdn
ihn
n
(b) DEA de G
i
(v
i
= n)
Figura 8.4. N
G
i−1
(v
i
= n) induz duas cliques que est˜ao em componentes distintas de
G
i−1
Observe que quando G ´e um grafo livre de buracos pares conexo e v
n
, · · · , v
1
´e uma
ordem de elimina¸c˜ao bi-simplicial de G, o procedimento acima retorna uma DEA de G.
Tal procedimento ´e apresentado em uma linguagem algor´ıtmica no Algoritmo 2.
63
8. Algoritmo de decomposi¸c˜ao baseado no Teorema do V´ertice Bi-simplicial
Algoritmo 2 (DEAVerticeBisimplicial)
Entrada: Grafo livre de buracos pares G, Ordem de elimina¸c˜ao bi-simplicial v
n
, · · · , v
1
de G
Sa´ıda: Decomposi¸c˜ao em floresta D = (X , T ) de G (quando G ´e conexo, uma DEA de G
´e retornada)
1: X ← ∅, V (T ) ← ∅, i ← 1
2: enquanto i ≤ n fa¸ca
3: se N
G
i
(v
i
) ´e vazia ent˜ao
4: X ← {v
i
}, X ← X ∪ X
5: Considere t
X
o n´o representando X em T
6: V (T ) ← V (T ) ∪ {t
X
}
7: sen˜ao
8: se N
G
i
(v
i
) induz apenas uma clique Q
1
ent˜ao
9: Considere X
Q
1
∈ X contendo Q
1
e t
X
Q
1
o n´o de T representando X
Q
1
10: X ← Q
1
∪ {v
1
}, X ← X ∪ X
11: Considere t
X
um v´ertice representando X em T
12: V (T ) ← V (T ) ∪ t
X
, E(T ) ← E(T ) ∪ (t
X
, t
X
Q
1
)
13: sen˜ao
14: Considere Q
1
e Q
2
as duas cliques em que N
G
i
(v
i
) ´e particionada
15: Considere X
Q
1
∈ X contendo Q
1
e t
X
Q
1
o n´o de T representando X
Q
1
16: Considere X
Q
2
∈ X contendo Q
2
e t
X
Q
2
o n´o de T representando X
Q
2
17: se X
Q
1
e X
Q
2
s˜ao representados por uma mesma ´arvore T
de T ent˜ao
18: Escolha partes X
Q
1
contendo Q
1
e X
Q
2
contendo Q
2
de X de forma que a distˆancia
entre os n´os t
X
Q
1
e t
X
Q
2
, representando X
Q
1
e X
Q
2
respectivamente, seja m´ınima
19: X
Q
1
← X
Q
1
∪ {v
i
}, X
Q
2
← X
Q
2
∪ {v
i
}
20: Acrescente v
i
em todas as partes de X representadas pelos v´ertices que est˜ao no
´unico caminho entre t
X
Q
1
e t
X
Q
2
em T
21: sen˜ao
22: X
Q
1
Q
2
← {v
i
}, X
Q
1
← Q
1
∪ {v
i
}, X
Q
2
← Q
2
∪ {v
i
}
23: X ← X ∪ {X
Q
1
Q
2
, X
Q
1
, X
Q
2
}
24: Considere t
X
Q
1
Q
2
, t
X
Q
1
e t
X
Q
2
v´ertices de T representando X
Q
1
Q
2
, X
Q
1
e X
Q
2
25: E(T ) ← E(T ) ∪ {(t
X
Q
1
, t
X
Q
1
), (t
X
Q
2
, t
X
Q
2
), (t
X
Q
1
Q
2
, t
X
Q
1
), (t
X
Q
1
Q
2
, t
X
Q
2
)}
26: fim se
27: fim se
28: fim se
29: i ← i + 1
30: fim enquanto
31: return D
64
8. Algoritmo de decomposi¸c˜ao baseado no Teorema do V´ertice Bi-simplicial
8.2. Corretude do algoritmo
Teorema 8.2.1. Seja G um grafo livre de buracos pares. O algoritmo 2 produz uma DEF
de G.
Prova: Observe que os argumentos dos Itens 2i, 2ii e 2iii da defini¸c˜ao do procedimento
para decompor os grafos planares livres de buracos apresentada na se¸c˜ao 8.1 formam uma
prova por indu¸c˜ao no n´umero i de itera¸c˜oes do algoritmo. ✷
8.3. Complexidade do algoritmo
Calculemos primeiro, de forma grosseira, a complexidade de encontrar uma ordem de
elimina¸c˜ao bi-simplicial de G. Para encontrar o i-´esimo v´ertice da ordem de um grafo G
livre de buracos pares com n v´ertices, ´e necess´ario testar, no pior caso, (n−i) v´ertices. Para
cada v´ertice v, precisamos testar se N(v) pode ser particionada em duas cliques. Como
d(v) ≤ n − 1 e precisamos testar a existˆencia de arestas entre todos os pares de v´ertices
de N(v), temos que testar se um v´ertice v ´e bi-simplicial pode ser feito em O(n
2
). Logo,
conclu´ımos que a ordem de elimina¸c˜ao bi-simplicial pode ser constru´ıda em O(n
3
).
No Algoritmo 2, como j´a temos uma ordem de elimina¸c˜ao bi-simplicial de G , j´a con-
hecemos a vizinhan¸ca de v
i
em G
i
, 1 ≤ i ≤ n, logo, os testes das linhas 3, 8 e 13 do
algoritmo podem ser feitos em tempo constante. Observe que as linhas 4 a 6, 10 a 12 e 22
a 25 tamb´em podem ser executadas em tempo constante (pois tais passos consistem apenas
em adicionar v´ertices ou arestas em T e partes em X ). Observe que em cada itera¸c˜ao do
bloco “enquanto” (Linha 2), s˜ao adicionadas no m´aximo 3 novas partes em X (Linhas 4,
10 ou 22), logo, o n´umero de partes em X antes da execu¸c˜ao da linha 2 do algoritmo ´e
O(i − 1). Dessa forma, para executar as linhas 15 e 16 do algoritmo, s˜ao necess´arios no
pior caso O((n − i)(i − 1)) testes ( pois |N
G
i
(v
i
)| ´e O(n − i) e para cada v ∈ N
G
i
(v
i
),
´e testado no pior caso se v pertence a O(i − 1) partes). Para se executar a linha 18 do
algoritmo, primeiramente, pode-se escolher uma parte qualquer X
Q
1
contendo Q
1
e uma
parte qualquer X
Q
2
contendo Q
2
(tais escolhas podem ser feitas em O(|Q
1
| ∗ (i − 1)) e
O(|Q
2
| ∗ (i − 1)) passos respectivamente no pior caso, ou seja, quando somente a ´ultima
parte a ser testada ´e a que cont´em Q
1
ou Q
2
). Dep ois, o ´unico caminho entre t
X
Q
1
e t
X
Q
2
em T ´e percorrido nos dois sentidos (t
X
Q
1
representando X
Q
1
e t
X
Q
2
representando X
Q
2
)
e para cada v´ertice t de tal caminho, ´e analisado se Q
1
e Q
2
est˜ao contidos em X
t
, e caso
65
8. Algoritmo de decomposi¸c˜ao baseado no Teorema do V´ertice Bi-simplicial
esteja contido, X
Q
1
ou X
Q
2
s˜ao substitu´ıdos por X
t
. Como a vizinhan¸ca de v
i
na itera¸c˜ao i
do bloco “enquanto” ´e O(n − i), o ´ultimo teste tamb´em pode ser feito em O((n − i)(i − 1))
passos. Pelos argumentos anteriores e p elo fato da linha 2 ser executada n vezes (uma vez
para cada v´ertice de G), conclu´ımos que a complexidade assint´otica do algoritmo no pior
caso ´e O(n
2
).
66
9
Conclus˜ao e trabalhos futuros
Nesta disserta¸c˜ao de mestrado, incrementamos o conjunto de menores topol´ogicos proibidos
para a classe dos grafos planares livres de buracos pares, provando que tal classe de grafos
n˜ao possui um menor topol´ogico grade 10 × 10 [22]. Na continua¸c˜ao desse trabalho, prova-
mos um resultado mais forte: os grafos planares livres de buracos pares n˜ao possuem um
menor grade 9 × 9 [21]. Tal resultado implica que a largura em ´arvore de tal classe de
grafos ´e limitada (no m´aximo 44).
Um outro resultado desta disserta¸c˜ao foi uma vers˜ao do Teorema da Decomposi¸c˜ao [10]
para os grafos planares. Conjecturamos que esse resultado pode ser usado para obter um
algoritmo de decomposi¸c˜ao em ´arvores para os grafos planares usando os cortes descritos
no teorema. Visto que os cortes, com exce¸c˜ao do 2-join, tˆem cardinalidade no m´aximo 4
e que os grafos b´asicos tˆem uma largura no m´aximo 4, poder´ıamos medir a qualidade da
decomposi¸c˜ao obtida em fun¸c˜ao da altura da ´arvore de decomposi¸c˜ao do grafo (a ´arvore
que decomp˜oe o grafo atrav´es dos cortes em grafos b´asicos).
O ´ultimo resultado desta disserta¸c˜ao foi o algoritmo que produz uma decomposi¸c˜ao
em ´arvore para um grafo sem buracos pares qualquer, baseado no Teorema do V´ertice
Bi-Simplicial [7]. Conjecturamos que no caso dos grafos de Γ, usando os resultados sobre
menores proibidos para essa classe, podemos medir a qualidade da decomposi¸c˜ao em ´arvore
produzida por esse algoritmo. Podemos tamb´em tentar usar, para obter uma decomposi¸c˜ao
em ´arvore de um grafo de Γ, um resultado recente de Silva e Vuskˇovi`c [23], que afirma que
todo grafo pertencente a essa classe tem um v´ertice cuja vizinhan¸ca induz um grafo cordal.
Conclu´ımos esta disserta¸c˜ao com a observa¸c˜ao de que o problema de decomposi¸c˜ao em
´arvore de grafos planares sem buracos pares foi abordado de v´arias maneiras e com as
9. Conclus˜ao e trabalhos futuros
diversas caracteriza¸c˜oes feitas para essa classe at´e ent˜ao, com dois objetivos: do ponto de
vista te´orico, limitar a largura em ´arvore dos grafos dessa classe e do ponto de vista pr´atico,
obter um algoritmo de decomposi¸c˜ao em ´arvore para esses grafos. Portanto, com os dois
objetivos atingidos e com o dom´ınio de todas as caracteriza¸c˜oes conhecidas dessa classe de
grafos, podemos prosseguir a pesquisa de um algoritmo exato polinomial de decomposi¸c˜ao
em ´arvore dessa classe de grafos.
68
Referˆencias Bibliogr´aficas
[1] S. Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded
decomposibility - a survey. BIT, 25:2–23, 1985.
[2] S. Arnborg, D.G. Corneil, and A. Proskurowski. Complexity of finding embeddings
in a k-tree. SIAM Journal on Algebraic and Discrete Math, 7:277–285, 1986.
[3] S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs.
Journal of Algorithms, 12:308–340, 1991.
[4] E. Birnel´e, J.A. Bondy, and B.A. Reed. Tree-width of graphs without a 3 × 3 grid
minor. 2006.
[5] H.L. Bodlaender. A linear time algorithm for finding tree-decompositions of small
treewidth. SIAM J. Comput, 25:1305–1317, 1996.
[6] Luis Eduardo Ximenes Carvalho. Decomposi¸c˜ao em
´
Arvore de grafos com largura
limitada - uma pesquisa algor´ıtmica. Disserta¸c˜ao de mestrado, Universidade Federal
do Cear´a (UFC), agosto 2002.
[7] M. Chudnovsky, B. Reed, F. Havet, P.D. Seymour, and L. Addario-Berry. Bisimplicial
vertices in even-hole-free graphs. Submetido ao Journal of Combinatorial Theory,
Series B, 2006.
[8] R. Diestel. Graph Theory - Graduate Texts in Mathematics, Volume 173. Springer-
Verlag, Heidelberg, second edition, 2000.
Referˆencias Bibliogr´aficas
[9] M.R. Garey and D.S. Johnson. Computers and Intractability. A Guide to the Theory
of NP-Completeness. Freeman, 1979.
[10] A. Kapoor, G. Cornu´ejols, K. Vuskˇovi`c, and M. Conforti. Even-hole-free graphs part
i: Decomposition theorem. Journal of Graph Theory, 39:6–49, 2002.
[11] A.M.C.A. Koster, S.P.M. van Hoesel, and A.W.J. Kolen. Solving partial constraint
satisfaction problems with tree decomposition. Network, (40):3:170–180, 2002.
[12] K. Kuratowski. Sur le probl`eme des courbes gauches en topologie. Fund. Math.,
15:271–283, 1930.
[13] J. Lagergren. Efficient parallel algorithms for graphs of bounded treewidth. Journal
of Algorithms, 20:20–44, 1996.
[14] S.L. Mitchell, E.J. Cockayne, and S.T. Hedetniemi. Linear algorithms on recursive
representations of trees. J. Comput. Syst. Sci., 18:76–85, 1979.
[15] O. Porto. Even induced cycles in planar graphs. In Proceedings of First Latin American
Symposium on Theoretical Informatics, Sao Paulo, Brazil, April 1992.
[16] J. Ramirez-Alfonsin and B. Reed (eds.). Perfect graphs. Wiley,Chichester, 130, 2001.
[17] N. Robertson and P.D. Seymour. Graph minors v: Excluding a planar graph. Journal
of Combinatorial Theory, Series B, 41:92–114, 1986.
[18] N. Robertson and P.D. Seymour. Graph minors xiii: The disjoint path problem.
Journal of Combinatorial Theory, Series B, 63:65–110, 1995.
[19] N. Robertson and P.D. Seymour. Graph minors. xx. wagner’s conjecture. Journal of
Combinatorial Theory, Series B, 92:325–357, 2004.
[20] N. Robertson, P.D. Seymour, and R. Thomas. Quickly excluding a planar graph.
Journal of Combinatorial Theory, Series B, 62:323–348, 1994.
[21] A. A. Silva, A. S. F. Silva, and C. L. Sales. Even-hole-free planar graphs have bounded
treewidth. IV Latin American Conference on Combinatorics, Graphs and Applica-
tions, 2007. accepted.
70
Referˆencias Bibliogr´aficas
[22] A. A. Silva, A. S. F. Silva, and C. L. Sales. Largura em
´
Arvore de grafos planares livres
de ciclos pares induzidos. Anais do 39o. Simp´osio Brasileiro de Pesquisa Operacional,
2007. accepted.
[23] M.V.G. Silva and K. Vuskˇovi`c. Triangulated neighborhoods in even-hole-free graphs.
Discrete Mathematics, 307:1065–1073, 2007.
[24] R. Thomas. Tree decompositions of graphs. Dispon´ıvel em
www.math.gatech.edu/ thomas/SLIDE/CBMS/trdec.pdf.
[25] K. Wagner. Graphentheorie, volume 248/248a. B.J. Hochschultascschenbucher,
Mannheim, first edition, 1970.
71
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo