The Complexity of Recognizing Geometric Hypergraphs
METADATA ONLY
Loading...
Author / Producer
Date
2023
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
As set systems, hypergraphs are omnipresent and have various representations ranging from Euler and Venn diagrams to contact representations. In a geometric representation of a hypergraph $H=(V,E)$, each vertex $v\in V$ is associated with a point $p_v\in \mathbb{R}^d$ and each hyperedge $e\in E$ is associated with a connected set $s_e\subset \mathbb{R}^d$ such that $\{p_v\mid v\in V\}\cap s_e=\{p_v\mid v\in e\}$ for all $e\in E$. We say that a given hypergraph $H$ is representable by some (infinite) family $F$ of sets in $\mathbb{R}^d$, if there exist $P\subset \mathbb{R}^d$ and $S \subseteq F$ such that $(P,S)$ is a geometric representation of $H$. For a family F, we define RECOGNITION(F) as the problem to determine if a given hypergraph is representable by F. It is known that the RECOGNITION problem is $\exists\mathbb{R}$-hard for halfspaces in $\mathbb{R}^d$. We study the families of translates of balls and ellipsoids in $\mathbb{R}^d$, as well as of other convex sets, and show that their RECOGNITION problems are also $\exists\mathbb{R}$-complete. This means that these recognition problems are equivalent to deciding whether a multivariate system of polynomial equations with integer coefficients has a real solution.
Permanent link
Publication status
published
External links
Book title
Graph Drawing and Network Visualization
Journal / series
Volume
14465
Pages / Article No.
163 - 179
Publisher
Springer
Event
31st International Symposium on Graph Drawing and Network Visualization (GD 2023)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Computational Geometry (cs.CG); FOS: Computer and information sciences; Hypergraph; Geometric hypergraph; Recognition; Computational complexity; Convex; Ball; Ellipsoid; Halfplane; Halfspace
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
08817 - Gärtner, Bernd (Tit.-Prof.) / Gärtner, Bernd (Tit.-Prof.)
Notes
Funding
Related publications and datasets
Is new version of: 10.48550/arXiv.2302.13597