Projeto e Análise de Algoritmos I

Aula 25 - Planaridade

Lucas Nunes Alegre

Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica


Estes slides utilizam conteúdo adaptado da bibliografia da disciplina e também de notas de aula e slides prévios dos professores Bruno Grisci, Rodrigo Machado e André Grahl.

Planaridade

Imersões Planares

Como já vimos, um mesmo grafo G tem diversas representações gráficas:

…

Definição: Uma associação:

nodos \mapsto pontos
arestas \mapsto curvas simples contínuas entre os pontos associados a vértices

determina uma imersão (embedding) do grafo no plano X-Y.

Definição: Uma imersão é planar sss duas curvas distintas se encontram somente nos pontos dos vértices.

O Problema das Três Casas

Em inglês, three utilities problem: https://en.wikipedia.org/wiki/Three_utilities_problem

Grafos Planares

Definição: Um grafo G é planar sss G possui alguma imersão planar.

Intuitivamente: Existe uma forma de desenhá-lo no plano sem que tenhamos arestas cortando outras arestas.

Exercício: Determine quais dos seguintes grafos são planares:

Grafos Planares: Exemplos

Os grafos que representam os cinco poliedros regulares são planares:

Ideia: “Expandir” um dos lados do poliedro, achatando a superfície tridimensional. Considera-se a região externa a “face” do lado expandido.

Grafos Planares: Definições de Topologia

Definição: Um conjunto aberto (no plano) é um subconjunto X \subseteq R^2 tal que, para qualquer ponto p \in X há uma dada distância \epsilon para a qual todos os pontos no plano a \epsilon de distância de p estão em X.

Definição: Uma região R é um conjunto aberto (no plano) onde, para qualquer par de pontos p1 e p2, há um caminho simples contínuo entre eles em R.

Definição: Uma face de uma imersão de um grafo G no plano é uma região maximal que não contém nenhum ponto da imersão.

Teorema: (Jordan) Uma curva c em R^2 fechada contínua e simples (não repete elementos, com exceção dos pontos iniciais/finais) divide o plano em exatas duas regiões: interna e externa, sendo que toda curva contínua ligando um ponto interno a um ponto externo intersecciona c em no mínimo um ponto.

Grafos Planares: Visualizando as Definições

X ε p q ∉ X

Conjunto aberto: todo p \in X tem um disco de raio \epsilon contido em X. A borda (tracejada) não pertence a X: nenhum disco em torno de q caberia em X.

R p1 p2 não é região

Região: conjunto aberto e conexo: quaisquer p_1, p_2 \in R são ligados por uma curva contínua dentro de R. À direita, um aberto que não é região.

f1 f2 f3 f4 (externa)

Face: cada região maximal que sobra ao retirar do plano os pontos da imersão. Aqui há 4 faces; f_4 é a face externa (ilimitada).

c interior exterior a b

Jordan: a curva fechada simples c divide o plano em interior e exterior; toda curva contínua de a (interior) até b (exterior) cruza c.

Grafos Planares: Grafo Dual Planar

Definição: Seja G um pseudografo planar. O pseudografo dual planar de uma imersão planar de G, também chamado dual geométrico, é o pseudografo G'=(V',E') onde

  • V' é o conjunto de faces da imersão planar de G.
  • existe uma aresta \{f_1,f_2\} \in E' para cada aresta e \in E dividindo as faces f_1 e f_2 em G.

Exemplo: Pseudografo G e o dual de G.

Nota: Duas imersões planares distintas de um mesmo pseudografo G podem ter duais não-isomorfos.

Mapas

Fórmula de Euler

Grafos Planares: Fórmula de Euler (Lema)

Lema: Para um grafo planar G,

