Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userColored Spanning Graphs for Set Visualization
62
0
0.0
(
0
)
Added by
Matias Korman
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study an algorithmic problem that is motivated by ink minimization for sparse set visualizations. Our input is a set of points in the plane which are either blue, red, or purple. Blue points belong exclusively to the blue set, red points belong exclusively to the red set, and purple points belong to both sets. A emph{red-blue-purple spanning graph} (RBP spanning graph) is a set of edges connecting the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected. We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. Specifically, we show that the general problem can be solved in polynomial time using matroid techniques. In addition, we discuss more efficient algorithms for the case in which points are located on a line or a circle, and also describe a fast $(frac 12rho+1)$-approximation algorithm, where $rho$ is the Steiner ratio.
rate research
Read More
K{a}rolyi, Pach, and T{o}th proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement generalizes to other classes of drawings, specifically, to simple drawings of the complete graph. These are drawings where edges are represented by Jordan arcs, any two of which intersect at most once. We present two partial results towards such a generalization. First, we show that the statement holds for cylindrical simple drawings. (In a cylindrical drawing, all vertices are placed on two concentric circles and no edge crosses either circle.) Second, we introduce a relaxation of the problem in which the graph is $k$-edge-colored, and the target structure must be hypochromatic, that is, avoid (at least) one color class. In this setting, we show that every $lceil (n+5)/6rceil$-edge-colored monotone simple drawing of $K_n$ contains a hypochromatic plane spanning tree. (In a monotone drawing, every edge is represented as an $x$-monotone curve.)
In this article, we study the Euclidean minimum spanning tree problem in an imprecise setup. The problem is known as the emph{Minimum Spanning Tree Problem with Neighborhoods} in the literature. We study the problem where the neighborhoods are represented as non-crossing line segments. Given a set ${cal S}$ of $n$ disjoint line segments in $I!!R^2$, the objective is to find a minimum spanning tree (MST) that contains exactly one end-point from each segment in $cal S$ and the cost of the MST is minimum among $2^n$ possible MSTs. We show that finding such an MST is NP-hard in general, and propose a $2alpha$-factor approximation algorithm for the same, where $alpha$ is the approximation factor of the best-known approximation algorithm to compute a minimum cost Steiner tree in an undirected graph with non-negative edge weights. As an implication of our reduction, we can show that the unrestricted version of the problem (i.e., one point must be chosen from each segment such that the cost of MST is as minimum as possible) is also NP-hard. We also propose a parameterized algorithm for the problem based on the separability parameter defined for segments.
A graph $G$ with $n$ vertices is called an outerstring graph if it has an intersection representation of a set of $n$ curves inside a disk such that one endpoint of every curve is attached to the boundary of the disk. Given an outerstring graph representation, the Maximum Independent Set (MIS) problem of the underlying graph can be computed in $O(s^3)$ time, where $s$ is the number of segments in the representation (Keil et al., Comput. Geom., 60:19--25, 2017). If the strings are of constant size (e.g., line segments, L-shapes, etc.), then the algorithm takes $O(n^3)$ time. In this paper, we examine the fine-grained complexity of the MIS problem on some well-known outerstring representations. We show that solving the MIS problem on grounded segment and grounded square-L representations is at least as hard as solving MIS on circle graph representations. Note that no $O(n^{2-delta})$-time algorithm, $delta>0$, is known for the MIS problem on circle graphs. For the grounded string representations where the strings are $y$-monotone simple polygonal paths of constant length with segments at integral coordinates, we solve MIS in $O(n^2)$ time and show this to be the best possible under the strong exponential time hypothesis (SETH). For the intersection graph of $n$ L-shapes in the plane, we give a $(4cdot log OPT)$-approximation algorithm for MIS (where $OPT$ denotes the size of an optimal solution), improving the previously best-known $(4cdot log n)$-approximation algorithm of Biedl and Derka (WADS 2017).
We study the cyclic color sequences induced at infinity by colored rays with apices being a given balanced finite bichromatic point set. We first study the case in which the rays are required to be pairwise disjoint. We derive a lower bound on the number of color sequences that can be realized from any such fixed point set and examine color sequences that can be realized regardless of the point set, exhibiting negative examples as well. We also provide a tight upper bound on the number of configurations that can be realized from a point set, and point sets for which there are asymptotically less configurations than that number. In addition, we provide algorithms to decide whether a color sequence is realizable from a given point set in a line or in general position. We address afterwards the variant of the problem where the rays are allowed to intersect. We prove that for some configurations and point sets, the number of ray crossings must be $Theta(n^2)$ and study then configurations that can be realized by rays that pairwise cross. We show that there are point sets for which the number of configurations that can be realized by pairwise-crossing rays is asymptotically smaller than the number of configurations realizable by pairwise-disjoint rays. We provide also point sets from which any configuration can be realized by pairwise-crossing rays and show that there is no configuration that can be realized by pairwise-crossing rays from every point set.
We prove that for each $Dge 2$ there exists $c>0$ such that whenever $ble cbig(tfrac{n}{log n}big)^{1/D}$, in the $(1:b)$ Maker-Breaker game played on $E(K_n)$, Maker has a strategy to guarantee claiming a graph $G$ containing copies of all graphs $H$ with $v(H)le n$ and $Delta(H)le D$. We show further that the graph $G$ guaranteed by this strategy also contains copies of any graph $H$ with bounded maximum degree and degeneracy at most $tfrac{D-1}{2}$. This lower bound on the threshold bias is sharp up to the $log$-factor when $H$ consists of $tfrac{n}{3}$ vertex-disjoint triangles or $tfrac{n}{4}$ vertex-disjoint $K_4$-copies.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
