ﻻ يوجد ملخص باللغة العربية
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$.
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 insta
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
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
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$ ve
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