Circular arc bigraphs and their Helly subclass

Abstract

Resumo: Um grafo e arco-circular se e o grafo de intersecao de uma familia de arcos em um circulo. Grafos arco-circulares foram extensamente estudados na literatura. Os grafos bi-arco-circulares sao uma variante bipartida dos grafos arco-circulares. Um modelo bi-arco-circular e uma tripla (C, I, E) onde C e um circulo, e I, E sao familias arcos em C. O grafo correspondente a um modelo bi-arco-circular e montado ao se criar, para cada arco em I?E, um vertice, e arestas entre vertices sao criadas se os seus arcos correspondentes intersectam e estao em familias opostas (ou seja, um em I, outro em E). Um grafo bi-arco-circular e o grafo correspondente de um modelo bi-arco-circular. Em nosso trabalho, estudamos propriedades de varias subclasses de grafos bi-arco-circulares. Um modelo bi-arco-circular (C, I, E) e dito ser Helly se o par de familias I, E admite a propriedade bipartido-Helly. Apresentamos caracterizacoes por grafos proibidos de tres classes de grafos bi-arco-circulares Helly, incluindo grafos bi-arco-circulares Helly que admitem um ciclo sem cordas de comprimento maior que 4, grafos bi-intervalo Helly, e grafos bi-arco-circulares proprio-Helly. As caracterizacoes se baseiam em apresentar uma estrutura fundamental que todo grafo na classe verifica. Tambem apresentamos um algoritmo polinomial de reconhecimento para grafos bi-arco-circulares Helly sem vertices isolados, no qual aplicamos uma reducao para o problema de reconhecimento de grafos bi-arco-circulares Helly para grafos C6-free. Tambem estudamos as relacoes de contencao entre varias subclasses de grafos biarco- circulares, incluindo grafos bi-arco-circulares Helly, grafos bi-arco-circulares proprios, grafos bi-intervalo Helly, grafos circular convexo bipartidos, e a classe que definimos como bi-arco-circulares normais. Tambem introduzimos as subclasses de grafos bi-arco-circulares normais, cross-normais e cross-próprios, e exploramos brevemente suas relacoes de continencia. Um grafo biclique de um grafo e o grafo de intersecao de suas bicliques. Mostramos que os grafos biclique de grafos bi-arco-circulares Helly sao uma subclasse de grafos arco-circulares proprios, e que eles nao sao comparaveis aos grafos clique de grafos arco-circulares Helly. Porem, tambem mostramos que os grafos biclique de grafos bi-arco-circulares Helly C6-free sao subclasse dos grafos clique de grafos arco-circulares Helly. Apresentamos uma simples caracterizacao de grafos biclique de grafos bi-arco-circulares Helly nao bicordais, baseada nas mesmas estruturas fundamentais usada na caracterizacao por grafos proibidos, bem como uma caracterizacao para seus grafos de bicliques mutuamente contidas. Mostramos tambem que os grafos de bicliques mutuamente contidas de grafos bi-arco-circulares normal-proper-Helly sao arco-arco circulares proprios. Tambem apresentamos uma simples caracterizacao de uma subclasse de grafos biarco- circulares Helly bicordais, e limites superiores para o numero de bicliques em diferentes subclasses de grafos bi-arco-circulares. Palavras-chave: arco circular. Helly. grafo bipartido.

Abstract: A graph is a circular-arc graph if it is the intersection graph of a family of arcs on a circle. Circular-arc graphs have been extensively studied in the literature. Circular-arc bigraphs are a bipartite variant of circular-arc graphs. A bi-circular-arc model is a triple (C, I, E) where C is a circle and I, E are families of arcs over C. The corresponding graph of a bi-circular-arc model is constructed by creating, for each arc in I ? E, a vertex, and edges between vertices are added if their corresponding arcs intersect and are in opposing families (i.e. one is in I and the other is in E). A circular-arc bigraph is the corresponding graph of a bi-circular-arc model. In our work, we study the properties of several subclasses of circular-arc bigraphs. A bi-circular-arc model (C, I, E) is said to be Helly if the pair of families I, E admits the bipartite-Helly property. We provide forbidden graph characterizations for three subclasses of Helly circular-arc bigraphs, including Helly circular-arc bigraphs that admit a chordless cycle of length greater than 4, Helly interval bigraphs, and proper-Helly circular-arc bigraphs. The characterizations rely on presenting a fundamental structure that every graph in those classes verifies. We also show a polynomial-time recognition algorithm for Helly circular-arc bigraphs without isolated vertices, in which we rely on a reduction to the problem of recognizing Helly circular-arc graphs for input graphs that are C6-free. We also study the containment relations between several subclasses of circular-arc bigraphs, including Helly circular-arc bigraphs, proper circular-arc bigraphs, Helly interval bigraphs, circular convex bipartite graphs, and the class we define as normal circular-arc bigraphs. We also introduce the classes of normal, cross-normal, and cross-proper circular-arc bigraphs, and briefly explore their containment relations. A biclique graph of a graph is the intersection graph of its bicliques. We show that biclique graphs of Helly circular-arc bigraphs are a subclass of proper circular-arc graphs, and that they are not comparable to the clique graphs of Helly circular-arc graphs. However, we also show that the biclique graphs of C6-free Helly circular-arc bigraphs are a subclass of clique graphs of Helly circular-arc graphs. We provide a simple characterization of the biclique graphs of non-bichordal Helly circular-arc bigraphs, based on the very same fundamental structures used in their forbidden graph characterization, as well as one for their mutually contained biclique graphs. We also show that the mutually contained biclique graphs of normal-proper-Helly circular-arc bigraphs are proper circular-arc graphs. We also provide a simple characterization of a subclass of bichordal Helly circular-arc bigraphs, and upper bounds for the number of bicliques for different classes of circular-arc bigraphs. Keywords: circular arc. Helly. bipartite graph.