ABSTRACT. In information visualization, the position of symbols often encodes associated data values. When visualizing data elements with both a numerical and a categorical dimension, positioning in the categorical axis admits some flexibility. This flexibility can be exploited to reduce symbol overlap, and thereby increase legibility. In this paper we initialize the algorithmic study of optimizing symbol legibility via a limited displacement of the symbols.

Specifically, we consider unit square symbols that need to be placed at specified y-coordinates. We optimize the drawing order of the symbols as well as their x-displacement, constrained within a rectangular container, to maximize the minimum visible perimeter over all squares. If the container has width and height at most 2, there is a point that stabs all squares. In this case, we prove that a staircase layout is arbitrarily close to optimality and can be computed in O(n log n) time. If the width is at most 2, there is a vertical line that stabs all squares, and in this case, we give a 2-approximation algorithm (assuming fixed container height) that runs in O(n log n) time. As a minimum visible perimeter of 2 is always trivially achievable, we measure this approximation with respect to the visible perimeter exceeding 2. We show that, despite its simplicity, the algorithm gives asymptotically optimal results for certain instances.

ABSTRACT. Given a geometric domain $P$, visibility-based search problems seek routes for one or more mobile agents (``watchmen'') to move within $P$ in order to be able to see a portion (or all) of $P$, while optimizing objectives, such as the length(s) of the route(s), the size (e.g., area or volume) of the portion seen, the probability of detecting a target distributed within $P$ according to a prior distribution, etc. The classic watchman route problem seeks a shortest route for an observer, with omnidirectional vision, to see all of $P$. In this paper we study bicriteria optimization problems for a single mobile agent within a polygonal domain $P$ in the plane, with the criteria of route length and area seen. Specifically, we address the problem of computing a minimum length route that sees at least a specified area of $P$ (minimum length, for a given area quota). We also study the problem of computing a length-constrained route that sees as much area as possible. We provide hardness results and approximation algorithms. In particular, for a simple polygon $P$ we provide the first fully polynomial-time approximation scheme for the problem of computing a shortest route seeing an area quota, as well as a (slightly more efficient) polynomial dual approximation. We also consider polygonal domains $P$ (with holes) and the special case of a planar domain consisting of a union of lines. Our results yield the first approximation algorithms for computing a time-optimal search route in $P$ to guarantee some specified probability of detection of a static target within $P$, randomly distributed in $P$ according to a given prior distribution.

ABSTRACT. We introduce and analyze a model for self-reconfigurable robots made up of unit-cube modules. Compared to past models, our model aims to newly capture two important practical aspects of real-world robots. First, modules often do not occupy an exact unit cube, but rather have features like bumps extending outside the allotted space so that modules can interlock. Thus, for example, our model forbids modules from squeezing in between two other modules that are one unit distance apart. Second, our model captures the practical scenario of many passive modules assembled by a single robot, instead of requiring all modules to be able to move on their own.

We prove two universality results. First, with a supply of auxiliary modules, we show that any connected polycube structure can be constructed by a carefully aligned plane sweep. Second, without additional modules, we show how to construct any structure for which a natural notion of external feature size is at least a constant; this property largely consolidates forbidden-pattern properties used in previous works on reconfigurable modular robots.

ABSTRACT. Given a set P of n points, with diameter ∆, and a parameter δ in (0, 1), it is known that there is a partition of P into sets P1,...,Pt, each of size O(1/δ^2), such that their convex-hulls all intersect a common ball of radius δ∆. We prove that a random partition, with a simple alteration step, yields the desired partition, resulting in a (randomized) linear time algorithm. We also provide a deterministic algorithm with running time O(dn log n). Previous proofs were either existential (i.e., at least exponential time), or required much bigger sets. In addition, the algorithm and its proof of correctness are significantly simpler than previous work, and the constants are slightly better.

We also include a number of applications and extensions using the same central ideas. For example, we provide a linear time algorithm for computing a “fuzzy” centerpoint, and prove a no-dimensional weak ε-net theorem with an improved constant.

ABSTRACT. TBA TBA TBA

ABSTRACT. In the \Minimum Sum Coloring with Bundles problem, we are given an undirected graph G = (V, E) and (not necessarily disjoint) bundles V_1, V_2, ..., V_p \subseteq V with associated weights w_1, \ldots, w_p \geq 0. The goal is to give a proper coloring of G using positive integers to minimize the weighted average/total completion time of all bundles, where the completion time of a bundle is the maximum integer assigned to one of its nodes. This is a common generalization of the classic \Minimum Sum Coloring problem, i.e. when all bundles are singleton nodes, and the classic Chromatic Number problem, i.e. the only bundle is all of V.

