𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hypergraph planarity and the complexity of drawing venn diagrams

✍ Scribed by D. S. Johnson; H. O. Pollak

Publisher
John Wiley and Sons
Year
1987
Tongue
English
Weight
821 KB
Volume
11
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

We introduce two new notions of planarity for hypergraphs based on dual generalizations of the standard Venn diagram. These definitions are illustrated by results concerning the existence and nonexistence of such diagrams for certain classes of hypergraphs. We conclude by showing that the general problem of determining whether such diagrams exist is N P-corn plete.

πŸ“œ SIMILAR VOLUMES

The complexity of the matching-cut probl
The complexity of the matching-cut problem for planar graphs and other graph classes
✍ Paul Bonsma πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 247 KB

## Abstract The Matching‐Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be ${\cal{NP}}$‐complete when restricted to graphs with maximum deg