2011 | OriginalPaper | Chapter
Blocks of Hypergraphs
Applied to Hypergraphs and Outerplanarity
Authors : Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, Arnaud Sallaberry
Published in: Combinatorial Algorithms
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A support of a hypergraph
H
is a graph with the same vertex set as
H
in which each hyperedge induces a connected subgraph. We show how to test in polynomial time whether a given hypergraph has a cactus support, i.e. a support that is a tree of edges and cycles. While it is
$\mathcal N\mathcal P$
-complete to decide whether a hypergraph has a 2-outerplanar support, we show how to test in polynomial time whether a hypergraph that is closed under intersections and differences has an outerplanar or a planar support. In all cases our algorithms yield a construction of the required support if it exists. The algorithms are based on a new definition of biconnected components in hypergraphs.