On planar supports for hypergraphs

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

13 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
TitelGraph Drawing (17th International Symposium, GD'09, Chicago, IL, USA, September 22-25, 2009. Revised Papers)
RedacteurenD. Eppstein, E.R. Gansner
Plaats van productieBerlin
UitgeverijSpringer
Pagina's345-356
ISBN van geprinte versie978-3-642-11804-3
DOI's
StatusGepubliceerd - 2010

Publicatie series

NaamLecture Notes in Computer Science
Volume5849
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'On planar supports for hypergraphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit