Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00237 On Planar Supports for Hypergraphs Kevin Buchin , Marc van Kreveld , Henk Meijer , Bettina Speckmann , and Kevin Verbeek Vol. 15, no. 4, pp. 533-549, 2011. Regular paper Abstract 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.
|
Revised: June 2011. Reviewed: January 2011. Accepted: August 2011. Final: September 2011. Submitted: January 2010. Published: September 2011. Communicated by Michael Kaufmann |
Journal of Graph Algorithms and Applications |