In computational geometry, one often meets graphs representing various kinds of geometric relations: intersection, containment, incidence, visibility, etc. While these graphs have natural geometric representations, these representations might sometimes be costly. We will consider biclique decompositions of such graphs, that allow compact representations using o(n) bits per vertex. In particular, we will describe compact representations of semialgebraic graphs - including segment and disk intersection graphs, semilinear graphs - including intersection graphs of rectilinear geometric objects, and various flavors of visibility graphs. We will argue that such representations are practical alternatives to the usual adjacency list representations. The presentation will involve classical and more recent results, including a joint work with Yelena Yuditsky (ESA 2025).

A matchstick graph is a planar graph drawn in the plane with straight edges of unit length. A natural generalization is the class of 1-planar unit distance graphs, where the planarity constraint is relaxed, and we allow each edge to be crossed by at most one other edge. Let $u_0(n)$ and $u_1(n)$ denote the maximum number of edges in a matchstick graph and a 1-planar unit distance graph on $n$ vertices, respectively. Although the exact value of $u_0(n)$ has been determined, the behavior of $u_1(n)$ remains a subject of active research. Recently, it was shown that $u_1(n)$ strictly exceeds $u_0(n)$ for all $n \ge 16135$. In this paper, we significantly improve this range of validity. Specifically, we prove that $u_1(n) > u_0(n)$ holds for every integer $n \ge 92$.

In this paper, we study the problem of constructing a (1/ε)-well-separated-pair-decomposition (WSPD) for a point set of size n in d-dimensional Euclidean space in the Massively Parallel Computation (MPC) model, where multiple machines work in parallel and communicate in synchronous rounds. We present an O(1)-round MPC algorithm that constructs a O(1/ε)-WSPD of size (1/ε)^{O(d)}. This improves the best-known algorithm [FOCS’93] for computing a WSPD which requires O(log n) rounds. As a consequence, the following problems can be solved in O(1) rounds in the MPC model: computing a (1 + ε)-spanner, a (1 − ε)-approximation of the diameter, the closest pair.

In a grounded string representation of a graph there is a horizontal line l and each vertex is represented as a simple curve below l with one end vertex on l such that two curves intersect if and only if the respective vertices are adjacent. A grounded string representation is a grounded L-mirrored-L-representation if each vertex is represented by a 1-bend orthogonal polyline. It is a grounded L-representation if in addition all curves are L-shaped. We show that every biconnected series-parallel graph without edges between the two vertices of a separation pair (i.e. transitive edges) admits a grounded L-mirrored-L-representation if and only if it admits a grounded string representation. Moreover, we can test in linear time whether such a representation exists. Note that there is a biconnected series-parallel graph without transitive edges that admits a grounded L-mirrored-L-representation, but no grounded L-representation.

We study the problem of computing for a point set P the well-separated pair decomposition with the minimum number of pairs. In this extended abstract, we present approximation algorithms for one-dimensional point sets, show that the problem is NP-hard for points in the plane, and also prove hardness of approximation in general.

Witness unit disk representations (wUDRs), are unit disk representations, where an additional set of points (witnesses) is given and two disks are considered not adjacent, if their overlap contains a witness. We prove upper and lower bounds on the number of witnesses required to represent graphs of different graph classes and provide an algorithm to compute the graph based on its wUDR.

Given a set of points $P$ in Euclidean space, a geometric $t$-spanner $G$ is a graph on $P$ such that for every pair of points, the shortest path in $G$ between those points is at most a factor $t$ longer than the Euclidean distance between those points. The value $t\geq 1$ is called the dilation of $G$. It was recently shown that there always exists an $O(n/k^{d/(d-1)})$-spanner of tree-width at most $k$ for sets of $n$ points $P \subset \mathbb{R}^d$. In this paper we strengthen this result qualitatively by extending it to the parameter path-width. We further argue that this result implies the same upper bound on the dilation for spanners of bounded cut-width and that a different previously known result on plane spanners of bounded tree-width implies a dilation bound for plane spanners of bounded clique-width. A directed $O(n/k^{d/(d-1)})$-spanner of directed tree-width $k$ can easily be obtained by replacing every edge of the undirected spanner by two opposing arcs. Complementing this, we show that the previously known lower bound of $\Omega(n/k^{d/(d-1)})$ on the dilation of tree-width $k$ bounded spanners extends to directed tree-width for directed geometric spanners.

