Source author record

Alexander Ravsky

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics Computational Geometry math.CO

Catalog footprint

Research overview

6works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

Computing Height-Optimal Tangles Faster

We study the following combinatorial problem. Given a set of $n$ y-monotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset $L$ of swaps (that is, unordered pairs of numbers between 1 and $n$ ) and an initial order of the wires, a tangle realizes $L$ if each pair of wires changes its order exactly as many times as specified by $L$ . The aim is to find a tangle that realizes $L$ using the smallest number of layers. We show that this problem is NP-hard, and we give an algorithm that computes an optimal tangle for $n$ wires and a given list $L$ of swaps in $O((2|L|/n^2+1)^{n^2/2} \cdot φ^n \cdot n)$ time, where $φ\approx 1.618$ is the golden ratio. We can treat lists where every swap occurs at most once in $O(n!φ^n)$ time. We implemented the algorithm for the general case and compared it to an existing algorithm. Finally, we discuss feasibility for lists with a simple structure.

preprint2023arXiv

The Complexity of Finding Tangles

We study the following combinatorial problem. Given a set of $n$ y-monotone curves, which we call wires, a tangle determines the order of the wires on a number of horizontal layers such that any two consecutive layers differ only in swaps of neighboring wires. Given a multiset $L$ of swaps (that is, unordered pairs of wires) and an initial order of the wires, a tangle realizes $L$ if each pair of wires changes its order exactly as many times as specified by $L$ . Deciding whether a given multiset of swaps admits a realizing tangle is known to be NP-hard [Yamanaka et al., CCCG 2018]. We prove that this problem remains NP-hard if every pair of wires swaps only a constant number of times. On the positive side, we improve the runtime of a previous exponential-time algorithm. We also show that the problem is in NP and fixed-parameter tractable with respect to the number of wires.

preprint2016arXiv

Block Crossings in Storyline Visualizations

Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. Our main results are as follows. We show that minimizing the number of block crossings is NP-hard, and we develop, for meetings of bounded size, a constant-factor approximation. We also present two fixed-parameter algorithms and, for meetings of size 2, a greedy heuristic that we evaluate experimentally.

preprint2016arXiv

Drawing Graphs on Few Lines and Few Planes

We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many connections to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows. We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values. We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, maximum degree, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing). We pay special attention to planar graphs. For example, we show that there are planar graphs that can be drawn in 3-space on a lot fewer lines than in the plane.

preprint2011arXiv

On collinear sets in straight line drawings

We consider straight line drawings of a planar graph $G$ with possible edge crossings. The \emph{untangling problem} is to eliminate all edge crossings by moving as few vertices as possible to new positions. Let $fix(G)$ denote the maximum number of vertices that can be left fixed in the worst case. In the \emph{allocation problem}, we are given a planar graph $G$ on $n$ vertices together with an $n$ -point set $X$ in the plane and have to draw $G$ without edge crossings so that as many vertices as possible are located in $X$ . Let $fit(G)$ denote the maximum number of points fitting this purpose in the worst case. As $fix(G)\le fit(G)$ , we are interested in upper bounds for the latter and lower bounds for the former parameter. For each $ε>0$ , we construct an infinite sequence of graphs with $fit(G)=O(n^{σ+ε})$ , where $σ<0.99$ is a known graph-theoretic constant, namely the shortness exponent for the class of cubic polyhedral graphs. To the best of our knowledge, this is the first example of graphs with $fit(G)=o(n)$ . On the other hand, we prove that $fix(G)\ge\sqrt{n/30}$ for all $G$ with tree-width at most 2. This extends the lower bound obtained by Goaoc et al. [Discrete and Computational Geometry 42:542-569 (2009)] for outerplanar graphs. Our upper bound for $fit(G)$ is based on the fact that the constructed graphs can have only few collinear vertices in any crossing-free drawing. To prove the lower bound for $fix(G)$ , we show that graphs of tree-width 2 admit drawings that have large sets of collinear vertices with some additional special properties.

preprint2010arXiv

Untangling planar graphs from a specified vertex position - Hard cases

Given a planar graph $G$ , we consider drawings of $G$ in the plane where edges are represented by straight line segments (which possibly intersect). Such a drawing is specified by an injective embedding $π$ of the vertex set of $G$ into the plane. We prove that a wheel graph $W_n$ admits a drawing $π$ such that, if one wants to eliminate edge crossings by shifting vertices to new positions in the plane, then at most $(2+o(1))\sqrt n$ of all $n$ vertices can stay fixed. Moreover, such a drawing $π$ exists even if it is presupposed that the vertices occupy any prescribed set of points in the plane. Similar questions are discussed for other families of planar graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.