Grafos bi-arco-circulares

Abstract

Resumo: Um modelo bi-arco-circular é uma tripla (C; I; E) onde C é um circulo, e I;E são duas famílias de arcos sobre C. O grafo correspondente ao modelo (C; I;E) é o grafo tal que para cada arco de I [ E existe um vértice, e dois vértices são vizinhos se e somente se os seus arcos correspondentes intersectam e um deles está em I e outro em E. Um grafo é dito bi-arco-circular se é o grafo correspondente a algum modelo bi-arco-circular. A classe dos grafos bi-arco-circulares foi até hoje pouco estudada, e não se conhece a complexidade computacional do seu reconhecimento. O estudo dessa classe é de interesse devido à mesma ser uma generalização intuitiva do conceito de grafos de bi-intervalo e uma adaptação bipartida do conceito de grafos arco-circulares, e pelas aplicações práticas que podem vir a emergir ao se estudar a estrutura das bicliques contidas em grafos da classe. Nesta dissertação, estudamos grafos bi-arco-circulares com um foco em descobrir propriedades estruturais da classe e de suas subclasses, com a intenção de explicitar resultados que possam ser úteis na descoberta de novas caracterizações. Além disso, também estudamos brevemente a relação da classe com outras classes semelhantes, bem como as subclasses bi-arco-circulares própria e Helly. Palavras-chave: grafos bi-arco-circulares. grafos bi-arco-circulares Helly. grafos biintervalo. grafos bipartidos. grafos coroa. complexidade de reconhecimento.

Abstract: A bi-circular-arc model is a triple (C; I;E) in which C is a circle, and I;E are two families of arcs over C. The corresponding graph of (C; I;E) is a graph in which for each arc in I [ E there is a vertex, and a pair of vertices are connected by an edge if and only if the arcs they correspond to intersect and one of them is in I while the other is in E. A graph is said to be bi-circular-arc (also called circular arc bigraph in certain publications) if it is the corresponding graph of one or more bi-circular-arc models. The bi-circular-arc class of graphs is yet to be extensively studied, and the computational complexity of its recognition is unknown. Studying this class is of some interest, mostly due to it being an intuitive generalization of the concept of interval bigraphs and a bipartite adaptation of circular-arc graphs, as well as the potential practical applications that may emerge from the study of the biclique structures of graphs in the class. In this dissertation, we study bi-circular-arc graphs with a focus on the structural properties of the class and a handful of it subclasses, aiming to display results that may be useful in the discovery of new characterizations in the future. Other than that, we also briefly studied the relationship between the class and other similarly defined classes, as well as proper and Helly bi-circular-arc subclasses. Key-words: bi-circular-arc graphs. circular-arc bigraphs. Helly bi-circular-arc graphs. interval bigraphs. bipartite graphs. crown graphs. complexity of recognition.