In this paper we introduce star-based separators, which are separators consisting of a small number of stars. We prove that the intersection graph of any set of axis-aligned segments admits a star-based separator consisting of O(\sqrt{n}) stars. In fact, our result is more general, as it applies to any set of n pseudo-segments that is partitioned into c subsets such that the pseudo-segments in the same subset are pairwise disjoint. These results lead to an almost-exact distance oracle for such intersection graphs, which has O(n\sqrt{n}) storage and O(\sqrt{n}) query time, and that can report the hop-distance between any two query nodes in the intersection graph with an additive error of at most 2.

An undirected graph G=(P,E) is a k-edge fault-tolerant t-spanner, when for every subset E' of E of size |E'|=k, the shortest path in G\E' between any pair of points is at most a factor t longer than their shortest path in K(P)\E', where K(P) denotes the complete undirected graph on P. An oriented graph G is an oriented t-spanner on a point set P, when for every pair of points, the shortest closed walk in G containing those points is at most a factor t longer than their shortest cycle in K(P). We present the first results on plane fault-tolerant spanners: For n points in the Euclidean plane, the greedy triangulation is a 1-edge fault-tolerant O(n)-spanner for arbitrary point sets and an O(1)-spanner for convex point sets. Further, we complement previous results on plane oriented spanners for convex point sets by an orientation of the greedy triangulation that yields an oriented O(n)-spanner for arbitrary point sets.

We present a new family of hypergraphs with arbitrarily large uniformity and chromatic number. As an application, we give a new proof of a theorem of Chen, Pach, Szegedy, and Tardos. They showed that for any constants c,k>1, there exists a set P of points in the plane with the following property: for every coloring of P with c colors, there is an axis-parallel rectangle containing at least k points, all of the same color. Their original proof is probabilistic; we present an explicit construction. Moreover, in the case k=2, we show that one can even realize a graph with arbitrarily high girth and chromatic number using points and axis-parallel rectangles.

In this paper, we study dynamic disk intersection graphs. We show how to construct and dynamically maintain a (1 + ε)-spanner over the disk intersection graph of a dynamic set S of n disks. All disks in S have diameters in [4, Ψ], for some predefined and fixed Ψ. The (1 + ε)-spanner has size O(n ε⁻² log n log Ψ log(1/ε)). The space used to maintain the spanner is O(Ψ² ε⁻² n log n log² Ψ), and a disk can be inserted or deleted in O(Ψ² ε⁻² log⁴ n log² Ψ log²(1/ε)) time.

Polycubes are connected structures formed by unit cubes in three or more dimensions. No closed-form formula for the number of polycubes of size~$n$ is currently known, and counting them is a fundamental computational challenge in combinatorial geometry. We extend the Redelmeier-Dodds method for counting 3-dimensional polycubes and generalizes it higher dimensions. We explain the combinatorial principles underlying the correctness of the Redelmeier-Dodds's technique, extend it further by optimizing its recursive process, and report our counting of polycubes in~3 to~5 dimensions.

We study the Dynamic Level Planarity problem, where a directed graph $G$ with vertices assigned to horizontal lines called levels is subject to either insertions or deletions, and we at every step want to check whether it can be drawn planarly while respecting the leveling. We build upon a 2-SAT model of Level Planarity by Randerath et al. and construct an implication graph that reduces Level Planarity to a connectivity problem. By applying known results on dynamic connectivity, we obtain efficient algorithms that respectively solve the incremental and decremental case of Level Planarity. Especially, to the best of our knowledge, this is the first incremental algorithm for a constrained planarity variant and also the first decremental algorithm in the context of planarity.

