Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Blocks of Hypergraphs
Applied to Hypergraphs and Outerplanarity
verfasst von : Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, Arnaud Sallaberry
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.