اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGraphs with large total angular resolution
49
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove that, up to a finite number of well specified exceptions of constant size, the number of edges of a graph with $n$ vertices and a total angular resolution greater than $60^{circ}$ is bounded by $2n-6$. This bound is tight. In addition, we show that deciding whether a graph has total angular resolution at least $60^{circ}$ is NP-hard.
قيم البحث
اقرأ أيضاً
Let $vec{T}_k$ be the transitive tournament on $k$ vertices. We show that every oriented graph on $n=4m$ vertices with minimum total degree $(11/12+o(1))n$ can be partitioned into vertex disjoint $vec{T}_4$s, and this bound is asymptotically tight. W
e also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint $vec{T}_k$s.
We provide a comprehensive study of a natural geometric optimization problem motivated by questions in the context of satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Costs (MSC), we are given a graph $G$ that
is embedded in Euclidean space. The edges of $G$ need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex takes some time proportional to the corresponding turn angle. Our goal is to minimize the time until all scans are completed, i.e., to compute a schedule of minimum makespan. We show that MSC is closely related to both graph coloring and the minimum (directed and undirected) cut cover problem; in particular, we show that the minimum scan time for instances in 1D and 2D lies in $Theta(log chi (G))$, while for 3D the minimum scan time is not upper bounded by $chi (G)$. We use this relationship to prove that the existence of a constant-factor approximation implies $P=NP$, even for one-dimensional instances. In 2D, we show that it is NP-hard to approximate a minimum scan cover within less than a factor of $frac{3}{2}$, even for bipartite graphs; conversely, we present a $frac{9}{2}$-approximation algorithm for this scenario. Generally, we give an $O(c)$-approximation for $k$-colored graphs with $kleq chi(G)^c$. For general metric cost functions, we provide approximation algorithms whose performance guarantee depend on the arboricity of the graph.
An edge guard set of a plane graph $G$ is a subset $Gamma$ of edges of $G$ such that each face of $G$ is incident to an endpoint of an edge in $Gamma$. Such a set is said to guard $G$. We improve the known upper bounds on the number of edges required
to guard any $n$-vertex embedded planar graph $G$: 1- We present a simple inductive proof for a theorem of Everett and Rivera-Campo (1997) that $G$ can be guarded with at most $ frac{2n}{5}$ edges, then extend this approach with a deeper analysis to yield an improved bound of $frac{3n}{8}$ edges for any plane graph. 2- We prove that there exists an edge guard set of $G$ with at most $frac{n}{3}+frac{alpha}{9}$ edges, where $alpha$ is the number of quadrilateral faces in $G$. This improves the previous bound of $frac{n}{3} + alpha$ by Bose, Kirkpatrick, and Li (2003). Moreover, if there is no short path between any two quadrilateral faces in $G$, we show that $frac{n}{3}$ edges suffice, removing the dependence on $alpha$.
Total Generalized Variation (TGV) has recently been proven certainly successful in image processing for preserving sharp features as well as smooth transition variations. However, none of the existing works aims at numerically calculating TGV over tr
iangular meshes. In this paper, we develop a novel numerical framework to discretize the second-order TGV over triangular meshes. Further, we propose a TGV-based variational model to restore the face normal field for mesh denoising. The TGV regularization in the proposed model is represented by a combination of a first- and second-order term, which can be automatically balanced. This TGV regularization is able to locate sharp features and preserve them via the first-order term, while recognize smoothly curved regions and recover them via the second-order term. To solve the optimization problem, we introduce an efficient iterative algorithm based on variable-splitting and augmented Lagrangian method. Extensive results and comparisons on synthetic and real scanning data validate that the proposed method outperforms the state-of-the-art methods visually and numerically.
We study biplane graphs drawn on a finite planar point set $S$ in general position. This is the family of geometric graphs whose vertex set is $S$ and can be decomposed into two plane graphs. We show that two maximal biplane graphs---in the sense tha
t no edge can be added while staying biplane---may differ in the number of edges, and we provide an efficient algorithm for adding edges to a biplane graph to make it maximal. We also study extremal properties of maximal biplane graphs such as the maximum number of edges and the largest maximum connectivity over $n$-element point sets.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
