Recognizing generalized transmission graphs of line segments and circular sectors

DOI10.1007/978-3-319-77404-6_50zbMATH Open1504.68260arXiv1712.07559OpenAlexW2963901236MaRDI QIDQ2294728FDOQ2294728

Authors: Katharina Klost, Wolfgang Mulzer 

Publication date: 12 February 2020

Abstract: Suppose we have an arrangement $mathcalA$ of $n$ geometric objects $x_1,dots,x_{n}subseteqmathbb{R}^2$ in the plane, with a distinguished point $p_i$ in each object $x_i$. The generalized transmission graph of $mathcalA$ has vertex set $x_1,dots,x_n$ and a directed edge $x_i{x}_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 $existsmathbbR$ 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$ range over $mathbbR$ and $phi$ is a propositional formula with signature $(+,-,cdot,0,1)$. The class $existsmathbbR$ aims to capture the complexity of the existential theory of the reals. It lies between $mathbfNP$ and $mathbfPSPACE$. Many geometric decision problems, such as recognition of disk graphs and of intersection graphs of lines, are complete for $existsmathbbR$. 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 $existsmathbbR$. As far as we know, this constitutes the first such result for a class of directed graphs.

Full work available at URL: https://arxiv.org/abs/1712.07559

Recommendations

• Publication:4724662
• Recognition of Circle Graphs
• Linear-time recognition of circular-arc graphs
• scientific article; zbMATH DE number 5130726
• A simpler linear-time recognition of circular-arc graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• Line-Polar Graphs: Characterization and Recognition
• Recognizing generalized Sierpiński graphs
• scientific article; zbMATH DE number 3859180
• Recognizing circle graphs in polynomial time

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

This page was built for publication: Recognizing generalized transmission graphs of line segments and circular sectors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294728)