<div class="csl-bib-body">
<div class="csl-entry">Dobler, A., Kobourov, S., Mondal, D., & Nöllenburg, M. (2025). Representing Hypergraphs by Point-Line Incidences. In <i>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</i> (pp. 241–254). Springer. https://doi.org/10.1007/978-3-031-82670-2_18</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/220853
-
dc.description.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
dc.language.iso
en
-
dc.relation.ispartofseries
Lecture Notes in Computer Science (LNCS)
-
dc.subject
ETR-hardness
en
dc.subject
Hypergraph visualization
en
dc.subject
Point-line incidence
en
dc.title
Representing Hypergraphs by Point-Line Incidences
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
Technical University of Munich, Germany
-
dc.contributor.affiliation
University of Saskatchewan, Canada
-
dc.relation.isbn
978-3-031-82670-2
-
dc.relation.doi
10.1007/978-3-031-82670-2
-
dc.description.startpage
241
-
dc.description.endpage
254
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
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
-
tuw.container.volume
15538
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Springer
-
tuw.relation.publisherplace
Cham
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.1007/978-3-031-82670-2_18
-
dc.description.numberOfPages
14
-
tuw.author.orcid
0000-0002-0712-9726
-
tuw.author.orcid
0000-0002-7370-8697
-
tuw.author.orcid
0000-0003-0454-3937
-
tuw.event.name
50th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2025)
en
tuw.event.startdate
20-01-2025
-
tuw.event.enddate
23-01-2025
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Bratislava
-
tuw.event.country
SK
-
tuw.event.presenter
Dobler, Alexander
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.grantfulltext
none
-
item.openairetype
conference paper
-
item.fulltext
no Fulltext
-
item.languageiso639-1
en
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
University of Saskatchewan, Canada
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
