Recovering Graphs from Their Witness Unit Square Representation
Publication date
2025-11-26
Authors
Löffler, Maarten
Staals, F.
Terziadis, Soeren
Editors
Dujmovic, Vida
Montecchiani, Fabrizio
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
cc_by
Abstract
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.
Keywords
geometric intersection graphs, output sensitive algorithm, proximity graphs, range searching, unit square intersection graph, witness representation, Software
Citation
Löffler, M, Staals, F & Terziadis, S 2025, Recovering Graphs from Their Witness Unit Square Representation. in V Dujmovic & F Montecchiani (eds), 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025., 44, Leibniz International Proceedings in Informatics, LIPIcs, vol. 357, Dagstuhl Publishing, 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025, Norrkoping, Sweden, 24/09/25. https://doi.org/10.4230/LIPIcs.GD.2025.44, conference