Return to search

Problemas computacionais em teoria topológica dos grafos / Computational problems in topological graph theory

Este trabalho tem por objetivo estudar os problemas computacionais que surgem ao se relacionar grafos com superfícies bidimensionais, dando especial atenção aos problemas do número de cruzamentos mínimo no plano (CROSSING NUMBER) e a problemas relacionados ao desenho de grafos em livros. Apresentamos uma redução do problema MULTICUT para CROSSING NUMBER, além de um resultado de complexidade em grafos de comparabilidade baseado em um resultado conhecido para desenhos em livros. / The objective of this text is to study computational problems that emerge from the relation between graphs and bidimensional surfaces, giving special attention to the crossing number problem and graph drawings on books. We present a reduction from MULTICUT to CROSSING NUMBER, in addition to a complexity result on comparability graphs based on a known result about drawings on books.

Identiferoai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-27012016-090223
Date11 December 2015
CreatorsRafael Veiga Pocai
ContributorsCarlos Eduardo Ferreira, Luerbio Faria, César Israel Hernández Vélez
PublisherUniversidade de São Paulo, Ciência da Computação, USP, BR
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Sourcereponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0022 seconds