Recognizing generalized transmission graphs of line segments and circular sectors

DOI10.1007/978-3-319-77404-6_50MaRDI QIDQ2294728zbMATH OpenOpenAlexFDO

Authors Katharina Klost, Wolfgang Mulzer

Publication date 12 February 2020

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

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)

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.

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

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)