Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has a
lso been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this paper, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consists of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing heuristics and exact SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several artificial and real-world data sets. Our experiments show that the heuristics produce solutions of comparable quality to the SAT models while running much faster.
A long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely
those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are $at$-outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness $k$ is NP-hard for any fixed $k ge 3$. We show that the problem, for any $k ge 5$, remains NP-hard for graphs whose domination number is $O(k)$, but it is FPT in the vertex cover number.
In this paper, we study the online Euclidean spanners problem for points in $mathbb{R}^d$. Suppose we are given a sequence of $n$ points $(s_1,s_2,ldots, s_n)$ in $mathbb{R}^d$, where point $s_i$ is presented in step~$i$ for $i=1,ldots, n$. The objec
tive of an online algorithm is to maintain a geometric $t$-spanner on $S_i={s_1,ldots, s_i}$ for each step~$i$. First, we establish a lower bound of $Omega(varepsilon^{-1}log n / log varepsilon^{-1})$ for the competitive ratio of any online $(1+varepsilon)$-spanner algorithm, for a sequence of $n$ points in 1-dimension. We show that this bound is tight, and there is an online algorithm that can maintain a $(1+varepsilon)$-spanner with competitive ratio $O(varepsilon^{-1}log n / log varepsilon^{-1})$. Next, we design online algorithms for sequences of points in $mathbb{R}^d$, for any constant $dge 2$, under the $L_2$ norm. We show that previously known incremental algorithms achieve a competitive ratio $O(varepsilon^{-(d+1)}log n)$. However, if the algorithm is allowed to use additional points (Steiner points), then it is possible to substantially improve the competitive ratio in terms of $varepsilon$. We describe an online Steiner $(1+varepsilon)$-spanner algorithm with competitive ratio $O(varepsilon^{(1-d)/2} log n)$. As a counterpart, we show that the dependence on $n$ cannot be eliminated in dimensions $d ge 2$. In particular, we prove that any online spanner algorithm for a sequence of $n$ points in $mathbb{R}^d$ under the $L_2$ norm has competitive ratio $Omega(f(n))$, where $lim_{nrightarrow infty}f(n)=infty$. Finally, we provide improved lower bounds under the $L_1$ norm: $Omega(varepsilon^{-2}/log varepsilon^{-1})$ in the plane and $Omega(varepsilon^{-d})$ in $mathbb{R}^d$ for $dgeq 3$.
A realizer, commonly known as Schnyder woods, of a triangulation is a partition of its interior edges into three oriented rooted trees. A flip in a realizer is a local operation that transforms one realizer into another. Two types of flips in a reali
zer have been introduced: colored flips and cycle flips. A corresponding flip graph is defined for each of these two types of flips. The vertex sets are the realizers, and two realizers are adjacent if they can be transformed into each other by one flip. In this paper we study the relation between these two types of flips and their corresponding flip graphs. We show that a cycle flip can be obtained from linearly many colored flips. We also prove an upper bound of $O(n^2)$ on the diameter of the flip graph of realizers defined by colored flips. In addition, a data structure is given to dynamically maintain a realizer over a sequence of colored flips which supports queries, including getting a nodes barycentric coordinates, in $O(log n)$ time per flip or query.
A unit disk intersection representation (UDR) of a graph $G$ represents each vertex of $G$ as a unit disk in the plane, such that two disks intersect if and only if their vertices are adjacent in $G$. A UDR with interior-disjoint disks is called a un
it disk contact representation (UDC). We prove that it is NP-hard to decide if an outerplanar graph or an embedded tree admits a UDR. We further provide a linear-time decidable characterization of caterpillar graphs that admit a UDR. Finally we show that it can be decided in linear time if a lobster graph admits a weak UDC, which permits intersections between disks of non-adjacent vertices.
The problem of graph Reachability is to decide whether there is a path from one vertex to another in a given graph. In this paper, we study the Reachability problem on three distinct graph families - intersection graphs of Jordan regions, unit contac
t disk graphs (penny graphs), and chordal graphs. For each of these graph families, we present space-efficient algorithms for the Reachability problem. For intersection graphs of Jordan regions, we show how to obtain a good vertex separator in a space-efficient manner and use it to solve the Reachability in polynomial time and $O(m^{1/2}log n)$ space, where $n$ is the number of Jordan regions, and $m$ is the total number of crossings among the regions. We use a similar approach for chordal graphs and obtain a polynomial-time and $O(m^{1/2}log n)$ space algorithm, where $n$ and $m$ are the number of vertices and edges, respectively. However, we use a more involved technique for unit contact disk graphs (penny graphs) and obtain a better algorithm. We show that for every $epsilon> 0$, there exists a polynomial-time algorithm that can solve Reachability in an $n$ vertex directed penny graph, using $O(n^{1/4+epsilon})$ space. We note that the method used to solve penny graphs does not extend naturally to the class of geometric intersection graphs that include arbitrary size cliques.
Lightness is a fundamental parameter for Euclidean spanners; it is the ratio of the spanner weight to the weight of the minimum spanning tree of a finite set of points in $mathbb{R}^d$. In a recent breakthrough, Le and Solomon (2019) established the
precise dependencies on $varepsilon>0$ and $din mathbb{N}$ of the minimum lightness of $(1+varepsilon)$-spanners, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner $(1+varepsilon)$-spanners of lightness $O(varepsilon^{-1}logDelta)$ in the plane, where $Deltageq Omega(sqrt{n})$ is the emph{spread} of the point set, defined as the ratio between the maximum and minimum distance between a pair of points. They also constructed spanners of lightness $tilde{O}(varepsilon^{-(d+1)/2})$ in dimensions $dgeq 3$. Recently, Bhore and T{o}th (2020) established a lower bound of $Omega(varepsilon^{-d/2})$ for the lightness of Steiner $(1+varepsilon)$-spanners in $mathbb{R}^d$, for $dge 2$. The central open problem in this area is to close the gap between the lower and upper bounds in all dimensions $dgeq 2$. In this work, we show that for every finite set of points in the plane and every $varepsilon>0$, there exists a Euclidean Steiner $(1+varepsilon)$-spanner of lightness $O(varepsilon^{-1})$; this matches the lower bound for $d=2$. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis.
Lightness and sparsity are two natural parameters for Euclidean $(1+varepsilon)$-spanners. Classical results show that, when the dimension $din mathbb{N}$ and $varepsilon>0$ are constant, every set $S$ of $n$ points in $d$-space admits an $(1+varepsi
lon)$-spanners with $O(n)$ edges and weight proportional to that of the Euclidean MST of $S$. Tight bounds on the dependence on $varepsilon>0$ for constant $din mathbb{N}$ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a $(1+varepsilon)$-spanner. They gave upper bounds of $tilde{O}(varepsilon^{-(d+1)/2})$ for the minimum lightness in dimensions $dgeq 3$, and $tilde{O}(varepsilon^{-(d-1))/2})$ for the minimum sparsity in $d$-space for all $dgeq 1$. They obtained lower bounds only in the plane ($d=2$). Le and Solomon (ESA 2020) also constructed Steiner $(1+varepsilon)$-spanners of lightness $O(varepsilon^{-1}logDelta)$ in the plane, where $Deltain Omega(sqrt{n})$ is the emph{spread} of $S$, defined as the ratio between the maximum and minimum distance between a pair of points. In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner $(1+varepsilon)$-spanners. Using a new geometric analysis, we establish lower bounds of $Omega(varepsilon^{-d/2})$ for the lightness and $Omega(varepsilon^{-(d-1)/2})$ for the sparsity of such spanners in Euclidean $d$-space for all $dgeq 2$. We use the geometric insight from our lower bound analysis to construct Steiner $(1+varepsilon)$-spanners of lightness $O(varepsilon^{-1}log n)$ for $n$ points in Euclidean plane.
An $h$-queue layout of a graph $G$ consists of a linear order of its vertices and a partition of its edges into $h$ queues, such that no two independent edges of the same queue nest. The minimum $h$ such that $G$ admits an $h$-queue layout is the que
ue number of $G$. We present two fixed-parameter tractable algorithms that exploit structural properties of graphs to compute optimal queue layouts. As our first result, we show that deciding whether a graph $G$ has queue number $1$ and computing a corresponding layout is fixed-parameter tractable when parameterized by the treedepth of $G$. Our second result then uses a more restrictive parameter, the vertex cover number, to solve the problem for arbitrary $h$.
We present fully dynamic approximation algorithms for the Maximum Independent Set problem on several types of geometric objects: intervals on the real line, arbitrary axis-aligned squares in the plane and axis-aligned $d$-dimensional hypercubes. It
is known that a maximum independent set of a collection of $n$ intervals can be found in $O(nlog n)$ time, while it is already textsf{NP}-hard for a set of unit squares. Moreover, the problem is inapproximable on many important graph families, but admits a textsf{PTAS} for a set of arbitrary pseudo-disks. Therefore, a fundamental question in computational geometry is whether it is possible to maintain an approximate maximum independent set in a set of dynamic geometric objects, in truly sublinear time per insertion or deletion. In this work, we answer this question in the affirmative for intervals, squares and hypercubes. First, we show that for intervals a $(1+varepsilon)$-approximate maximum independent set can be maintained with logarithmic worst-case update time. This is achieved by maintaining a locally optimal solution using a constant number of constant-size exchanges per update. We then show how our interval structure can be used to design a data structure for maintaining an expected constant factor approximate maximum independent set of axis-aligned squares in the plane, with polylogarithmic amortized update time. Our approach generalizes to $d$-dimensional hypercubes, providing a $O(4^d)$-approximation with polylogarithmic update time. Those are the first approximation algorithms for any set of dynamic arbitrary size geometric objects; previous results required bounded size ratios to obtain polylogarithmic update time. Furthermore, it is known that our results for squares (and hypercubes) cannot be improved to a $(1+varepsilon)$-approximation with the same update time.
