2017/12/20 by Katharina Klost, Klost, Katharina, Wolfgang Mulzer +1
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #cs.CG #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1712.07559
11 pages, 5 figures
arxiv created 2017/12/20 · openalex publication_date 2017/12/20 · arxiv updated 2017/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Suppose we have an arrangement A of n geometric objects x1, …, xn ⊆ ℝ2 in the plane, with a distinguished point pi in each object xi. The generalized transmission graph of A has vertex set \x1, …, xn\ and a directed edge xixj if and only if pj ∈ xi. Generalized transmission graphs provide a generalized model of the connectivity in networks of directional antennas. The complexity class ∃ ℝ contains all problems that can be reduced in polynomial time to an existential sentence of the form ∃ x1, …, xn: ϕ(x1,…, xn), where x1,…, xn range over ℝ and ϕ is a propositional formula with signature (+, -, ⋅, 0, 1). The class ∃ ℝ aims to capture the complexity of the existential theory of the reals. It lies between NP and PSPACE. Many geometric decision problems, such as recognition of disk graphs and of intersection graphs of lines, are complete for ∃ ℝ. Continuing this line of research, we show that the recognition problem of generalized transmission graphs of line segments and of circular sectors is hard for ∃ ℝ. As far as we know, this constitutes the first such result for a class of directed graphs.