Representing Hypergraphs by Point-Line Incidences
This work provides complexity results and algorithmic insights for hypergraph visualization, which is relevant to graph drawing and computational geometry communities.
The paper studies hypergraph visualizations using point-line incidences, proving ∃ℝ-hardness for six of eight decision problem variants and providing polynomial-time algorithms for restricted settings. It also corrects a long-standing result by generalizing a counterexample when lines are allowed to have bends.
We consider hypergraph visualizations that represent vertices as points in the plane and hyperedges as curves passing through the points of their incident vertices. Specifically, we consider several different variants of this problem by (a) restricting the curves to be lines or line segments, (b) allowing two curves to cross if they do not share an element, or not; and (c) allowing two curves to overlap or not. We show $\exists\mathbb{R}$-hardness for six of the eight resulting decision problem variants and describe polynomial-time algorithms in some restricted settings. Lastly, we briefly touch on what happens if we allow the lines of the represented hyperedges to have bends - to this we generalize a counterexample to a long-standing result that was sometimes assumed to be correct.