On Planar Supports for Hypergraphs

Buchin, Kevin and van Kreveld, Marc and Meijer, Henk and Verbeek, Kevin (2010) On Planar Supports for Hypergraphs. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009 , pp. 345-356(Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_33).

Full text not available from this repository.


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 [9] proved that it is NP-complete to decide if a given hypergraph has a planar support. In contrast, there are polynomial 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 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 3-outerplanar support.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-11805-0_33
Classifications: P Styles > P.420 Hyper
G Algorithms and Complexity > G.770 Planarity Testing
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1073

Actions (login required)

View Item View Item