2024/01/04 by Michael M. Hoffmann, Tillmann Miltzow, Hoffmann, Michael +5
Computer Science · Engineering · #Digital Image Processing Techniques #Computational Geometry and Mesh Generation #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2401.02172
Given a set of objects O in the plane, the corresponding intersection graph is defined as follows. Each object defines a vertex and an edge joins two vertices whenever the corresponding objects intersect. We study here the case of unit segments and polylines with exactly k bends. In the recognition problem, we are given a graph and want to decide whether the graph can be represented as an intersection graph of certain geometric objects. In previous work it was shown that various recognition problems are ∃ℝ-complete, leaving unit segments and polylines among the few remaining natural cases where the recognition complexity remained open. We show that recognition for both families of objects is ∃ℝ-complete.