Pesquisa Operacional | |
Directed hypergraph planarity | |
André Luiz Pires Guedes1  Lilian Markenzon2  | |
[1] ,Universidade Federal do Paraná Departamento de Informática | |
关键词: directed hypergraphs; planarity; algorithms; hipergrafos direcionados; planaridade; algoritmos; | |
DOI : 10.1590/S0101-74382005000300005 | |
来源: SciELO | |
【 摘 要 】
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.
【 授权许可】
CC BY
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO202005130083849ZK.pdf | 218KB | download |