Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGraphs with large total angular resolution
49
0
0.0
(
0
)
Added by
Birgit Vogtenhuber
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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. We 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 triangular 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 that 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
