Source author record

Krzysztof Fleszar

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

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms math.CO

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Colored Non-Crossing Euclidean Steiner Forest

Given a set of $k$ -colored points in the plane, we consider the problem of finding $k$ trees such that each tree connects all points of one color class, no two trees cross, and the total edge length of the trees is minimized. For $k=1$ , this is the well-known Euclidean Steiner tree problem. For general $k$ , a $kρ$ -approximation algorithm is known, where $ρ\le 1.21$ is the Steiner ratio. We present a PTAS for $k=2$ , a $(5/3+\varepsilon)$ -approximation algorithm for $k=3$ , and two approximation algorithms for general~ $k$ , with ratios $O(\sqrt n \log k)$ and $k+\varepsilon$ .

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.

preprint2016arXiv

New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness

We study the classical NP-hard problems of finding maximum-size subsets from given sets of $k$ terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The approximability of MaxEDP/NDP is currently not well understood; the best known lower bound is $Ω(\log^{1/2-ε}{n})$ , assuming NP $~\not\subseteq~$ ZPTIME $(n^{\mathrm{poly}\log n})$ . This constitutes a significant gap to the best known approximation upper bound of $O(\sqrt{n})$ due to Chekuri et al. (2006) and closing this gap is currently one of the big open problems in approximation algorithms. In their seminal paper, Raghavan and Thompson (Combinatorica, 1987) introduce the technique of randomized rounding for LPs; their technique gives an $O(1)$ -approximation when edges (or nodes) may be used by $O(\frac{\log n}{\log\log n})$ paths. In this paper, we strengthen the above fundamental results. We provide new bounds formulated in terms of the feedback vertex set number $r$ of a graph, which measures its vertex deletion distance to a forest. In particular, we obtain the following. * For MaxEDP, we give an $O(\sqrt{r}\cdot \log^{1.5}{kr})$ -approximation algorithm. As $r\leq n$ , up to logarithmic factors, our result strengthens the best known ratio $O(\sqrt{n})$ due to Chekuri et al. * Further, we show how to route $Ω(\mathrm{OPT})$ pairs with congestion $O(\frac{\log{kr}}{\log\log{kr}})$ , strengthening the bound obtained by the classic approach of Raghavan and Thompson. * For MaxNDP, we give an algorithm that gives the optimal answer in time $(k+r)^{O(r)}\cdot n$ . If $r$ is at most triple-exponential in $k$ , this improves the best known algorithm for MaxNDP with parameter $k$ , by Kawarabayashi and Wollan (STOC 2010). We complement these positive results by proving that MaxEDP is NP-hard even for $r=1$ , and MaxNDP is W $[1]$ -hard for parameter $r$ .

preprint2012arXiv

Polylogarithmic Approximation for Generalized Minimum Manhattan Networks

Given a set of $n$ terminals, which are points in $d$ -dimensional Euclidean space, the minimum Manhattan network problem (MMN) asks for a minimum-length rectilinear network that connects each pair of terminals by a Manhattan path, that is, a path consisting of axis-parallel segments whose total length equals the pair's Manhattan distance. Even for $d=2$ , the problem is NP-hard, but constant-factor approximations are known. For $d \ge 3$ , the problem is APX-hard; it is known to admit, for any $\eps > 0$, an $O(n^\eps)$-approximation. In the generalized minimum Manhattan network problem (GMMN), we are given a set $R$ of $n$ terminal pairs, and the goal is to find a minimum-length rectilinear network such that each pair in $R$ is connected by a Manhattan path. GMMN is a generalization of both MMN and the well-known rectilinear Steiner arborescence problem (RSA). So far, only special cases of GMMN have been considered. We present an $O(\log^{d+1} n)$ -approximation algorithm for GMMN (and, hence, MMN) in $d \ge 2$ dimensions and an $O(\log n)$ -approximation algorithm for 2D. We show that an existing $O(\log n)$ -approximation algorithm for RSA in 2D generalizes easily to $d>2$ dimensions.

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.

Krzysztof Fleszar

Research overview

Is this your work?

4 publications

Colored Non-Crossing Euclidean Steiner Forest

Drawing Graphs on Few Lines and Few Planes

New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness

Polylogarithmic Approximation for Generalized Minimum Manhattan Networks

See the researcher in context

Building this map preview