On a conjecture concerning helly circle graphs
AUTOR(ES)
Durán, Guillermo, Gravano, Agustín, Groshaus, Marina, Protti, Fábio, Szwarcfiter, Jayme L.
FONTE
Pesquisa Operacional
DATA DE PUBLICAÇÃO
2003-01
RESUMO
Dizemos que G é um grafo e-circular se existe uma bijeção entre seus vértices e retas no plano cartesiano de forma que dois vértices são adjacentes em G se e somente se as retas correspondentes se intersectam dentro do círculo de raio unitário centrado na origem. Esta definição sugere um método para decidir se um dado grafo G é um grafo e-circular, construindo convenientemente um sistema S de equações e inequações que representa a estrutura de G, de tal modo que G é um grafo e-circular se e somente se S tem solução. Em realidade, grafos e-circulares são exatamente os grafos circulares (grafos de interseção de cordas em um círculo), e portanto este método fornece um modo analítico de reconhecimento de grafos circulares. Um grafo G é circular Helly se G é um grafo circular e existe um modelo de cordas de G tal que em todo grupo de três cordas mutuamente intersectantes existe um ponto comum a todas elas. Uma conjectura de Durán (2000) afirma que G é um grafo circular Helly se e somente se G é um grafo circular e não contém diamantes induzidos (um diamante é um grafo formado por quatro vértices e cinco arestas). Muitas tentativas infrutíferas - baseadas principalmente em abordagens combinatórias e geométricas - foram realizadas para tentar validar a conjectura. Neste trabalho, utilizamos as idéias subjacentes à definição de grafos e-circulares e reformulamos a conjectura em termos de uma equivalência entre dois sistemas de equações e inequações, fornecendo uma nova ferramenta analítica para tratá-la.
ASSUNTO(S)
grafo circular grafo circular helly
