Source author record

Abhijeet Khopkar

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

2works

3topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2012arXiv

On Computing Optimal Locally Gabriel Graphs

Delaunay and Gabriel graphs are widely studied geometric proximity structures. Motivated by applications in wireless routing, relaxed versions of these graphs known as \emph{Locally Delaunay Graphs} ( $LDGs$ ) and \emph{Locally Gabriel Graphs} ( $LGGs$ ) were proposed. We propose another generalization of $LGGs$ called \emph{Generalized Locally Gabriel Graphs} ( $GLGGs$ ) in the context when certain edges are forbidden in the graph. Unlike a Gabriel Graph, there is no unique $LGG$ or $GLGG$ 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. We show that computing an edge maximum $GLGG$ for a given problem instance is NP-hard and also APX-hard. We also show that computing an $LGG$ on a given point set with dilation $\le k$ is NP-hard. Finally, we give an algorithm to verify whether a given geometric graph $G=(V,E)$ is a valid $LGG$ .

preprint2012arXiv

On Locally Gabriel Geometric Graphs

Let $P$ be a set of $n$ points in the plane. A geometric graph $G$ on $P$ is said to be {\it locally Gabriel} if for every edge $(u,v)$ in $G$ , the disk with $u$ and $v$ as diameter does not contain any points of $P$ that are neighbors of $u$ or $v$ in $G$ . A locally Gabriel graph is a generalization of Gabriel graph and is motivated by applications in wireless networks. Unlike a Gabriel graph, there is no unique locally Gabriel graph on a given point set since no edge in a locally Gabriel graph is necessarily included or excluded. Thus the edge set of the graph can be customized to optimize certain network parameters depending on the application. In this paper, we show the following combinatorial bounds on edge complexity and independent sets of locally Gabriel graphs: (i) For any $n$ , there exists locally Gabriel graphs with $Ω(n^{5/4})$ edges. This improves upon the previous best bound of $Ω(n^{1+\frac{1}{\log \log n}})$ . (ii) For various subclasses of convex point sets, we show tight linear bounds on the maximum edge complexity of locally Gabriel graphs. (iii) For any locally Gabriel graph on any $n$ point set, there exists an independent set of size $Ω(\sqrt{n}\log n)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.