Directed hypergraph planarity
AUTOR(ES)
Guedes, André Luiz Pires, Markenzon, Lilian
FONTE
Pesquisa Operacional
DATA DE PUBLICAÇÃO
2005-12
RESUMO
Hipergrafos direcionados são generalizações de digrafos, e são utilizados na modelagem de relações binárias entre subconjuntos de um dado conjunto. O problema da planaridade em hipergrafos foi estudado por Johnson e Pollak; neste trabalho estendemos o conceito de planaridade para hipergrafos direcionados. É noção conhecida que a planaridade de hipergrafos depende da planaridade de seu grafo subjacente. Entretanto, para hipergrafos direcionados, esta propriedade não pode ser aplicada e propomos uma nova abordagem que generaliza o conceito tradicional. Mostramos também que a complexidade de testar a planaridade de um hipergrafo direcionado é linear no tamanho do hipergrafo.
ASSUNTO(S)
hipergrafos direcionados planaridade algoritmos
