10 citations · 15 across the 22 of their papers we have counts for
39 papers
Metric Planarity Testing is Hard
Anubhav Dhar, Debajyoti Kar, Sándor Kisfaludi-Bak +3
A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for…
Fast Thick-Thin Decomposition for Sparse Spanners on Hyperbolic Surfaces
Sándor Kisfaludi-Bak, Geert van Wordragen
We consider spanners for point sets lying in the hyperbolic plane or on a closed hyperbolic surface with the restriction that spanner edges are not allowed to cross. This is a natu…
Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes
Manuel Cáceres, Sándor Kisfaludi-Bak, Saeed Odak
The shifting technique of Hochbaum and Maass [J.ACM'85] produces PTASes with the fastest known running times for several -dimensional geometric prob…
Touring a Sequence of Orthogonal Polygons
Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist +3
We study the problem of computing a shortest tour that visits a sequence of polygons with a total number of vertices. A tour is an oriented curve such that…
Charting the Diameter Computation Landscape on Intersection Graphs in the Plane
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainl…
Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
Sándor Kisfaludi-Bak, Dániel Marx
We give approximation schemes for Subset TSP and Steiner Tree on unit disk graphs, and more generally, on intersection graphs of similarly sized connected fat (not necessarily conv…
Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case where truly subquadratic-time algorithms…
Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
Sándor Kisfaludi-Bak, Saeed Odak, Satyam Singh +1
We give an approximation scheme for the TSP in -dimensional hyperbolic space that has optimal dependence on under Gap-ETH. For any fixed dimension and fo…
Recognizing Subgraphs of Regular Tilings
Eliel Ingervo, Sándor Kisfaludi-Bak
For the -tiling graph is the (finite or infinite) planar graph where all faces are cycles of length and all vertices have degree . We give algor…
Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity
Sujoy Bhore, Sándor Kisfaludi-Bak, Lazar Milenković +3
A Euclidean noncrossing Steiner -spanner for a point set is a planar straight-line graph that, for any two points , contains a path whose…
Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
Mark de Berg, Sándor Kisfaludi-Bak
Recently it was shown that many classic graph problems -- Independent Set, Dominating Set, Hamiltonian Cycle, and more -- can be solved in subexponential time on unit-ball graphs.…
Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings
Sándor Kisfaludi-Bak, Tze-Yang Poon, Geert van Wordragen
Hyperbolic tilings are natural infinite planar graphs where each vertex has degree and each face has edges for some . We study the structure of sho…
Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
We give the first truly subquadratic time algorithm, with running time, for computing the diameter of an -vertex unit-disk graph, resolving a central open prob…
Realizing Metric Spaces with Convex Obstacles
Sándor Kisfaludi-Bak, Leonidas Theocharous
The presence of obstacles has a major impact on distance computation, motion planning, and visibility. While these problems are well studied in the plane, our understanding in thre…
Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces
Sándor Kisfaludi-Bak, Geert van Wordragen
We consider Steiner spanners in Euclidean and non-Euclidean geometries. In the Euclidean setting, a recent line of work initiated by Le and Solomon [FOCS'19] and further improved b…
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…
Separator Theorem and Algorithms for Planar Hyperbolic Graphs
Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen +2
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incompa…
A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space
Sándor Kisfaludi-Bak, Geert van Wordragen
We propose a data structure in -dimensional hyperbolic space that can be considered a natural counterpart to quadtrees in Euclidean spaces. Based on this data structure we propo…
Computing Smallest Convex Intersecting Polygons
Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak +1
A polygon C is an intersecting polygon for a set O of objects in the plane if C intersects each object in O, where the polygon includes its interior. We study the problem of comput…
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification
Esther Galby, Sandor Kisfaludi-Bak, Daniel Marx +1
In the Directed Steiner Network problem, the input is a directed graph G, a subset T of k vertices of G called the terminals, and a demand graph D on T. The task is to find a subgr…
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann +2
The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves in , it provides a ro…
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann +2
We initiate the study of diameter computation in geometric intersection graphs from the fine-grained complexity perspective. A geometric intersection graph is a graph whose vertice…
Computing list homomorphisms in geometric intersection graphs
Sándor Kisfaludi-Bak, Karolina Okrasa, Paweł Rzążewski
A homomorphism from a graph to a graph is an edge-preserving mapping from to . Let be a fixed graph with possible loops. In the list homomorphism problem,…
Clique-Based Separators for Geometric Intersection Graphs
Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh +1
Let be a set of objects in the plane and let be its intersection graph. A balanced clique-based separator of is a set consisting of cliques whose removal…