Representing Hypergraphs by Point-Line Incidences.
Saved in:
| Title: | Representing Hypergraphs by Point-Line Incidences. |
|---|---|
| Authors: | Dobler, Alexander1, Mondal, Debajyoti2, Kobourov, Stephen3, Nöllenburg, Martin1 |
| Source: | Discrete Mathematics & Theoretical Computer Science (DMTCS). 2026, Vol. 28 Issue 3, p1-24. 24p. |
| Subjects: | Hypergraphs, Polynomial time algorithms, Computational complexity, Incidence geometry, Intersection graph theory |
| Abstract: | 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 ∃ℝ-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. [ABSTRACT FROM AUTHOR] |
| Copyright of Discrete Mathematics & Theoretical Computer Science (DMTCS) is the property of Discrete Mathematics & Theoretical Computer Science DMTCS and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
