ON STRUCTURAL AND GRAPH THEORETIC PROPERTIES OF HIGHER ORDER DELAUNAY GRAPHS
| Autor: | Prosenjit Bose, Carlos M. Nicolas, Jesús García, Pedro Ramos, Ferran Hurtado, Manuel Abellanas |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta |
| Rok vydání: | 2009 |
| Předmět: |
Combinatorial analysis
Voronoi polygons Computer Science::Computational Geometry Theoretical Computer Science law.invention Combinatorics law Line graph Triangulations Beta skeleton Complement graph Mathematics Distance-hereditary graph Discrete mathematics Grafs Teoria de Applied Mathematics Voltage graph Butterfly graph Geometric graph theory Graph theory Triangulació Computational Mathematics Computational Theory and Mathematics Voronoi Polígons de Geometry and Topology Null graph Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC] Anàlisi combinatòria |
| Zdroj: | Recercat. Dipósit de la Recerca de Catalunya instname UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| ISSN: | 1793-6357 0218-1959 |
| DOI: | 10.1142/s0218195909003143 |
| Popis: | Given a set $\emph{P}$ of $\emph{n}$ points in the plane, the order-$\emph{k}$ Delaunay graph is a graph with vertex set $\emph{P}$ and an edge exists between two points p,q ∊ $\emph{P}$ when there is a circle through $\emph{p}$ and $\emph{q}$ with at most $\emph{k}$ other points of $\emph{P}$ in its interior. We provide upper and lower bounds on the number of edges in an order-$\emph{k}$ Delaunay graph. We study the combinatorial structure of the set of triangulations that can be constructed with edges of this graph. Furthermore, we show that the order-$\emph{k}$ Delaunay graph is connected under the flip operation when $\emph{k}$ ≤ 1 but not necessarily connected for other values of $\emph{k}$. If $\emph{P}$ is in convex position then the order-$\emph{k}$ Delaunay graph is connected for all $\emph{k}$ ≥ 0. We show that the order-$\emph{k}$ Gabriel graph, a subgraph of the order-$\emph{k}$ Delaunay graph, is Hamiltonian for $\emph{k}$ ≥ 15. Finally, the order-$\emph{k}$ Delaunay graph can be used to effciently solve a coloring problem with applications to frequency assignments in cellular networks. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|