Grafos biclique de grafos de bi-intervalos e bi-arco-circulares

Abstract

Resumo: Um modelo bipartido de intervalos é uma bipartição de um número finito de intervalos da reta real. Um modelo bipartido arco-circular é uma bipartição de um número finito de arcos num círculo. Um grafo de bi-intervalos é um grafo de intersecção de um modelo bipartido de intervalos onde cada vértice corresponde a um intervalo e dois vértices compartilham uma aresta se, e somente se, ambos intervalos correspondentes intersectam e não pertencem à mesma parte. Da mesma maneira, um grafo bi-arco-circular é o grafo de intersecção de um modelo bipartido arco-circular onde os vértices correspondem a arcos e dois vértices compartilham uma aresta se, e somente se, ambos arcos correspondentes intersectam e não pertencem a mesma parte. O grafo biclique de um grafo G é o grafo de intersecção de todas bicliques maximais de G. Neste trabalho, apresentamos um algoritmo de varredura para encontrar todas bicliques maximais de um grafo de bi-intervalos a partir de um dado modelo bipartido de intervalos e propomos uma adaptação desse algoritmo para encontrar as bicliques maximais de um grafo bi-arco-circular. Nós também apresentamos algumas propriedades de bicliques de grafos de bi-intervalos quando vistas como conjuntos de intervalos de um modelo bipartido de intervalos. Introduzimos a noção de vãos e centros dessas bicliques e, baseado nessas propriedades estruturais, mostramos que todo grafo biclique de um grafo de bi-intervalos é um grafo de co-comparabilidade livre de K1,4. Palavras-chave: Grafos biclique, Grafos de bi-intervalos, Grafos bi-arco-circulares.

Abstract: A bipartite interval model is a bipartition of a finite number of intervals on the real line. A bipartite circular-arc model is a bipartition of a finite number of arcs on a circle. An interval bigraph is an intersection graph of a bipartite interval model in which each vertex corresponds to an interval and two vertices share an edge if and only if both corresponding intervals intersect and do not belong to the same part. Likewise, a circular-arc bigraph is the intersection graph of a bipartite circular-arc model where its vertices correspond to arcs and two vertices share an edge if and only if both corresponding arcs intersect and do not belong to the same part. The biclique graph of a graph G is the intersection graph of all maximal bicliques in G. In this work, we present a sweepline algorithm for finding all maximal bicliques of an interval bigraph from a given bipartite interval model and we propose an adaption of this algorithm for finding the maximal bicliques of a circular-arc bigraph. We also present some structural properties of bicliques of interval bigraphs when seen as sets of intervals from a bipartite interval model. We introduce the notion of gaps and centers of these bicliques and, based on these structral properties, we show that all biclique graphs of interval bigraphs are K1,4-free co-comparability graphs. Keywords: Biclique graphs, Interval bigraphs, Circular-arc bigraph.