### Geometric Graphs for Directional Communication

This research project studies fundamental combinatorial, geometric, and graph-theoretical problems related to the design of wireless networks with directional antennas. The types of antennas used in wireless networks can be roughly divided into *omnidirectional* antennas, which emit in all directions, and *directional* antennas, which emit only within a given wedge, whose orientation and angle can
be specified. Although the properties of omnidirectional networks are by now quite well understood mathematically, configuring directional antennas appropriately to form efficient communication graphs poses additional challenges. The goal is to maximize communication robustness and security while minimizing power consumption and interference. The technical focus of this research is determining theoretical and algorithmic relationships between antenna parameters (orientation, range, angle), and the structure of the induced communication graph (such as connectivity, fault tolerance, and spanning ratio). This research is supported by the NSF grant CCF-1218814 (2012-2017).

**Publications** resulted from this project (Villanova student names underlined):

- Mirela Damian and
__Naresh Nelavalli__. "Improved Bounds on the Stretch Factor of Y_{4}." In*Computational Geometry Theory and Applications*, 62(1):14-24, April 2017. - Michiel Smid, Prosenjit Bose, Paz Carmi, Mirela Damian, Jean-Lou De Carufel, Darryl Hill, Anil Maheshwari and Yuyang Liu. "On the Stretch Factor of Convex Polyhedra whose Vertices are (Almost) on a Sphere." In
*Computational Geometry Theory and Applications*, 7(1):444-472, 2016. - Luis Barba, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, Wah Loon Keng, Joseph O'Rourke, André van Renssen, Perouz Taslakian, Sander Verdonschot and Ge Xia. "New and Improved Spanning Ratios for Yao Graphs." In
*Computational Geometry Theory and Applications*, 6(2):19-53, January 2015. - Mirela Damian and
__Dumitru V. Voicu__. "Spanning Properties of Theta-Theta Graphs." In*Proc. of the 8th Int. Conference on Combinatorial Optimization and Applications*, COCOA'14, LNCS 8881, pp. 216-230, December 2014. - Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Mirela Damian, Rolf Fagerberg, André van Renssen,
Perouz Taslakian and Sander Verdonschot. "Continuous Yao Graphs." In online
*Proc. of the 26th Canadian Conference on Computational Geometry*, CCCG'14, Halifax, Nova Scotia, August 2014. - Luis Barba, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, Wah Loon Keng, Joseph O'Rourke, André
van Renssen, Perouz Taslakian, Sander Verdonschot and Ge Xia.
"New and Improved Spanning Ratios for Yao Graphs." In
*Proc. of the 30th Symposium on Computational Geometry*, SoCG'14, Kyoto, Japan, June 2014. - Prosenjit Bose, Paz Carmi, Mirela Damian, Robin Flatland, Matthew Katz and Anil Maheshwari. "Switching to
Directional Antennas with Constant Increase in Radius and Hop Distance." In
*Algorithmica*, 56(1):1-15, June 2014. - Mirela Damian and Robin Flatland. "Spanning Properties of Graphs Induced by Directional Antennas." In
*Discrete Mathematics, Algorithms and Applications*, 5(3):1-16, August 2013. - Greg Aloupis, Mirela Damian, Robin Flatland, Matias Korman, Özgür Özkan,
David Rappaport and Stefanie Wuhrer. "Establishing Strong Connectivity using Optimal
Radius Half-Disk Antennas." In
*Computational Geometry Theory and Applications*, 46(3):328-339, April 2013. -
__Matthew Bauer__and Mirela Damian. "An Infinite Class of Sparse-Yao Spanners." In*Proc. of the 24th ACM-SIAM Symposium on Discrete Algorithms*, SODA'13, pages 184-196, New Orleans, Louisiana, January 6-8, 2013.

**Abstracts** (student names underlined):

__Naresh Nelavalli__and Mirela Damian. "Improved Bounds on the Stretch Factor of Yao Graphs." In*Proc. of the Sigma Xi Student Research Poster Symposium*, Villanova University, April 22, 2016.__Kelly Gremban__,__Kelly O'Conor__and Mirela Damian. "Spanning Properties of Theta Graphs." In*Proc. of the Sigma Xi Student Research Poster Symposium*, Villanova University, April 25, 2014.__Mathura S. Srishar__,__Sreevidya Pothineni__and Mirela Damian. "Wireless Connectivity under the Random Waypoint Mobility Model." In*Proc. of the Sigma Xi Student Research Poster Symposium*, Villanova University, April 26, 2013.

**Software** (student names underlined):

- Mirela Damian,
__Kelly Gremban__and__Naresh Nelavalli__. Cone-Based Graphs, an interactive Mathematica visualization published on the Wolfram Demonstration Project website.