Grafos String

Grafos de interseção de curvas foram introduzidos por Sinden em (Sinden 1966) num estudo sobre circuitos RC e, mais tarde, estudados em (Ehrlich 1976). O termo ”grafos string” foi introduzido por Graham em (Graham 1976) propondo o problema de caracterização desta classe de grafos. Este trabalho faz uma breve introdução a classe de grafos string.

Introdução

Seja \(S\) um conjunto finito de curvas no plano. Dizemos que duas curvas \(a,b\in S\) se intersectam se eles têm ao menos um ponto em comum e denotaremos por \(a\cap b\neq\emptyset\). O grafo \(G=(V,E)\) tal que \(V=S\) e \(ab\in E\) se, e somente se, as curvas \(a\) e \(b\) se intersectam é o grafo de interseção de \(S\). E um grafo \(G\) é string se existe um conjunto de curvas no plano no qual \(G\) é o grafo de interseção de \(S\) e dizemos que \(S\) é uma representação de curvas de \(G\). Como cada curva corresponde a um vértice, utilizaremos os termos vértice e curva indistintamente.

Formalizando as definições, uma curva é uma função \(\gamma:I\rightarrow\mathbb{R}^{2}\) homeomorfa a sua imagem, onde \(I=[0,1]\). E duas curvas \(\gamma\) e \(\delta\) se intersectam se existem \(s,t\in I\) tais que \(\gamma(s)=\delta(t)\).

TODO incluir exemplos

\label{lemma:prop}

Todo grafo string possui uma representação de string satisfazendo:

  1. 1.

    duas curvas se intersectam um número finito de vezes,

  2. 2.

    por cada ponto passam no máximo duas curvas, e

  3. 3.

    se \(deg(u)\leq 2\), então a curva de \(u\) possui somente um ponto de interseção com cada um de seus vizinhos.

Proof.
  1. 1.

    TODO trivial?!

  2. 2.

    Sempre podemos alterar as curvas localmente em torno do ponto de interseção entre três ou mais curvas de modo que haja somente interseções entre duas curvas.

  3. 3.

    Temos dois casos. Primeiramente, se \(deg(u)=1\), então basta reduzirmos a curva \(u\) de forma a ter somente uma única interseção com o seu único vizinho. Se \(deg(u)=2\) e \(\gamma\) é a curva representando \(u\), então existem \(s<t\in I\) tais que \(\gamma(s)\) é uma interseção com um dos vizinhos de \(u\), \(\gamma(t)\) é uma interseção com o outro vizinho de \(u\) e \(\gamma\) não possui nenhuma interseção no intervalo \((s,t)\). Então, podemos substituir a curva \(\gamma\) por \(\gamma^{\prime}=\gamma|_{[s-\epsilon_{0},t+\epsilon_{1}]}\) para algum \(\epsilon_{0},\epsilon_{1}>0\).

Mostraremos agora que a classe de grafos string é um subconjunto próprio do conjunto de grafos através do seguinte resultado.

Dado um grafo \(G\), seja \(G^{\prime}\) o grafo resultante da subdivisão de cada aresta de \(G\). Temos que \(G^{\prime}\) é grafo string se, e somente se, \(G\) é planar.

Proof.

Se \(G\) é planar, então \(G^{\prime}\) também é planar. Logo, \(G^{\prime}\) é grafo string (ver \ref{prop:planar}). Por outro lado, assuma que \(G^{\prime}\) é grafo string. Seja \(R\) uma representação de curvas de \(G\). Temos que os vértices de \(G\) em \(G^{\prime}\) estão representadas por curvas que só possuem interseção com as curvas que representam os vértices da subdivisão. Estes, por sua vez, têm exatamente duas interseções: uma para cada vértice de \(G\) adjacente. Assim, sem perda, podemos assumir que as interseções dessas curvas ocorrem exatamente nos extremos. Se contrairmos as curvas que representam os vértices de \(G\) a um ponto, teremos uma representação plana de \(G\). Portanto, \(G\) é planar. ∎

O grafo resultante da subdivisão das arestas do \(K_{5}\) não é grafo string.

TODO incluir figuras

Subclasses de Grafos String

Apresentaremos nesta seção algumas classes de grafos e como elas estão relacionadas a classe de grafos string. Começaremos apresentando o resultado já utilizado na seção anterior.

\label{prop:planar}

Todo grafo planar é grafo string.

Proof.

Dado um grafo planar, podemos construir a sua representação de curvas a partir de sua representação plana da seguinte forma: para cada vértice, faça uma curva contornando o vértice e pouco mais da metade das arestas incidentes ao vértice (ver TODO figura)). Dessa forma, todas as interseções entre curvas ocorrem no meio de cada aresta: as curvas relativas ao vértices extremos da aresta se cruzam duas vezes.