Back to Search
Start Over
Combinatorial Properties and Recognition of Unit Square Visibility Graphs
- Source :
- Maastricht University, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), 83, 30:1-30:15, Discrete & Computational Geometry, 69, 937-980. Springer Verlag
- Publication Year :
- 2023
- Publisher :
- Springer Science and Business Media LLC, 2023.
-
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.
- 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
Subjects
Details
- ISSN :
- 14320444 and 01795376
- Volume :
- 69
- Database :
- OpenAIRE
- Journal :
- Discrete & Computational Geometry
- Accession number :
- edsair.doi.dedup.....82bb39ee60e39da3f3ce27dd35b1bd2b