Representing Hypergraphs by Point-Line Incidences
Discrete Mathematics & Theoretical Computer Science · 19.08.2026 · vol. 28:3 (Combinatorics)
DOI: 10.46298/dmtcs.15876 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 19.08.2026. Verfasst von Alexander Dobler und 3 weiteren Autor:innen.
Abstract (Originalsprache)
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. 24 pages, 12 figures
Zitieren
APA
Dobler, A., Kobourov, S., Mondal, D., & Nöllenburg, M. (2026). Representing Hypergraphs by Point-Line Incidences. Discrete Mathematics & Theoretical Computer Science, vol. 28:3(Combinatorics). https://doi.org/10.46298/dmtcs.15876
Vancouver
Dobler A, Kobourov S, Mondal D, Nöllenburg M. Representing Hypergraphs by Point-Line Incidences. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:3(Combinatorics). doi:10.46298/dmtcs.15876
BibTeX
@article{Dobler2026,
author = {Dobler, Alexander and Kobourov, Stephen and Mondal, Debajyoti and Nöllenburg, Martin},
title = {Representing Hypergraphs by Point-Line Incidences},
journal = {Discrete Mathematics & Theoretical Computer Science},
year = {2026},
volume = {vol. 28:3},
number = {Combinatorics},
doi = {10.46298/dmtcs.15876}
}
EUVIMED