| Journal: | Pesquisa operacional |
| Database: | PERIÓDICA |
| System number: | 000313041 |
| ISSN: | 0101-7438 |
| Authors: | Durán, Guillermo1 Gravano, Agustín Groshaus, Marina Protti, Fabio2 Szwarcfiter, Jayme L |
| Institutions: | 1Universidad de Buenos Aires, Buenos Aires. Argentina 2Universidade Federal do Rio de Janeiro, Rio de Janeiro. Brasil |
| Year: | 2003 |
| Season: | Ene-Abr |
| Volumen: | 23 |
| Number: | 1 |
| Pages: | 221-229 |
| Country: | Brasil |
| Language: | Inglés |
| Document type: | Artículo |
| Approach: | Analítico, descriptivo |
| English abstract | We say that G is an e-circle graph if there is a bijection between its vertices and straight lines on the cartesian plane such that two vertices are adjacent in G if and only if the corresponding lines intersect inside the circle of radius one. This definition suggests a method for deciding whether a given graph G is an e-circle graph, by constructing a convenient system S of equations and inequations which represents the structure of G, in such a way that G is an e-circle graph if and only if S has a solution. In fact, e-circle graphs are exactly the circle graphs (intersection graphs of chords in a circle), and thus this method provides an analytic way for recognizing circle graphs. A graph G is a Helly circle graph if G is a circle graph and there exists a model of G by chords such that every three pairwise intersecting chords intersect at the same point. A conjecture by Durán (2000) states that G is a Helly circle graph if and only if G is a circle graph and contains no induced diamonds (a diamond is a graph formed by four vertices and five edges). Many unsuccessful efforts - mainly based on combinatorial and geometrical approaches - have been done in order to validate this conjecture. In this work, we utilize the ideas behind the definition of e-circle graphs and restate this conjecture in terms of an equivalence between two systems of equations and inequations, providing a new, analytic tool to deal with it |
| Portuguese abstract | 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 |
| Disciplines: | Matemáticas |
| Keyword: | Matemáticas aplicadas, Grafo circular Helly, Grafos circulares |
| Keyword: | Mathematics, Applied mathematics, Helly circle graph, Circle graphs |
| Full text: | Texto completo (Ver HTML) |
