Representações retangulares de grafos planares (2012)
- Authors:
- Autor USP: ASSUNÇÃO, GUILHERME PUGLIA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: OTIMIZAÇÃO COMBINATÓRIA
- Agências de fomento:
- 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
-
ABNT
ASSUNÇÃO, Guilherme Puglia. Representações retangulares de grafos planares. 2012. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2012. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07052012-164622. Acesso em: 17 nov. 2024. -
APA
Assunção, G. P. (2012). Representações retangulares de grafos planares (Dissertação (Mestrado). 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. Representações retangulares de grafos planares [Internet]. 2012 ;[citado 2024 nov. 17 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07052012-164622 -
Vancouver
Assunção GP. Representações retangulares de grafos planares [Internet]. 2012 ;[citado 2024 nov. 17 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07052012-164622
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
