Directed hypergraph planarity

Pesquisa Operacional

André Luiz Pires Guedes¹  Lilian Markenzon² 

[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