اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTesting Graph Isotopy on Surfaces
242
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We investigate the following problem: Given two embeddings G_1 and G_2 of the same abstract graph G on an orientable surface S, decide whether G_1 and G_2 are isotopic; in other words, whether there exists a continuous family of embeddings between G_1 and G_2. We provide efficient algorithms to solve this problem in two models. In the first model, the input consists of the arrangement of G_1 (resp., G_2) with a fixed graph cellularly embedded on S; our algorithm is linear in the input complexity, and thus, optimal. In the second model, G_1 and G_2 are piecewise-linear embeddings in the plane minus a finite set of points; our algorithm runs in O(n^{3/2}log n) time, where n is the complexity of the input. The graph isotopy problem is a natural variation of the homotopy problem for closed curves on surfaces and on the punctured plane, for which algorithms have been given by various authors; we use some of these algorithms as a subroutine. As a by-product, we reprove the following mathematical characterization, first observed by Ladegaillerie (1984): Two graph embeddings are isotopic if and only if they are homotopic and congruent by an oriented homeomorphism.
قيم البحث
اقرأ أيضاً
It is well-known that both the pathwidth and the outer-planarity of a graph can be used to obtain lower bounds on the height of a planar straight-line drawing of a graph. But both bounds fall short for some graphs. In this paper, we consider two othe
r parameters, the (simple) homotopy height and the (simple) grid-major height. We discuss the relationship between them and to the other parameters, and argue that they give lower bounds on the straight-line drawing height that are never worse than the ones obtained from pathwidth and outer-planarity.
Human subject studies that map-like visualizations are as good or better than standard node-link representations of graphs, in terms of task performance, memorization and recall of the underlying data, and engagement [SSKB14, SSKB15]. With this in mi
nd, we propose the Zoomable Multi-Level Tree (ZMLT) algorithm for multi-level tree-based, map-like visualization of large graphs. We propose seven desirable properties that such visualization should maintain and an algorithm that accomplishes them. (1) The abstract trees represent the underlying graph appropriately at different level of details; (2) The embedded trees represent the underlying graph appropriately at different levels of details; (3) At every level of detail we show real vertices and real paths from the underlying graph; (4) If any node or edge appears in a given level, then they also appear in all deeper levels; (5) All nodes at the current level and higher levels are labeled and there are no label overlaps; (6) There are no edge crossings on any level; (7) The drawing area is proportional to the total area of the labels. This algorithm is implemented and we have a functional prototype for the interactive interface in a web browser.
We study four classical graph problems -- Hamiltonian path, Traveling salesman, Minimum spanning tree, and Minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points i
n the Euclidean plane, and many of them are NP-hard. In this work, we consider these problems in two restricted settings: (i) collinear points and (ii) equidistant points on a circle. We show that almost all of these problems can be solved in linear time in these constrained, yet non-trivial settings.
textit{Clustering problems} often arise in the fields like data mining, machine learning etc. to group a collection of objects into similar groups with respect to a similarity (or dissimilarity) measure. Among the clustering problems, specifically te
xtit{$k$-means} clustering has got much attention from the researchers. Despite the fact that $k$-means is a very well studied problem its status in the plane is still an open problem. In particular, it is unknown whether it admits a PTAS in the plane. The best known approximation bound in polynomial time is $9+eps$. In this paper, we consider the following variant of $k$-means. Given a set $C$ of points in $mathcal{R}^d$ and a real $f > 0$, find a finite set $F$ of points in $mathcal{R}^d$ that minimizes the quantity $f*|F|+sum_{pin C} min_{q in F} {||p-q||}^2$. For any fixed dimension $d$, we design a local search PTAS for this problem. We also give a bi-criterion local search algorithm for $k$-means which uses $(1+eps)k$ centers and yields a solution whose cost is at most $(1+eps)$ times the cost of an optimal $k$-means solution. The algorithm runs in polynomial time for any fixed dimension. The contribution of this paper is two fold. On the one hand, we are being able to handle the square of distances in an elegant manner, which yields near optimal approximation bound. This leads us towards a better understanding of the $k$-means problem. On the other hand, our analysis of local search might also be useful for other geometric problems. This is important considering that very little is known about the local search method for geometric approximation.
In this article, we provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely
, given two homotopic curves $gamma_1$ and $gamma_2$ on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy between $gamma_1$ and $gamma_2$ where the length of the longest intermediate curve is minimized. Such optimal homotopies are relevant for a wide range of purposes, from very theoretical questions in quantitative homotopy theory to more practical applications such as similarity measures on meshes and graph searching problems. We prove that Homotopy Height is in the complexity class NP, and the corresponding exponential algorithm is the best one known for this problem. This result builds on a structural theorem on monotonicity of optimal homotopies, which is proved in a companion paper. Then we show that this problem encompasses the Homotopic Frechet distance problem which we therefore also establish to be in NP, answering a question which has previously been considered in several different settings. We also provide an O(log n)-approximation algorithm for Homotopy Height on surfaces by adapting an earlier algorithm of Har-Peled, Nayyeri, Salvatipour and Sidiropoulos in the planar setting.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
