Name
Abstract | ||
|---|---|---|
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$. |
Year | Venue | Keywords |
|---|---|---|
2011 | CoRR | computational geometry,geometric graph,independent set,data structure |
Field | DocType | Volume |
Discrete mathematics,Indifference graph,Combinatorics,Modular decomposition,Gabriel graph,Chordal graph,Cograph,Pathwidth,Mathematics,Maximal independent set,Dense graph | Journal | abs/1110.1180 |
Citations | PageRank | References |
2 | 0.40 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abhijeet Khopkar | 1 | 2 | 1.75 |
| Sathish Govindarajan | 2 | 110 | 12.84 |