For each value of $\rho > 1$, let $e(n,\rho)$ denote the maximum combined number of occurrences of the smallest and second smallest distances in a set of $n$ points in the plane, given that the smallest distance is $1$ and the second smallest distance is $\rho$. We determine the asymptotics of $e(n,\rho) = f(\rho)n-o(n)$ for all except six values of $\rho$. For these exceptional values, we determine upper and lower bounds that are quite close. The hardest exceptional value is the golden ratio $\varphi=\frac{1+\sqrt{5}}{2}$, where we give the bounds $53/13\leq f(\varphi)\leq 141/34$, % $45/11$ with the lower bound disproving a conjecture of Csizmadia. It turns out that for all except finitely many values of $\rho$, $f(\rho)\in\{3,7/2\}$.

In a set of three-dimensional planes, the \emph{k-lowest planes query} asks for the k-lowest planes pierced by a vertical line q. In this paper we describe a semi-dynamic insertion-only data structure that answers k-lowest planes queries in optimal O(log n+k) time and supports insertions in poly-logarithmic time.

For a planar set $P$ of $n$ points in general position, $h$ of those being extremal, let $t(P)$ denote the number of geometric triangulations $P$ admits. It is conjectured that for any $n$, $t(P)$ is minimized when $P$ is a so-called double circle configuration (which has half the points on the convex hull). We prove lower bounds on $t(P)$, expressed as functions of both $n$ and $h$. Our bounds improve asymptotically on the best known bounds for $h \leq 0.64\cdot n$. In particular we show that, for large enough $n$, \begin{itemize} \item if $h=O(1)$, then $t(P) \geq 2.72^n$, improving the bounds of $2.63^n$ by McCabe and Seidel (EWCG 2004) and $2.631^n$ by Aichholzer et al.\ (SoCG 2016); \item if $h\approx n/2$ (which is the regime of the family of configurations conjectured to minimize the number of triangulations) then $t(P) \geq 2.93^n$, improving the bound of $2.83^n$ by Sharir, Sheffer and Welzl (J.~Comb.~Theory.\ 2011); \item regardless of $h$, $t(P) \geq 2.637^n$, slightly improving the aforementioned bound of $2.631^n$ (which also holds regardless of $h$) by Aichholzer et al. \end{itemize}

We consider the problem of searching for special unknown rays in the half-plane and apply a generalized online cow-path like strategy with exponentially increasing $X$-distances with respect to a fixed basis $r$ and we move up with a fixed slope $\alpha$. We found values that guarantee a worst case ratio of at most $9.12725$ against the shortest offline path for detecting the ray. By special adjustments we attain the same ratio for a $1.5$D terrain search problem which motivates our problem definition. We can also slightly improve the lower bound to $9.06357$ shown in the full technical report.

Let $T$ be a tree and let $\Gamma'$ be a drawing of a subtree of $T$ such that $\Gamma'$ is a Euclidean minimum spanning tree (EMST) of its vertex set. We study the problem of extending $\Gamma'$ to a drawing of $T$ that is also an EMST of the full vertex set. We prove the problem to be NP-hard even for trees having maximum vertex degree three. We also show that for any $\epsilon > 0$ the drawing $\Gamma'$ can be extended to a $(1+\epsilon)$-EMST drawing of $T$, i.e., to a planar straight-line drawing in which the distance between any two vertices is at least $1/(1+\epsilon)$ times the length of the longest edge on the path connecting them. The computed drawings have polynomial edge-length ratio for trees with bounded vertex degree and can be constructed in linear time assuming the real RAM model of computation.

A graph drawing is k-matching-planar, if for each edge e the largest matching among the edges crossing e has size at most k. In a 2-layer drawing of a bipartite graph the vertices of one set of the bipartition are placed along a common horizontal line while the vertices of the other set are placed on another horizontal line. The edges are drawn as straightline segments in between. We prove that graphs with a 2-layer k-matching-planar drawing have pathwidth at most 2k+1 and describe, for each k≥1, a graph with a 2-layer k-matching-planar drawing and pathwidth $3\lfloor k/2\rfloor+1$.

