2005-12
Directed hypergraph planarity
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 complexi...
Texto completo-
Assuntos:
- hipergrafos direcionados
- planaridade
- algoritmos