اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدBundled Crossings Revisited
72
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
An effective way to reduce clutter in a graph drawing that has (many) crossings is to group edges that travel in parallel into emph{bundles}. Each edge can participate in many such bundles. Any crossing in this bundled graph occurs between two bundles, i.e., as a emph{bundled crossing}. We consider the problem of bundled crossing minimization: A graph is given and the goal is to find a bundled drawing with at most $k$ bundled crossings. We show that the problem is NP-hard when we require a simple drawing. Our main result is an FPT algorithm (in $k$) when we require a simple circular layout. These results make use of the connection between bundled crossings and graph genus.
قيم البحث
اقرأ أيضاً
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 me
eting 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.
Storyline visualizations show the structure of a story, by depicting the interactions of the characters over time. Each character is represented by an x-monotone curve from left to right, and a meeting is represented by having the curves of the parti
cipating characters run close together for some time. There have been various approaches to drawing storyline visualizations in an automated way. In order to keep the visual complexity low, rather than minimizing pairwise crossings of curves, we count block crossings, that is, pairs of intersecting bundles of lines. Partly inspired by the ILP-based approach of Gronemann et al. [GD 2016] for minimizing the number of pairwise crossings, we model the problem as a satisfiability problem (since the straightforward ILP formulation becomes more complicated and harder to solve). Having restricted ourselves to a decision problem, we can apply powerful SAT solvers to find optimal drawings in reasonable time. We compare this SAT-based approach with two exact algorithms for block crossing minimization, using both the benchmark instances of Gronemann et al. and random instances. We show that the SAT approach is suitable for real-world instances and identify cases where the other algorithms are preferable.
A path or a polygonal domain is C-oriented if the orientations of its edges belong to a set of C given orientations; this is a generalization of the notable rectilinear case (C = 2). We study exact and approximation algorithms for minimum-link C-orie
nted paths and paths with unrestricted orientations, both in C-oriented and in general domains. Our two main algorithms are as follows: A subquadratic-time algorithm with a non-trivial approximation guarantee for general (unrestricted-orientation) minimum-link paths in general domains. An algorithm to find a minimum-link C-oriented path in a C-oriented domain. Our algorithm is simpler and more time-space efficient than the prior algorithm. We also obtain several related results: - 3SUM-hardness of determining the link distance with unrestricted orientations (even in a rectilinear domain). - An optimal algorithm for finding a minimum-link rectilinear path in a rectilinear domain. The algorithm and its analysis are simpler than the existing ones. - An extension of our methods to find a C-oriented minimum-link path in a general (not necessarily C-oriented) domain. - A more efficient algorithm to compute a 2-approximate C-oriented minimum-link path. - A notion of robust paths. We show how minimum-link C-oriented paths approximate the robust paths with unrestricted orientations to within an additive error of 1.
A measure for the visual complexity of a straight-line crossing-free drawing of a graph is the minimum number of lines needed to cover all vertices. For a given graph $G$, the minimum such number (over all drawings in dimension $d in {2,3}$) is calle
d the emph{$d$-dimensional weak line cover number} and denoted by $pi^1_d(G)$. In 3D, the minimum number of emph{planes} needed to cover all vertices of~$G$ is denoted by $pi^2_3(G)$. When edges are also required to be covered, the corresponding numbers $rho^1_d(G)$ and $rho^2_3(G)$ are called the emph{(strong) line cover number} and the emph{(strong) plane cover number}. Computing any of these cover numbers -- except $pi^1_2(G)$ -- is known to be NP-hard. The complexity of computing $pi^1_2(G)$ was posed as an open problem by Chaplick et al. [WADS 2017]. We show that it is NP-hard to decide, for a given planar graph~$G$, whether $pi^1_2(G)=2$. We further show that the universal stacked triangulation of depth~$d$, $G_d$, has $pi^1_2(G_d)=d+1$. Concerning~3D, we show that any $n$-vertex graph~$G$ with $rho^2_3(G)=2$ has at most $5n-19$ edges, which is tight.
Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. The previous best algorithm
was given by Hershberger and Suri [FOCS 1993, SIAM J. Comput. 1999] and the algorithm runs in $O(nlog n)$ time and $O(nlog n)$ space, where $n$ is the total number of vertices of all obstacles. The algorithm is time-optimal because $Omega(nlog n)$ is a lower bound. It has been an open problem for over two decades whether the space can be reduced to $O(n)$. In this paper, we settle it by solving the problem in $O(nlog n)$ time and $O(n)$ space, which is optimal in both time and space; we achieve this by modifying the algorithm of Hershberger and Suri. Like their original algorithm, our new algorithm can build a shortest path map for a source point $s$ in $O(nlog n)$ time and $O(n)$ space, such that given any query point $t$, the length of a shortest path from $s$ to $t$ can be computed in $O(log n)$ time and a shortest path can be produced in additional time linear in the number of edges of the path.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