We study the reconfiguration of plane spanning trees on point sets in the plane in convex position, where a reconfiguration step (flip) replaces one edge with another, yielding again a plane spanning tree. The flip distance between two trees is then the minimum number of flips needed to transform one tree into the other. We study structural properties of shortest flip sequences. The folklore happy edge conjecture suggests that any edge shared by both the initial and target tree is never flipped in a shortest flip sequence. The more recent parking edge conjecture, which would have implied the happy edge conjecture, states that there exist shortest flip sequences which use only edges of the start and target tree, and edges in the convex hull of the point set. Finally, the reparking conjecture states that no edge is flipped more than twice. Essentially all recent flip algorithms respect these three conjectures and the properties they imply. We study cases in which the latter two conjectures hold and disprove them for the general setting.

A graph is geometric 1-planar if it admits a straight-line drawing where each edge is crossed at most once. We provide the first systematic study of the parameterized complexity of recognizing geometric 1-planar graphs. By substantially extending a technique of Bannister, Cabello, and Eppstein, combined with Thomassen’s characterization of 1-planar embeddings that can be straightened, we show that the problem is fixed-parameter tractable when parameterized by treedepth. Furthermore, we obtain a kernel for Geometric 1-Planarity parameterized by the feedback edge number ℓ. As a by-product, we improve the best known kernel size of O((3ℓ)!) for 1-Planarity and k-Planarity under the same parameterization to O(ℓ · 8^ℓ). Our approach naturally extends to Geometric k-Planarity, yielding a kernelization under the same parameterization, albeit with a larger kernel. Complementing these results, we provide matching lower bounds: Geometric 1-Planarity remains NP-complete even for graphs of bounded pathwidth, bounded feedback vertex number, and bounded bandwidth.

We prove that finding a shortest flip sequence between two non-crossing spanning trees is NP-hard, already on point sets in convex position. The result still holds in the case when we restrict the flips to be compatible flips or rotations. Our proof relies on a tool called conflict graphs introduced by Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber [SODA 2025].

