notesum.ai

Published at November 21

Representing Hypergraphs by Point-Line Incidences

cs.CG

Released Date: November 21, 2024

Authors: Alexander Dobler¹, Stephen Kobourov², Debajyoti Mondal³, Martin Nöllenburg¹

Aff.: ¹TU Wien, Austria; ²TUM School of Computation, Germany; ³University of Saskatchewan, Canada

Arxiv: http://arxiv.org/abs/2411.13985v1

Refer to caption

	lines			line segments
	strict (= non-strict)			strict			non-strict
complexity	rank	max-deg	ref	rank	max-deg	ref	rank	max-deg	ref
$\exists\mathbb{R}$ -hard	$\geq 3$	n.b.	Thm 4.1	$\geq 3$	$\geq 10$	Thm 4.8	$\geq 3$	$\geq 6$	Thm 4.4
$\exists\mathbb{R}$ -hard	n.b.	$\geq 3$	Cor 4.3	$\geq 3$	$\geq 10$	Thm 4.8	$\geq 5$	$\geq 2$	Thm 4.6
Poly-time	$\leq 2$	n.b.	Obs 4.1	$\leq 2$	n.b.	Cor 4.10	$\leq 2$	n.b.	Cor 4.10
Poly-time	n.b.	$\leq 2$	Obs 4.1	n.b.	$\leq 2$	Cor 4.10	$\leq 3$	$\leq 2$	Thm 4.11