On Computing Optimal Locally Gabriel Graphs

Details On Computing Optimal Locally Gabriel Graphs On Computing Optimal Locally Gabriel Graphs

2011-10-06

arxiv.org/abs/1110.1180v1

Computer Science

Computational Geometry

Scientific paper

Delaunay, Gabriel graphs are widely studied proximity structures. Motivated by applications in wireless routing, a relaxed version of these graphs known as \emph{Locally Delaunay/Locally Gabriel Graphs} ($LGG$) was proposed. We propose another generalization of these graphs called \emph{Generalized Locally Gabriel Graphs} ($GLGG$). Unlike a Gabriel Graph, $LGG/GLGG$ is not unique for a given point set because no edge is necessarily included or excluded. This property allows us to choose an $LGG/GLGG$ that optimizes a parameter of interest in the graph. In this paper we focus on computational and combinatorial questions on $LGG/GLGG$ for parameters like maximum edges, dilation and independent set. Given a geometric graph $G$, we show that computing an edge maximum $GLGG$ on $G$ is NP-hard and also APX-hard. We also show that any $LGG$ on any $n$ points contains an independent set of size $\Omega(\sqrt{n}\log n)$. Finally, we show that computing an $LGG$ on a given point set with dilation $\le k$ is NP-complete.

Affiliated with

Also associated with

No associations

Rating

On Computing Optimal Locally Gabriel Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Computing Optimal Locally Gabriel Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Computing Optimal Locally Gabriel Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-181075