1. Combinatorial Properties and Recognition of Unit Square Visibility Graphs
- Author
-
Casel, Katrin, Fernau, Henning, Grigoriev, Alexander, Schmid, Markus L., Whitesides, Sue, Larsen, Kim G., Bodlaender, Hans L., Raskin, Jean-Francois, QE Operations research, RS: GSBE ETBC, Data Analytics and Digitalisation, RS: GSBE Theme Data-Driven Decision-Making, and RS: FSE DACS Mathematics Centre Maastricht
- Subjects
Computational Geometry (cs.CG) ,FOS: Computer and information sciences ,c00 - Mathematical and Quantitative Methods: General ,Visibility graphs ,exact algorithms ,Graph recognition ,02 engineering and technology ,Computational Complexity (cs.CC) ,Theoretical Computer Science ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Geometric graph classes ,060201 languages & linguistics ,Visibility layout ,000 Computer science, knowledge, general works ,06 humanities and the arts ,Mathematical and Quantitative Methods: General ,NP-completeness ,Computer Science - Computational Complexity ,Computational Theory and Mathematics ,0602 languages and literature ,Computer Science ,Computer Science - Computational Geometry ,020201 artificial intelligence & image processing ,Geometry and Topology ,F.2.2 ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard, which settles an open question.
- Published
- 2023