@inproceedings{0c1d91ee52c34e0495ccbd1bf04c035f,
title = "Representing Hypergraphs by Point-Line Incidences",
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 ∃R-hardness for six of the eight resulting decision problem variants and describe polynomial-time algorithms in some restricted settings.",
keywords = "ETR-hardness, Hypergraph visualization, Point-line incidence",
author = "Alexander Dobler and Stephen Kobourov and Debajyoti Mondal and Martin N{\"o}llenburg",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025 ; Conference date: 20-01-2025 Through 23-01-2025",
year = "2025",
doi = "10.1007/978-3-031-82670-2_18",
language = "English (US)",
isbn = "9783031826696",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "241--254",
editor = "Rastislav Kr{\'a}lovi{\v c} and V{\v e}ra Kůrkov{\'a}",
booktitle = "SOFSEM 2025",
address = "Germany",
}