Despite its generality as an extension of Minimum Sum Coloring, only very special cases have been studied with the most common being the line graph L(H) of a graph H (also known as Coflow Scheduling). We provide the first constant-factor approximation in perfect graphs and, more generally, graphs whose chromatic number is within a constant factor of the maximum clique size in any induced subgraph. For example, we obtain constant-factor approximations for graphs that are well-studied in minimum sum coloring such as interval graphs and unit disk graphs.

Next, we extend our results to get constant-factor approximations for a general model where the bundles are disjoint (i.e. can be thought of as jobs brought by the corresponding client) and we are only permitted to color/schedule a bounded number of jobs from each bundle at any given time. Specifically, we get constant-factor approximations for this model if the nodes of graph G have an ordering $v_1, v_2, \ldots, v_n$ such that the {\em left neighborhood} N_\ell(v_i) := \{v_j : j < i, v_iv_j \in E\} can be covered by O(1) cliques. For example, this applies to chordal graphs, unit disc graphs, and circular arc graphs.

ABSTRACT. The capacitated tree cover problem with edge loads is a variant of the tree cover problem, where we are given facility opening costs, edge costs and loads, as well as vertex loads. We try to find a tree cover of minimum cost such that the total edge and vertex load of each tree does not exceed a given bound. We present an O(m log n) 3-approximation algorithm for this problem.

This is achieved by starting with a certain LP formulation. We give a combinatorial algorithm that solves the LP optimally in time O(m log n). Then, we show that a linear time rounding and splitting technique leads to an integral solution that costs at most 3 times as much as the LP solution. Finally, we prove that the integrality gap of the LP is 3, which shows that we can not improve the rounding step in general.

ABSTRACT. In this paper, we show that computing canonical labelings of graphs of bounded rank-width is in TC^2. Our approach builds on the framework of Köbler & Verbitsky (CSR 2008), who established the analogous result for graphs of bounded treewidth. Here, we use the framework of Grohe & Neuen (ACM Trans. Comput. Log., 2023) to enumerate separators via split-pairs and flip functions. Nonetheless, these separators may not in general split the graph into connected components of sufficiently small size. This presents an obstacle for controlling the depth of our circuit. To overcome this obstacle, we leverage the balanced rank decomposition of width $\leq 2k$ and height $O(\log n)$ of Courcelle & Kant\'e (WG 2007), which allows us to utilize an idea from Wagner (CSR 2011) of tracking the depth of the recursion in our computation.

Furthermore, after splitting the graph into connected components, it is necessary to decide isomorphism of said components in TC^1. To this end, we extend the work of Grohe & Neuen (ibid) to show that the $(6k+3)$-dimensional Weisfeiler--Leman (WL) algorithm identifies graphs of rank-width $k$ using only $O(\log n)$ rounds. Prior to this paper, isomorphism testing for graphs of bounded rank-width was not known to be in NC.

ABSTRACT. For some time, it has been known that the model checking problem for first-order formulas is fixed-parameter tractable on nowhere dense graph classes, so we shall ask in which direction there is space for improvements. One of the possible directions is to go beyond first-order formulas: Augmenting first-order logic with general counting quantifiers increases the expressiveness by far, but makes the model checking problem hard even on graphs of bounded tree-depth. The picture is different if we allow only ``simple'' -- but arbitrarily nested -- counting terms of the form $#y φ(x_1...x_k,y)>N$. Even then, only approximate model-checking is possible on graph classes of bounded expansion. Here, the largest known logic fragment, on which exact model-checking is still fpt, consists of formulas of the form $∃x_1...∃x_k #y φ(x_1...x_k,y)>N$, where $φ(x_1...x_k,y)$ is a first-order formula without counting terms. An example of a problem that can be expressed in this way is partial dominating set: Are there $k$ vertices that dominate at least a given number of vertices in the graph? The complexity of the same problem is open if you replace \emph{at least} with **exactly**. Likewise, the complexity of ``are there $k$ vertices that dominate at least half of the blue and half of the red vertices?'' is also open. We answer both questions by providing an fpt algorithm that solves the model-checking problem for formulas of the more general form $ψ ≡ ∃x_1...x_k P (#y φ_1(x_1...x_k,y), ..., #y φ_l(x_1...x_k,y))$, where $P$ is an arbitrary polynomially computable predicate on numbers. The running time is $f(|ψ|)n^{l+1} \polylog(n)$ on graph classes of bounded expansion. Under SETH, this running time is tight up to almost linear factor.

ABSTRACT. It is known that the weighted version of Edge Multiway Cut (also known as Multiterminal Cut) is NP-complete on planar graphs of maximum degree 3. In contrast, for the unweighted version, NP-completeness is only known for planar graphs of maximum degree 11. In fact, the complexity of unweighted Edge Multiway Cut was open for graphs of maximum degree 3 for over twenty years. We prove that the unweighted version is NP-complete even for planar graphs of maximum degree 3. As weighted Edge Multiway Cut is polynomial-time solvable for graphs of maximum degree at most 2, we have now closed the complexity gap. We also prove that (unweighted) Node Multiway Cut (both with and without deletable terminals) is \NP-complete for planar graphs of maximum degree 3. By combining our results with known results, we can apply two meta-classifications on graph containment from the literature. This yields full dichotomies for all three problems on H-topological-minor-free graphs and, should H be finite, on H-subgraph-free graphs as well. Previously, such dichotomies were only implied for H-minor-free graphs.

