On planar supports for hypergraphs

K. Buchin, M.J. Kreveld, van, H. Meijer, B. Speckmann, K.A.B. Verbeek

Research output: Contribution to journalArticleAcademicpeer-review

21 Citations (Scopus)
139 Downloads (Pure)

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 [11] 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 e¿cient 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.
Original languageEnglish
Pages (from-to)533-549
JournalJournal of Graph Algorithms and Applications
Volume15
Issue number4
Publication statusPublished - 2011

Fingerprint

Dive into the research topics of 'On planar supports for hypergraphs'. Together they form a unique fingerprint.

Cite this