Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Bounds for Guarding Plane Graphs with Edges
86
0
0.0
(
0
)
Added by
Ahmad Biniaz
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
We provide an O(log log OPT)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building epsilon-nets of size O(1/epsilon log log 1/epsilon) for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Bronnimann and Goodrich to build an approximation algorithm from this epsilon-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygons vertices. If a finite set of potential guard locations is not specified, e.g. when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithms running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log OPT)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.
Given an arrangement of lines in the plane, what is the minimum number $c$ of colors required to color the lines so that no cell of the arrangement is monochromatic? In this paper we give bounds on the number c both for the above question, as well as some of its variations. We redefine these problems as geometric hypergraph coloring problems. If we define $Hlinecell$ as the hypergraph where vertices are lines and edges represent cells of the arrangement, the answer to the above question is equal to the chromatic number of this hypergraph. We prove that this chromatic number is between $Omega (log n / loglog n)$. and $O(sqrt{n})$. Similarly, we give bounds on the minimum size of a subset $S$ of the intersections of the lines in $mathcal{A}$ such that every cell is bounded by at least one of the vertices in $S$. This may be seen as a problem on guarding cells with vertices when the lines act as obstacles. The problem can also be defined as the minimum vertex cover problem in the hypergraph $Hvertexcell$, the vertices of which are the line intersections, and the hyperedges are vertices of a cell. Analogously, we consider the problem of touching the lines with a minimum subset of the cells of the arrangement, which we identify as the minimum vertex cover problem in the $Hcellzone$ hypergraph.
We initiate the study of the following problem: Given a non-planar graph G and a planar subgraph S of G, does there exist a straight-line drawing {Gamma} of G in the plane such that the edges of S are not crossed in {Gamma} by any edge of G? We give positive and negative results for different kinds of connected spanning subgraphs S of G. Moreover, in order to enlarge the subset of instances that admit a solution, we consider the possibility of bending the edges of G not in S; in this setting we discuss different trade-offs between the number of bends and the required drawing area.
For a real constant $alpha$, let $pi_3^alpha(G)$ be the minimum of twice the number of $K_2$s plus $alpha$ times the number of $K_3$s over all edge decompositions of $G$ into copies of $K_2$ and $K_3$, where $K_r$ denotes the complete graph on $r$ vertices. Let $pi_3^alpha(n)$ be the maximum of $pi_3^alpha(G)$ over all graphs $G$ with $n$ vertices. The extremal function $pi_3^3(n)$ was first studied by GyH{o}ri and Tuza [Decompositions of graphs into complete subgraphs of given order, Studia Sci. Math. Hungar. 22 (1987), 315--320]. In a recent progress on this problem, Kral, Lidicky, Martins and Pehova [Decomposing graphs into edges and triangles, Combin. Prob. Comput. 28 (2019) 465--472] proved via flag algebras that $pi_3^3(n)le (1/2+o(1))n^2$. We extend their result by determining the exact value of $pi_3^alpha(n)$ and the set of extremal graphs for all $alpha$ and sufficiently large $n$. In particular, we show for $alpha=3$ that $K_n$ and the complete bipartite graph $K_{lfloor n/2rfloor,lceil n/2rceil}$ are the only possible extremal examples for large $n$.
A graph drawn in the plane with n vertices is k-fan-crossing free for k > 1 if there are no k+1 edges $g,e_1,...e_k$, such that $e_1,e_2,...e_k$ have a common endpoint and $g$ crosses all $e_i$. We prove a tight bound of 4n-8 on the maximum number of edges of a 2-fan-crossing free graph, and a tight 4n-9 bound for a straight-edge drawing. For k > 2, we prove an upper bound of 3(k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