For a fixed graph class Pi, the goal of Pi-Modification is to transform an input graph G into a graph H in Pi using at most k modifications. Vertex and edge deletions are common operations, and their (parameterized) complexity for various Pi is well-studied. Classic graph modification operations such as edge deletion do not consider the geometric aspect of geometric graphs such as (unit) disk graphs, which led Fomin et al. [ITCS' 25] to initiate the study of disk scaling as a geometric graph modification operation: For a given radius r, each modified disk will be rescaled to radius r. We generalize their model by allowing rescaled disks to choose a radius within a given interval [rmin, rmax] and study the (parameterized) complexity (with respect to k) of the corresponding problem Pi-Scaling. We show that Pi-Scaling is in XP for graph classes Pi that can be recognized in polynomial time. Furthermore, we show that Pi-Scaling is NP-hard and FPT for cluster graphs.

We study the diameter of flip graphs $H_n$ whose node set is given by crossing-free drawings of perfect matchings. Specifically, we consider straight-line perfect matchings on a set of $2n$ vertices, with $n$ odd, that are equidistantly placed on the unit circle which is centered at the origin. A centered flip of a matching is the replacement of two edges $a$ and $b$ by two edges $c$, $d$ such that $a$,$b$,$c$,$d$ form a crossing-free quadrilateral that contains the origin. Milich, Mütze and Pergel showed a lower bound of $n-1$ and an upper bound of $11n-29$ for the diameter of $H_n$. We improve the lower bound to $\frac{3}{2}n-1$ and the upper bound to $6.5n-16$ for $n \geq 5$.

We study the complexity of Maximum k × k Square Packing, the problem of packing a maximum number of axis aligned k × k squares into a rectilinear polygon with n vertices on integer coordinates. We present a branching algorithm that runs in O(c_k^h poly(n)) time, where h is the amount of remaining space (unit squares not covered) in an optimal solution, and c_k is a constant with c_2=2 and converging to 1 as k goes to infinity. This runtime is fixed parameter tractable (FPT) in h and, as we show, in the length of the boundary of the polygon. Furthermore, we analyze a straightforward integer linear programming (ILP) formulation of the problem and show that our branching rule can be implemented in an ILP solver as a natural variable selection policy, and the reduction rules can be forced to hold in the fractional relaxation. This enables an ILP solver-based solution that runs in FPT time by bounding the maximum branching depth.

A unique sink orientation (USO) is an orientation of the edges of a polytope in which every face contains a unique source. For a product of simplices $\Delta_{m-1} \times \Delta_{n-1}$, Felsner, Gärtner and Tschirschnitz (2005) characterize USOs which are induced by linear functions as the USOs on a $(m \times n)$-grid that correspond to a two-colored arrangement of lines. We generalize some of their results to products $\Delta^1 \times \cdots \times \Delta^r$ of r simplices, USOs on r-dimensional grids and (r+1)-signotopes.

Multi-block grids are widely used for high-fidelity computational fluid dynamics (CFD) simulations in aerospace. However, constructing high-quality multi-block grids for complex geometries is still a largely manual, time-intensive process which relies on human expertise. This abstract reports on the collaborative efforts of the Royal Netherlands Aerospace Centre (NLR) and researchers from TU Eindhoven to automate a crucial step in the multi-block grid pipeline, namely the constructions of a so-called polycube segmentation of the input geometry.

The Erdős distinct distance problem and the unit distance problem are classical problems posed in 1946, which ask for the minimum number of distinct distances determined by n points in Euclidean space and the maximum number of pairs at a given distance that such a set can form, respectively. In this paper, we study a dual setting for hyperplane arrangements. First, we ask for the maximum number of d-simplices of unit volume, minimum volume, or maximum volume determined by n hyperplanes in d-space. Second, we study the largest integer D_d (n) such that any arrangement of n hyperplanes in general position in d-space contains a subset of size D_d (n) whose induced d-simplices all have distinct volumes.

Classical formulations of the Traveling Salesman Problem (TSP) search for a 1-dimensional cycle of edges. We propose a novel formulation that instead constructs a 2-dimensional surface, motivated by the geometric intuition that a tour is simply the boundary of this surface. This geometric shift maps undirected TSP to a node-cost / edge-profit constrained Group Steiner Tree Problem variant (cGSTP), where maximizing the net weight of this tree is equivalent to minimizing the tour length. We provide a Mixed-Integer Linear Program (MILP) that uses the Euler characteristic as a filter to enforce topological consistency, and demonstrate that this formulation offers structural advantages over standard edge-based Miller-Tucker-Zemlin (MTZ) models, particularly on sparse planar triangulations such as Delaunay.

We study approximations of polytopes in the standard model for computing polytopes using Minkowski sums and (convex hulls of) unions. Specifically, we study the ability to approximate a target polytope by polytopes of a given depth. Our main results imply that simplices can only be ``trivially approximated''. On the way, we obtain a characterization of simplices as the only ``outer additive'' convex bodies.

We study the patient zero problem in epidemic spreading processes in the independent cascade model and propose a geometric approach for source reconstruction. Using Johnson-Lindenstrauss projections, we embed the contact network into a low-dimensional Euclidean space and estimate the infection source as the node closest to the center of gravity of infected nodes. Simulations on synthetic networks, including Erdős-Rényi graphs, demonstrate that our estimator achieves meaningful reconstruction accuracy despite operating on compressed observations.

We consider a map defined by Kapranov and Voevodsky, mapping from the higher Bruhat orders to the higher Stasheff-Tamari orders on triangulations of the cyclic polytope. This map generalizes the quotient map given by the Silvester congruence, which is a map from the weak Bruhat order on permutations to the Tamari lattice. It is an open question whether this map is surjective. The surjectivity for triangulations of two and three dimensional cyclic polytopes was proven by Thomas in 2003. We prove that the map is surjective in the four dimensional case.