Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00237
On Planar Supports for Hypergraphs
Vol. 15, no. 4, pp. 533549, 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 S_{i} ∈ S the subgraph of G induced by S_{i} is connected. G is a planar support if it is a support and planar.
Johnson and Pollak [] proved that it is NPcomplete 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 NPhard to decide if a
hypergraph has a 2outerplanar support.

Submitted: January 2010.
Reviewed: January 2011.
Revised: June 2011.
Accepted: August 2011.
Final: September 2011.
Published: September 2011.
Communicated by
Michael Kaufmann

Journal Supporters
