| Title: |
Recovering Graphs from Their Witness Unit Square Representation |
| Authors: |
Löffler, Maarten; Staals, Frank; Terziadis, Soeren; Sub Geometric Computing; Dujmovic, Vida; Montecchiani, Fabrizio |
| Publication Year: |
2025 |
| Subject Terms: |
geometric intersection graphs; output sensitive algorithm; proximity graphs; range searching; unit square intersection graph; witness representation; Software |
| Description: |
A wUSR of a graph G is a set of unit squares in the plane, one per vertex, if two vertices have an edge in G if their squares overlap and the overlap contains no witness. We present an output sensitive algorithm to compute a graph G based on its given witness unit square representation. |
| Document Type: |
book part |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
1868-8969 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/483528 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/483528 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.21AAA016 |
| Database: |
BASE |