@inproceedings{0dc56a8f685d45fcb8cae6d4e1960ec1,
title = "On planar supports for hypergraphs",
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 e 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.",
author = "K. Buchin and \{Kreveld, van\}, M.J. and H. Meijer and B. Speckmann and K.A.B. Verbeek",
year = "2010",
doi = "10.1007/978-3-642-11805-0\_33",
language = "English",
isbn = "978-3-642-11804-3",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "345--356",
editor = "D. Eppstein and E.R. Gansner",
booktitle = "Graph Drawing (17th International Symposium, GD'09, Chicago, IL, USA, September 22-25, 2009. Revised Papers)",
address = "Germany",
}