اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدPlanar Drawings of Fixed-Mobile Bigraphs
71
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A fixed-mobile bigraph G is a bipartite graph such that the vertices of one partition set are given with fixed positions in the plane and the mobile vertices of the other part, together with the edges, must be added to the drawing. We assume that G is planar and study the problem of finding, for a given k >= 0, a planar poly-line drawing of G with at most k bends per edge. In the most general case, we show NP-hardness. For k=0 and under additional constraints on the positions of the fixed or mobile vertices, we either prove that the problem is polynomial-time solvable or prove that it belongs to NP. Finally, we present a polynomial-time testing algorithm for a certain type of layered 1-bend drawings.
قيم البحث
اقرأ أيضاً
This paper studies the problem of computing quasi-upward planar drawings of bimodal plane digraphs with minimum curve complexity, i.e., drawings such that the maximum number of bends per edge is minimized. We prove that every bimodal plane digraph ad
mits a quasi-upward planar drawing with curve complexity two, which is worst-case optimal. We also show that the problem of minimizing the curve complexity in a quasi-upward planar drawing can be modeled as a min-cost flow problem on a unit-capacity planar flow network. This gives rise to an $tilde{O}(m^frac{4}{3})$-time algorithm that computes a quasi-upward planar drawing with minimum curve complexity; in addition, the drawing has the minimum number of bends when no edge can be bent more than twice. For a contrast, we show bimodal planar digraphs whose bend-minimum quasi-upward planar drawings require linear curve complexity even in the variable embedding setting.
Graph drawing addresses the problem of finding a layout of a graph that satisfies given aesthetic and understandability objectives. The most important objective in graph drawing is minimization of the number of crossings in the drawing, as the aesthe
tics and readability of graph drawings depend on the number of edge crossings. VLSI layouts with fewer crossings are more easily realizable and consequently cheaper. A straight-line drawing of a planar graph G of n vertices is a drawing of G such that each edge is drawn as a straight-line segment without edge crossings. However, a problem with current graph layout methods which are capable of producing satisfactory results for a wide range of graphs is that they often put an extremely high demand on computational resources. This paper introduces a new layout method, which nicely draws internally convex of planar graph that consumes only little computational resources and does not need any heavy duty preprocessing. Here, we use two methods: The first is self organizing map known from unsupervised neural networks which is known as (SOM) and the second method is Inverse Self Organized Map (ISOM).
We show that many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials. A two-dimensional packing problem is defined by the type of pieces, containers, and motions that are allowed.
The aim is to decide if a given set of pieces can be placed inside a given container. The pieces must be placed so that they are pairwise interior-disjoint, and only motions of the allowed type can be used to move them there. We establish a framework which enables us to show that for many combinations of allowed pieces, containers, and motions, the resulting problem is $existsmathbb R$-complete. This means that the problem is equivalent (under polynomial time reductions) to deciding whether a given system of polynomial equations and inequalities with integer coefficients has a real solution. We consider packing problems where only translations are allowed as the motions, and problems where arbitrary rigid motions are allowed, i.e., both translations and rotations. When rotations are allowed, we show that the following combinations of allowed pieces and containers are $existsmathbb R$-complete: $bullet$ simple polygons, each of which has at most 8 corners, into a square, $bullet$ convex objects bounded by line segments and hyperbolic curves into a square, $bullet$ convex polygons into a container bounded by line segments and hyperbolic curves. Restricted to translations, we show that the following combinations are $existsmathbb R$-complete: $bullet$ objects bounded by segments and hyperbolic curves into a square, $bullet$ convex polygons into a container bounded by segments and hyperbolic curves.
Given a graph $G=(V,E)$, the dominating set problem asks for a minimum subset of vertices $Dsubseteq V$ such that every vertex $uin Vsetminus D$ is adjacent to at least one vertex $vin D$. That is, the set $D$ satisfies the condition that $|N[v]cap D
|geq 1$ for each $vin V$, where $N[v]$ is the closed neighborhood of $v$. In this paper, we study two variants of the classical dominating set problem: $boldmath{k}$-tuple dominating set ($k$-DS) problem and Liars dominating set (LDS) problem, and obtain several algorithmic and hardness results. On the algorithmic side, we present a constant factor ($frac{11}{2}$)-approximation algorithm for the Liars dominating set problem on unit disk graphs. Then, we obtain a PTAS for the $boldmath{k}$-tuple dominating set problem on unit disk graphs. On the hardness side, we show a $Omega (n^2)$ bits lower bound for the space complexity of any (randomized) streaming algorithm for Liars dominating set problem as well as for the $boldmath{k}$-tuple dominating set problem. Furthermore, we prove that the Liars dominating set problem on bipartite graphs is W[2]-hard.
In a nutshell, we show that polynomials and nested polytopes are topological, algebraic and algorithmically equivalent. Given two polytops $Asubseteq B$ and a number $k$, the Nested Polytope Problem (NPP) asks, if there exists a polytope $X$ on $k$ v
ertices such that $Asubseteq X subseteq B$. The polytope $A$ is given by a set of vertices and the polytope $B$ is given by the defining hyperplanes. We show a universality theorem for NPP. Given an instance $I$ of the NPP, we define the solutions set of $I$ as $$ V(I) = {(x_1,ldots,x_k)in mathbb{R}^{kcdot n} : Asubseteq text{conv}(x_1,ldots,x_k) subseteq B}.$$ As there are many symmetries, induced by permutations of the vertices, we will consider the emph{normalized} solution space $V(I)$. Let $F$ be a finite set of polynomials, with bounded solution space. Then there is an instance $I$ of the NPP, which has a rationally-equivalent normalized solution space $V(I)$. Two sets $V$ and $W$ are rationally equivalent if there exists a homeomorphism $f : V rightarrow W$ such that both $f$ and $f^{-1}$ are given by rational functions. A function $f:Vrightarrow W$ is a homeomorphism, if it is continuous, invertible and its inverse is continuous as well. As a corollary, we show that NPP is $exists mathbb{R}$-complete. This implies that unless $exists mathbb{R} =$ NP, the NPP is not contained in the complexity class NP. Note that those results already follow from a recent paper by Shitov. Our proof is geometric and arguably easier.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
