Recognizing Generalized Transmission Graphs of Line Segments and Circular Sectors

Suppose we have an arrangement $\mathcal{A}$ of $n$ geometric objects $x_1, \dots, x_n \subseteq $\mathbb{R}$^2$intheplane,withadistinguishedpoint$p_i$ineachobject$x_i$\mathrm{.}Thegeneralizedtransmissiongraphof$$\mathcal{A}$$hasvertexset${x_1, \dots, x_n}$andadirectededge$x_ix_j$ if and only if $p_j\in x_i$. Generalized transmission graphs provide a generalized model of the connectivity in networks of directional antennas. The complexity class $\mathrm{\exists }\mathbb{R}$ contains all problems that can be reduced in polynomial time to an existential sentence of the form $\exists x_1, \dots, x_n: \phi(x_1,\dots, x_n)$,where$x_1,\dots, x_n$rangeover$$\mathbb{R}$$and$\phi$isapropositionalformulawithsignature$(+, -, \cdot, 0, 1)$\mathrm{.}Theclass$\exists $\mathbb{R}$$ aims to capture the complexity of the existential theory of the reals. It lies between $\mathbf{N}\mathbf{P}$ and $\mathbf{P}\mathbf{S}\mathbf{P}\mathbf{A}\mathbf{C}\mathbf{E}$. Many geometric decision problems, such as recognition of disk graphs and of intersection graphs of lines, are complete for $\mathrm{\exists }\mathbb{R}$. 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 $\mathrm{\exists }\mathbb{R}$. As far as we know, this constitutes the first such result for a class of directed graphs.