Ver registro no DEDALUS
Exportar registro bibliográfico

Representações retangulares de grafos planares (2012)

  • Authors:
  • USP affiliated authors: ASSUNÇÃO, GUILHERME PUGLIA - IME
  • USP Schools: IME
  • Sigla do Departamento: MAC
  • Subjects: OTIMIZAÇÃO COMBINATÓRIA
  • Language: Português
  • Abstract: Uma representação retangular de um grafo plano G é uma representação de G, onde cada vértice é desenhado como um retângulo de modo que dois retângulos devem compartilhar algum segmento de seus lados se e somente se existe uma aresta em G entre os vértices correspondentes aos retângulos. Ainda, a representação de G deve formar um retângulo e não deve existir buracos, ou seja, toda região interna deve corresponder a algum vértice de G. Um desenho retangular de um grafo plano H é um desenho de H, onde todas as arestas são desenhadas como segmentos horizontais ou vérticais. Ainda, todas as faces internas são retângulos e as arestas que incidem na face externa também formam um retângulo. Nesta dissertação, apresentamos os principais trabalhos existentes na literatura para problemas associados à representação retangular. Também apresentamos resultados para problemas associados ao desenho retangular. Por fim, apresentamos o algoritmo que desenvolvemos para determinar as coordenadas dos vértices de um desenho retangular quando a orientação das arestas já foram determinadas.
  • Imprenta:
  • Data da defesa: 04.04.2012
  • Acesso online ao documento

    Acesso à fonte or search this record in

    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      ASSUNÇÃO, Guilherme Puglia; FERREIRA, Carlos Eduardo. Representações retangulares de grafos planares. 2012.Universidade de São Paulo, São Paulo, 2012. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07052012-164622 >.
    • APA

      Assunção, G. P., & Ferreira, C. E. (2012). Representações retangulares de grafos planares. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07052012-164622
    • NLM

      Assunção GP, Ferreira CE. Representações retangulares de grafos planares [Internet]. 2012 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07052012-164622
    • Vancouver

      Assunção GP, Ferreira CE. Representações retangulares de grafos planares [Internet]. 2012 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07052012-164622

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

    Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2019