\textcolor{#d96c00}{v} + \textcolor{#006666}{f} = \textcolor{#bf0000}{e} + \textcolor{#6c006c}{c} + 1

onde

  • \textcolor{#d96c00}{v}: número de vértices = |V|
  • \textcolor{#006666}{f}: número de faces de uma imersão planar de G
  • \textcolor{#bf0000}{e}: número de arestas = |E|
  • \textcolor{#6c006c}{c}: número de componentes conexos

Grafos Planares: Fórmula de Euler (Prova do Lema)

Demonstração: Por indução no número de arestas (\textcolor{#bf0000}{e}):

  • Caso base: \textcolor{#bf0000}{e}=0: \textcolor{#d96c00}{v} + 1 = 0 + \textcolor{#d96c00}{v} + 1 (prova válida)

  • Passo indutivo:

  • Suponha que \textcolor{#d96c00}{v} + \textcolor{#006666}{f} = \textcolor{#bf0000}{e} + \textcolor{#6c006c}{c} + 1 valha para grafo planar G (hipótese indutiva).

  • Tome uma imersão planar de G, como base, e considere a adição de uma aresta i entre dois nodos não-adjacentes de G de tal forma que não haja cruzamento de arestas. Duas possibilidades:

    • i conecta dois nodos de um mesmo componente conexo. Nesse caso, aumenta-se em um o número de faces (planaridade) e o número de arestas, onde temos \textcolor{#d96c00}{v} + (\textcolor{#006666}{f}+1) = (\textcolor{#bf0000}{e}+1) + \textcolor{#6c006c}{c} + 1.
    • i conecta dois nodos em componentes conexos distintos. Neste caso, não se adicionam faces porém reduz-se (em uma unidade) o número de componentes conexos do grafo, e temos \textcolor{#d96c00}{v} + \textcolor{#006666}{f} = (\textcolor{#bf0000}{e}+1) + (\textcolor{#6c006c}{c}-1) + 1. \blacksquare

Grafos Planares: Fórmula de Euler

Teorema: Para um grafo planar e conexo G,

\textcolor{#d96c00}{v} + \textcolor{#006666}{f} = \textcolor{#bf0000}{e} + 2

onde

  • \textcolor{#d96c00}{v}: número de vértices
  • \textcolor{#006666}{f}: número de faces de uma imersão planar de G
  • \textcolor{#bf0000}{e}: número de arestas

Demonstração: Usando a prova do lema anterior, contando \textcolor{#d96c00}{v}-1 vezes o caso 2 (conexão de nodos em componentes conexos distintos).

Grafos Planares: Quantidade Máxima de Arestas

Os grafos planares possuem a propriedade de serem esparsos (poucas arestas).

Definição: Um grafo simples planar G = (V,E) é maximal se, para toda aresta e \notin E, G' = (V,E \cup \{e\}) não é planar.

Teorema: Um grafo simples planar maximal G possui \textcolor{#bf0000}{e} = 3\textcolor{#d96c00}{v} - 6 arestas.

Demonstração:

  • G é conexo.
  • Todas as regiões de um grafo simples planar maximal são triângulos.
  • Como cada face é composta por três arestas, podemos inicialmente aproximar 3\textcolor{#006666}{f} \propto \textcolor{#bf0000}{e}.
  • Contudo, isso estaria contando duas vezes cada aresta, portanto a fórmula exata é 3\textcolor{#006666}{f} = 2\textcolor{#bf0000}{e}.
  • Substituindo \textcolor{#006666}{f} na fórmula de Euler pelo resultado anterior, obtemos \textcolor{#bf0000}{e} = 3\textcolor{#d96c00}{v} -6. \blacksquare

Grafos Planares: Quantidade Máxima de Arestas

Exemplo: octaedro, planar maximal com \textcolor{#d96c00}{v} = 6.

1. Faces: \textcolor{#006666}{f} = 8, todas triângulos (inclusive a externa).

2. Contando por face: cada face marca suas 3 arestas, totalizando 3\textcolor{#006666}{f} = 24 marcas. Mas só há \textcolor{#bf0000}{e} = 12 arestas: 3\textcolor{#006666}{f} \propto \textcolor{#bf0000}{e} conta arestas repetidas.

3. Contando por aresta: cada aresta separa exatamente 2 faces, então recebe 2 marcas (uma de cada lado). Logo 3\textcolor{#006666}{f} = 2\textcolor{#bf0000}{e}, ou seja, 24 = 2 \cdot 12.

4. Euler: substituindo \textcolor{#006666}{f} = \tfrac{2}{3}\textcolor{#bf0000}{e} em \textcolor{#d96c00}{v} + \textcolor{#006666}{f} = \textcolor{#bf0000}{e} + 2:

\begin{aligned} \textcolor{#d96c00}{v} + \tfrac{2}{3}\textcolor{#bf0000}{e} &= \textcolor{#bf0000}{e} + 2 \\ \textcolor{#d96c00}{v} - 2 &= \tfrac{1}{3}\textcolor{#bf0000}{e} \\ \textcolor{#bf0000}{e} &= 3\textcolor{#d96c00}{v} - 6 \quad \blacksquare \end{aligned}

Conferindo: 3 \cdot 6 - 6 = 12 = \textcolor{#bf0000}{e} ✓

Grafos Planares: Quantidade Máxima de Arestas

Teorema: Um grafo simples planar maximal G possui \textcolor{#bf0000}{e} = 3\textcolor{#d96c00}{v} - 6 arestas.

Corolário: Se G é planar, então \textcolor{#bf0000}{e} \leq 3\textcolor{#d96c00}{v} - 6.

Obs: Note que isto não é uma equivalência:

  • Nem todo grafo com \textcolor{#bf0000}{e} \leq 3\textcolor{#d96c00}{v} - 6 é planar.
  • Exemplo: K_{3,3} tem \textcolor{#d96c00}{v} = 6 e \textcolor{#bf0000}{e} = 9, e portanto \textcolor{#bf0000}{e} \leq 3\textcolor{#d96c00}{v} - 6, mas K_{3,3} é não-planar.

Grafos Planares: Exemplos do Limite

Planar maximal (octaedro)
\textcolor{white}{e = 3v-6} · planar

e = 12 3v − 6 = 12

\textcolor{#d96c00}{v} = 6, \textcolor{#bf0000}{e} = 12, \textcolor{#006666}{f} = 8. Todas as faces são triângulos e o limite é atingido exatamente.

Grafo completo K_5
\textcolor{white}{e > 3v-6} ⇒ não planar

e = 10 3v − 6 = 9 +1

\textcolor{#bf0000}{e} = 10 > 9: pelo corolário, K_5 não é planar. O teste funciona!

Bipartido K_{3,3}
\textcolor{white}{e \leq 3v-6} ⇒ inconclusivo

e = 9 3v − 6 = 12 ?

\textcolor{#bf0000}{e} = 9 \leq 12: o corolário não conclui nada, e mesmo assim K_{3,3} não é planar.

Resumo: \textcolor{#bf0000}{e} \leq 3\textcolor{#d96c00}{v} - 6 é condição necessária, mas não suficiente: serve para provar que um grafo não é planar, nunca que ele é planar.

Caracterização de Planaridade

Não-Planaridade de K_{3,3} e K_5

Os seguintes grafos não-planares são especiais:

K_5 =

\textcolor{#d96c00}{v} = 5 \qquad \textcolor{#bf0000}{e} = 10

K_{3,3} =

\textcolor{#d96c00}{v} = 6 \qquad \textcolor{#bf0000}{e} = 9

Caracterização de Planaridade

Definição: Dado um grafo simples G, uma extensão direta de G é um grafo G' obtido pela eliminação de uma aresta em G e a introdução de um caminho de tamanho 2 no lugar da aresta removida (com um nodo novo).

Exemplo:

G =

\quad \Rightarrow \quad G' =

Definição: Dado um grafo simples G, uma extensão de G é um grafo G' obtido através de um número finito (possivelmente zero) de sucessivas extensões diretas de G.

G =

\quad \Rightarrow \quad G' =

Caracterização de Grafos Planares

Teorema: (Kuratowski) Um grafo simples é não-planar sss possui como subgrafo uma extensão de K_5 ou de K_{3,3}.

Demonstração: Não será vista nessa disciplina.

Exemplo: Mostre que o grafo de Petersen não é planar utilizando o teorema de Kuratowski.

1. Escolhemos as arestas \textcolor{#c62828}{\{a2, a3\}} e \textcolor{#c62828}{\{b1, b4\}} para remover.

2. Sem elas, a2, a3, b1, b4 ficam com grau 2: são só pontos no meio de caminhos (subdivisões de arestas).

3. Os demais vértices têm grau 3: \textcolor{#1565c0}{V_1 = \{a1, b0, a4\}} e \textcolor{#c62828}{V_2 = \{a0, b2, b3\}}.

4. Redesenhando: cada vértice de \textcolor{#1565c0}{V_1} se liga a cada vértice de \textcolor{#c62828}{V_2} por um caminho, o que dá uma extensão de K_{3,3}.

5. Suavizando os vértices de grau 2, obtemos exatamente K_{3,3}. Pelo teorema de Kuratowski, o grafo de Petersen não é planar. \blacksquare

Caracterização de Grafos Planares (2)

Definição: Contração de aresta (grafos simples).
Seja G=(V,E) um grafo simples e uma aresta e=\{v,w\} \in E. Definimos a contração de e em G, denotada G/e, como o grafo G' = (V',E') onde

V' = V - \{v,w\} \uplus \{\bullet\}

E' = \{ e \mid e \in E,\ \ v \notin e,\ \ w \notin e \} \cup \{ \{\bullet, x\} \mid x \in V \land (v \ \text{adj}\ x \lor w\ \text{adj}\ x) \}

Exemplo:

G =

\quad \Rightarrow \quad G/\{a,d\} =

Teorema: (Wagner) Um grafo simples G é não-planar sss possui um subgrafo que pode ser transformado em K_5 ou K_{3,3} através de um número finito (possivelmente zero) de contrações de aresta.

Demonstração: Não será vista nessa disciplina.

Caracterização de Grafos Planares (2)

Exemplo: mostre que o grafo de Petersen não é planar utilizando o teorema de Wagner.

1. Escolhemos as 5 arestas \{a_i, b_i\}, que ligam o pentágono externo à estrela interna (cada par com uma cor).

2. Contraindo \{a0, b0\}: os dois viram um só vértice, que herda os vizinhos de ambos: a1, a4, b2, b3.

3. Contraindo as demais, /\{a1,b1\}/\{a2,b2\}/\{a3,b3\}/\{a4,b4\}, as arestas da estrela \{b_i, b_{i+2}\} viram as diagonais do pentágono.

4. Restam 5 vértices, todos adjacentes entre si: é o K_5! Pelo teorema de Wagner, o grafo de Petersen não é planar. \blacksquare

Algoritmos e Aplicações

Algoritmo de Hopcroft-Tarjan

  • O algoritmo de Hopcroft-Tarjan determina a planaridade de um grafo de forma linear usando DFS: O(n).


Artigo: https://www.cse.iitk.ac.in/users/dsrkg/cs245/html/Planarity.pdf

Circuitos Planares e Não Planares

  • Circuitos planares
    • Usados em placas de circuitos impressos (finas camadas de material isolante com traços condutores impressos).
    • São usadas para conectar componentes eletrônicos em computadores, celulares, etc.
  • Circuitos não planares
    • Usados em circuitos integrados 3D, compostos por múltiplas camadas de componentes eletrônicos conectados por fios ou trilhas verticais.
    • Circuitos integrados 3D normalmente oferecem maior densidade e menor consumo de energia.

Printed Circuit Board

?