ABSTRACT. Genome rearrangement is a common model for molecular evolution. In this paper, we consider the Pairwise Rearrangement problem, which takes as input two genomes and asks for the number of minimum-length sequences of permissible operations transforming the first genome into the second. In the Single Cut-and-Join model (Bergeron, Medvedev, & Stoye, J. Comput. Biol. 2010), Pairwise Rearrangement is #P-complete (Bailey, et. al., COCOON 2023), which implies that exact sampling is intractable. In order to cope with this intractability, we investigate the parameterized complexity of this problem. We exhibit a fixed-parameter tractable algorithm with respect to the number of components in the adjacency graph that are not cycles of length 2 or paths of length 1. As a consequence, we obtain that Pairwise Rearrangement in the Single Cut-and-Join model is fixed-parameter tractable by distance. Our results suggest that the number of nontrivial components in the adjacency graph serves as the key obstacle for efficient sampling.

ABSTRACT. Given a spanning tree $T$ of a planar graph $G$, the \emph{co-tree} of $T$ is the spanning tree of the dual graph $G^*$ with edge set $(E(G)-E(T))^*$. Grünbaum conjectured in 1970 that every planar 3-connected graph $G$ contains a spanning tree $T$ such that both $T$ and its co-tree have maximum degree at most~3.

While Grünbaum's conjecture remains open, Biedl proved that there is a spanning tree $T$ such that $T$ and its co-tree have maximum degree at most~5. By using new structural insights into Schnyder woods, we prove that there is a spanning tree $T$ such that $T$ and its co-tree have maximum degree at most~4.

ABSTRACT. An independent set in a graph is a set of vertices where no two vertices are adjacent to each other. A maximum independent set is the largest possible independent set that can be formed within a given graph $G$. The cardinality of this set is referred to as the independence number of $G$. This paper investigates the independence number of $1$-planar graphs, a subclass of graphs defined by drawings in the Euclidean plane where each edge can have at most one crossing point. Borodin establishes a tight lower bound of $6$ for the chromatic number of every $1$-planar graph $G$, leading to a corresponding lower bound of $n/6$ for the independence number, where $n$ is the number of vertices of $G$. In contrast, the upper bound for the independence number in $1$-planar graphs remains unknown. This paper addresses this gap by presenting upper bounds based on the minimum degree $\delta$. A comprehensive table summarizes these upper bounds for various $\delta$ values, providing insights into achievable independence numbers under different conditions.

ABSTRACT. There are a lot of recent works on generalizing the spectral theory of graphs and graph partitioning to k-uniform hypergraphs. There have been two broad directions toward this goal. One generalizes the notion of graph conductance to hypergraph conductance [LM16, CLTZ18]. In the second approach one can view a hypergraph as a simplicial complex and study its various topological properties [LM06, MW09, DKW16, PR17] and spectral properties [KM17, DK17, KO18a, KO18b, Opp18].

In this work, we attempt to bridge these two directions of study by relating the spectrum of up-down walks and swap-walks on the simplicial complex to hypergraph expansion. In surprising contrast to random-walks on graphs, we show that the spectral gap of swap-walks and up-down walks between level m and l with 1<m≤l can not be used to infer any bounds on hypergraph conductance. Moreover, we show that the spectral gap of swap-walks between X(1) and X(k−1) can not be used to infer any bounds on hypergraph conductance, whereas we give a Cheeger-like inequality relating the spectral of walks between level 1 and l for any l≤k to hypergraph expansion. This is a surprising difference between swaps-walks and up-down walks!

Finally, we also give a construction to show that the well-studied notion of link expansion in simplicial complexes can not be used to bound hypergraph expansion in a Cheeger like manner.

ABSTRACT. We analyze the computational complexity of the following computational problems called Bounded-Density Edge Deletion and Bounded-Density Vertex Deletion: Given a graph G, a budget k and a target density ρ_T, are there k edges (k vertices) whose removal from G results in a graph where the densest subgraph has density at most ρ_T? Here, the density of a graph is the number of its edges divided by the number of its vertices. We prove that both problems are polynomial-time solvable on trees and cliques but are NP-complete on planar bipartite graphs and split graphs. From a parameterized point of view, we show that both problems are fixed-parameter tractable with respect to the vertex cover number but W[1]-hard with respect to the solution size. Furthermore, we prove that Bounded-Density Edge Deletion is W[1]-hard with respect to the feedback edge number, demonstrating that the problem remains hard on very sparse graphs.