21 citations · 44 across the 25 of their papers we have counts for
6 papers · 1 filter
Hyperbolic Sphericity
Thomas Bläsius, Lennart Großkreutz, Jean-Pierre von der Heydt
The sphericity of a graph is the minimum dimension d such that the graph has an intersection representation of d-dimensional balls of equal radius. While sphericity has been studie…
Benchmarking and Engineering Data Structures for Spherical Range Queries
Thomas Bläsius, Jean-Pierre von der Heydt, Tobias Kempf +2
Spherical range queries are a fundamental primitive for working with spatial data. Many spatial data structures have been developed to answer these queries, but choosing the optima…
Structure and Independence in Hyperbolic Uniform Disk Graphs
Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak +2
We consider intersection graphs of disks of radius in the hyperbolic plane. Unlike the Euclidean setting, these graph classes are different for different values of , where v…
Recognizing Unit Disk Graphs in Hyperbolic Geometry is -Complete
Nicholas Bieker, Thomas Bläsius, Emil Dohse +1
A graph G is a (Euclidean) unit disk graph if it is the intersection graph of unit disks in the Euclidean plane . Recognizing them is known to be -…
Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model
Thomas Bläsius, Guido Brückner, Ignaz Rutter
We show that finding orthogonal grid-embeddings of plane graphs (planar with fixed combinatorial embedding) with the minimum number of bends in the so-called Kandinsky model (which…
Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings
Therese Biedl, Thomas Bläsius, Benjamin Niedermann +3
We present a simple and versatile formulation of grid-based graph representation problems as an integer linear program (ILP) and a corresponding SAT instance. In a grid-based repre…