@MastersThesis{Cruz2018,
  author =       {Edmilson Pereira da Cruz},
  title =        {Grafos Biclique de Grafos de Bi-Intervalos e Bi-Arco-Circulares},
  school =       {PPGInf/UFPR},
  year =         {2018},
  month =        {junho},
  day =          {06},
  type =         {Mestrado},
  note =         {Orientador: André Luiz Pires Guedes e Marina Groshaus.
                 Banca:
                   Renato Carmo e
                   Sheila Morais de Almeida},
  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   $K_{1,4}$-free
                  co-comparability graphs.},
  url =          {https://hdl.handle.net/1884/59455},
  url_pdf =      {https://acervodigital.ufpr.br/bitstream/handle/1884/59455/R%20-%20D%20-%20EDMILSON%20PEREIRA%20DA%20CRUZ.pdf}
}

{"_id":"r3nbxPov8SsZD2p4a","bibbaseid":"dacruz-grafosbicliquedegrafosdebiintervalosebiarcocirculares-2018","downloads":4,"creationDate":"2018-06-08T01:16:43.122Z","title":"Grafos Biclique de Grafos de Bi-Intervalos e Bi-Arco-Circulares","author_short":["da Cruz, E. P."],"year":2018,"bibtype":"mastersthesis","biburl":"http://www.inf.ufpr.br/teoria/universal2016/orientacoes.bib","bibdata":{"bibtype":"mastersthesis","type":"Mestrado","author":[{"firstnames":["Edmilson","Pereira"],"propositions":["da"],"lastnames":["Cruz"],"suffixes":[]}],"title":"Grafos Biclique de Grafos de Bi-Intervalos e Bi-Arco-Circulares","school":"PPGInf/UFPR","year":"2018","month":"junho","day":"06","note":"Orientador: André Luiz Pires Guedes e Marina Groshaus. Banca: Renato Carmo e Sheila Morais de Almeida","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 $K_{1,4}$-free co-comparability graphs.","url":"https://hdl.handle.net/1884/59455","url_pdf":"https://acervodigital.ufpr.br/bitstream/handle/1884/59455/R%20-%20D%20-%20EDMILSON%20PEREIRA%20DA%20CRUZ.pdf","bibtex":"@MastersThesis{Cruz2018,\n author = {Edmilson Pereira da Cruz},\n title = {Grafos Biclique de Grafos de Bi-Intervalos e Bi-Arco-Circulares},\n school = {PPGInf/UFPR},\n year = {2018},\n month = {junho},\n day = {06},\n type = {Mestrado},\n note = {Orientador: André Luiz Pires Guedes e Marina Groshaus.\n Banca:\n Renato Carmo e\n Sheila Morais de Almeida},\n abstract = {A bipartite interval model is a bipartition of a\n finite number of intervals on the real line. A\n bipartite circular-arc model is a bipartition of a\n finite number of arcs on a circle. An interval\n bigraph is an intersection graph of a bipartite\n interval model in which each vertex corresponds to an\n interval and two vertices share an edge if and only if\n both corresponding intervals intersect and do not\n belong to the same part. Likewise, a circular-arc\n bigraph is the intersection graph of a bipartite\n circular-arc model where its vertices correspond to\n arcs and two vertices share an edge if and only if\n both corresponding arcs intersect and do not belong to\n the same part. The biclique graph of a graph $G$ is\n the intersection graph of all maximal bicliques in\n $G$. In this work, we present a sweepline algorithm\n for finding all maximal bicliques of an interval\n bigraph from a given bipartite interval model and we\n propose an adaption of this algorithm for finding the\n maximal bicliques of a circular-arc bigraph. We also\n present some structural properties of bicliques of\n interval bigraphs when seen as sets of intervals from\n a bipartite interval model. We introduce the notion\n of gaps and centers of these bicliques and, based on\n these structral properties, we show that all biclique\n graphs of interval bigraphs are $K_{1,4}$-free\n co-comparability graphs.},\n url = {https://hdl.handle.net/1884/59455},\n url_pdf = {https://acervodigital.ufpr.br/bitstream/handle/1884/59455/R%20-%20D%20-%20EDMILSON%20PEREIRA%20DA%20CRUZ.pdf}\n}\n\n\n\n","author_short":["da Cruz, E. P."],"key":"Cruz2018","id":"Cruz2018","bibbaseid":"dacruz-grafosbicliquedegrafosdebiintervalosebiarcocirculares-2018","role":"author","urls":{"Paper":"https://hdl.handle.net/1884/59455"," pdf":"https://acervodigital.ufpr.br/bitstream/handle/1884/59455/R%20-%20D%20-%20EDMILSON%20PEREIRA%20DA%20CRUZ.pdf"},"metadata":{"authorlinks":{}},"downloads":4},"search_terms":["grafos","biclique","grafos","intervalos","arco","circulares","da cruz"],"keywords":[],"authorIDs":[],"dataSources":["mCoYickddKEAfTgnb","zM4PZJhTBjBtW2gjb","Raee3ruyuhmzCg93Q"]}