Record link: 
http://hdl.handle.net/20.500.12708/220853
-
Title: 
Representing Hypergraphs by Point-Line Incidences
en
Citation: 
Dobler, A., Kobourov, S., Mondal, D., & Nöllenburg, M. (2025). Representing Hypergraphs by Point-Line Incidences. In SOFSEM 2025: Theory and Practice of Computer Science : 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Bratislava, Slovak Republic, January 20–23, 2025, Proceedings, Part I (pp. 241–254). Springer. https://doi.org/10.1007/978-3-031-82670-2_18
-
Publisher DOI: 
10.1007/978-3-031-82670-2_18
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Dobler, Alexander 
Kobourov, Stephen 
Mondal, Debajyoti 
Nöllenburg, Martin 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
SOFSEM 2025: Theory and Practice of Computer Science : 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Bratislava, Slovak Republic, January 20–23, 2025, Proceedings, Part I 
-
ISBN: 
978-3-031-82670-2
-
Volume: 
15538
-
DOI of the book: 
10.1007/978-3-031-82670-2
-
Date (published): 
7-Feb-2025
-
Event name: 
50th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2025) 
en
Event date: 
20-Jan-2025 - 23-Jan-2025
-
Event place: 
Bratislava, Slovakia
-
Number of Pages: 
14
-
Publisher: 
Springer, Cham
-
Peer reviewed: 
Yes
-
Keywords: 
ETR-hardness; Hypergraph visualization; Point-line incidence
en
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.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

92
checked on Nov 10, 2025

Google ScholarTM

Check