Academic Journals Database
Disseminating quality controlled scientific knowledge

Directed hypergraph planarity

Author(s): André Luiz Pires Guedes | Lilian Markenzon

Journal: Pesquisa Operacional
ISSN 0101-7438

Volume: 25;
Issue: 3;
Start page: 383;
Date: 2005;
Original page

Keywords: hipergrafos direcionados | planaridade | algoritmos | directed hypergraphs | planarity | algorithms

Directed hypergraphs are generalizations of digraphs and can be used to model binary relations among subsets of a given set. Planarity of hypergraphs was studied by Johnson and Pollak; in this paper we extend the planarity concept to directed hypergraphs. It is known that the planarity of a digraph relies on the planarity of its underlying graph. However, for directed hypergraphs, this property do not apply and we propose a new approach which generalizes the usual concept. We also show that the complexity of the recognition of a directed hypergraph as planar is linear on the size of the hypergraph.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.
Save time & money - Smart Internet Solutions      Why do you need a reservation system?