Geodesic
On Planar Supports for Hypergraphs
Journal of Graph Algorithms and Applications, Tome 15 (2011) no. 4, pp. 533-549.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

A graph G is a support for a hypergraph H = (V, S) if the vertices of G correspond to the vertices of H such that for each hyperedge Si ∈ S the subgraph of G induced by Si is connected. G is a planar support if it is a support and planar. Johnson and Pollak [] proved that it is NP-complete to decide if a given hypergraph has a planar support. In contrast, there are lienar time algorithms to test whether a given hypergraph has a planar support that is a path, cycle, or tree. In this paper we present an efficient algorithm which tests in polynomial time if a given hypergraph has a planar support that is a tree where the maximal degree of each vertex is bounded. Our algorithm is constructive and computes a support if it exists. Furthermore, we prove that it is already NP-hard to decide if a hypergraph has a 2-outerplanar support.
DOI : 10.7155/jgaa.00237
Keywords: hypergraph, subdivision drawing, planar support 
@article{JGAA_2011_15_4_a2,
     author = {Kevin Buchin and Marc van Kreveld and Henk Meijer and Bettina Speckmann and Kevin Verbeek},
     title = {On {Planar} {Supports} for {Hypergraphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {533--549},
     publisher = {mathdoc},
     volume = {15},
     number = {4},
     year = {2011},
     doi = {10.7155/jgaa.00237},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00237/}
}
TY  - JOUR
AU  - Kevin Buchin
AU  - Marc van Kreveld
AU  - Henk Meijer
AU  - Bettina Speckmann
AU  - Kevin Verbeek
TI  - On Planar Supports for Hypergraphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2011
SP  - 533
EP  - 549
VL  - 15
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00237/
DO  - 10.7155/jgaa.00237
LA  - en
ID  - JGAA_2011_15_4_a2
ER  - 
%0 Journal Article
%A Kevin Buchin
%A Marc van Kreveld
%A Henk Meijer
%A Bettina Speckmann
%A Kevin Verbeek
%T On Planar Supports for Hypergraphs
%J Journal of Graph Algorithms and Applications
%D 2011
%P 533-549
%V 15
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00237/
%R 10.7155/jgaa.00237
%G en
%F JGAA_2011_15_4_a2
Kevin Buchin; Marc van Kreveld; Henk Meijer; Bettina Speckmann; Kevin Verbeek. On Planar Supports for Hypergraphs. Journal of Graph Algorithms and Applications, Tome 15 (2011) no. 4, pp. 533-549. doi : 10.7155/jgaa.00237. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00237/

Cité par Sources :