In this paper we study local routing strategies on geometric graphs. Such strategies use geometric properties of the graph like the coordinates of the current and target nodes to route. Specifically, we study routing strategies in the presence of constraints which are obstacles that edges of the graph are not allowed to cross. Let $P$ be a set of $n$ points in the plane and let $S$ be a set of line segments whose endpoints are in $P$, with no two line segments intersecting properly. We present the first deterministic 1-local $O(1)$-memory routing algorithm that is guaranteed to find a path between two vertices in the visibility graph of $P$ with respect to a set of constraints $S$. The strategy never looks beyond the direct neighbors of the current node and does not store more than $O(1)$-information to reach the target.
We then turn our attention to finding competitive routing strategies. We show that when routing on any triangulation $T$ of $P$ such that $S \subseteq T$, no $o(n)$-competitive routing algorithm exists when the routing strategy restricts its attention to the triangles intersected by the line segment from the source to the target (a technique commonly used in the unconstrained setting). Finally, we provide an $O(n)$-competitive deterministic 1-local $O(1)$-memory routing algorithm on any such $T$, which is optimal in the worst case, given the lower bound.
@article{non-visible-constrained-routing-journal, author={Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Verdonschot, Sander}, title={Constrained Routing Between Non-Visible Vertices}, year={2017}, journal={ArXiv e-prints}, archivePrefix={arXiv}, eprint={1710.08060}, primaryClass={cs.CG}, note={\href{http://arxiv.org/abs/1710.08060}{arXiv:1710.08060} [cs.CG]}, url={http://arxiv.org/abs/1710.08060} }
@article{morin2014average, author={Morin, Pat and Verdonschot, Sander}, title={On the Average Number of Edges in {T}heta Graphs}, journal={Online Journal of Analytic Combinatorics}, year={2014} }
An edge guard set of a plane graph $G$ is a subset $\Gamma$ of edges of $G$ such that each face of $G$ is incident to an endpoint of an edge in $\Gamma$. Such a set is said to guard $G$. We improve the known upper bounds on the number of edges required to guard any $n$-vertex embedded planar graph $G$:
@article{edge-guarding-plane-graphs-journal, author={Biniaz, Ahmad and Bose, Prosenjit and Ooms, Aur\'elien and Verdonschot, Sander}, title={Improved Bounds for Guarding Plane Graphs with Edges}, journal={Graphs and Combinatorics}, year={2019}, volume={35}, number={2}, pages={437--450}, doi={10.1007/s00373-018-02004-z} }
@article{constrained-bounded-degree-spanners, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={On Plane Constrained Bounded-Degree Spanners}, journal={Algorithmica}, year={2019}, volume={81}, number={4}, pages={1392--1415}, doi={10.1007/s00453-018-0476-8} }
@article{dynamic-graph-coloring-algo, author={Barba, Luis and Cardinal, Jean and Korman, Matias and Langerman, Stefan and van Renssen, Andr\'e and Roeloffzen, Marcel and Verdonschot, Sander}, title={Dynamic Graph Coloring}, journal={Algorithmica}, year={2019}, volume={81}, number={4}, pages={1319--1341}, doi={10.1007/s00453-018-0473-y} }
@article{routing-visibility-graph-journal, author={Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Verdonschot, Sander}, title={Routing on the Visibility Graph}, journal={Journal of Computational Geometry}, year={2018}, volume={9}, number={1}, pages={430--453}, doi={10.20382/jocg.v9i1a15} }
Flips in triangulations have received a lot of attention over the past decades. However, the problem of tracking where particular edges go during the flipping process has not been addressed. We examine this question by attaching unique labels to the triangulation edges. We also introduce the concept of the orbit of an edge $e$, which is the set of all edges reachable from $e$ via flips.
We establish the first upper and lower bounds on the diameter of the flip graph in this setting. Specifically, we prove tight $\Theta(n \log n)$ bounds for edge-labelled triangulations of $n$-vertex convex polygons and combinatorial triangulations, contrasting with the $\Theta(n)$ bounds in their respective unlabelled settings. When simultaneous flips are allowed, the upper bound for convex polygons decreases to $O(\log^2 n)$, although we no longer have a matching lower bound.
Moving beyond convex polygons, we show that edge-labelled triangulated polygons with a single reflex vertex can have a disconnected flip graph. This is in sharp contrast with the unlabelled case, where the flip graph is connected for any triangulated polygon. For spiral polygons, we provide a complete characterization of the orbits. This allows us to decide connectedness of the flip graph of a spiral polygon in linear time. We also prove an upper bound of $O(n^2)$ on the diameter of each connected component, which is optimal in the worst case. We conclude with an example of a non-spiral polygon whose flip graph has diameter $\Omega(n^3)$.
@article{edge-labelled-flips-CGTA, author={Bose, Prosenjit and Lubiw, Anna and Pathak, Vinayak and Verdonschot, Sander}, title={Flipping Edge-Labelled Triangulations}, journal={Computational Geometry: Theory and Applications}, year={2018}, volume={68}, pages={309--326}, note={Special Issue in Memory of Ferran Hurtado}, doi={10.1016/j.comgeo.2017.06.005} }
In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points $S\subset \mathbb{R}^2$ and an angle $0 < \theta \leq 2\pi$, we define the \emph{continuous Yao graph} $cY(\theta)$ with vertex set $S$ and angle $\theta$ as follows. For each $p,q\in S$, we add an edge from $p$ to $q$ in $cY(\theta)$ if there exists a cone with apex $p$ and aperture $\theta$ such that $q$ is a closest point to $p$ inside this cone.
We study the spanning ratio of $cY(\theta)$ for different values of $\theta$. Using a new algebraic technique, we show that $cY(\theta)$ is a spanner when $\theta \leq 2\pi /3$. We believe that this technique may be of independent interest. We also show that $cY(\pi)$ is not a spanner, and that $cY(\theta)$ may be disconnected for $\theta > \pi$, but on the other hand is always connected for $\theta\leq \pi$. Furthermore, we show that $cY(\theta)$ is a region-fault-tolerant geometric spanner for convex fault regions when $\theta<\pi/3$. For half-plane faults, $cY(\theta)$ remains connected if $\theta\leq\pi$. Finally, we show that $cY(\theta)$ is not always self-approaching for any value of $\theta$.
@article{continuous-yao-graphs-cgta, author={Bakhshesh, Davood and Barba, Luis and Bose, Prosenjit and De Carufel, Jean-Lou and Damian, Mirela and Fagerberg, Rolf and Farshi, Mohammad and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander}, title={Continuous {Y}ao Graphs}, journal={Computational Geometry: Theory and Applications}, year={2018}, volume={67}, pages={42--52}, doi={10.1016/j.comgeo.2017.10.002} }
@article{competitive-local-routing-with-constraints, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={Competitive Local Routing with Constraints}, journal={Journal of Computational Geometry}, year={2017}, volume={8}, number={1}, pages={125--152}, doi={10.20382/jocg.v8i1a7} }
@article{edge-labelled-pts, author={Bose, Prosenjit and Verdonschot, Sander}, title={Flips in Edge-Labelled Pseudo-Triangulations}, journal={Computational Geometry: Theory and Applications}, year={2017}, volume={60}, pages={45--54}, note={Special issue for CCCG 2015}, doi={10.1016/j.comgeo.2016.08.001} }
We present improved upper and lower bounds on the spanning ratio of $\theta$-graphs with at least six cones. Given a set of points in the plane, a $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta = 2 \pi/m$, and adds an edge to the ‘closest’ vertex in each cone. We show that for any integer $k \geq 1$, $\theta$-graphs with $4k + 2$ cones have a spanning ratio of $1 + 2 \sin(\theta/2)$ and we provide a matching lower bound, showing that this spanning ratio is tight.
Next, we show that for any integer $k \geq 1$, $\theta$-graphs with $4k + 4$ cones have spanning ratio at most $1 + 2 \sin(\theta/2) / (\cos(\theta/2) - \sin(\theta/2))$. We also show that $\theta$-graphs with $4k + 3$ and $4k + 5$ cones have spanning ratio at most $\cos (\theta/4) / (\cos (\theta/2) - \sin (3\theta/4))$. This is a significant improvement on all families of $\theta$-graphs for which exact bounds are not known. For example, the spanning ratio of the $\theta$-graph with 7 cones is decreased from at most 7.5625 to at most 3.5132. These spanning proofs also imply improved upper bounds on the competitiveness of the $\theta$-routing algorithm. In particular, we show that the $\theta$-routing algorithm is $(1 + 2 \sin(\theta/2) / (\cos(\theta/2) - \sin(\theta/2)))$-competitive on $\theta$-graphs with $4k + 4$ cones and that this ratio is tight.
Finally, we present improved lower bounds on the spanning ratio of these graphs. Using these bounds, we provide a partial order on these families of $\theta$-graphs. In particular, we show that $\theta$-graphs with $4k + 4$ cones have spanning ratio at least $1 + 2 \tan(\theta/2) + 2 \tan^2(\theta/2)$, where $\theta$ is $2 \pi / (4k + 4)$. This is somewhat surprising since, for equal values of $k$, the spanning ratio of $\theta$-graphs with $4k + 4$ cones is greater than that of $\theta$-graphs with $4k + 2$ cones, showing that increasing the number of cones can make the spanning ratio worse.
@article{bose2016towards, author={Bose, Prosenjit and De Carufel, Jean-Lou and Morin, Pat and van Renssen, Andr\'e and Verdonschot, Sander}, title={Towards Tight Bounds on theta-Graphs: {M}ore is not always better}, journal={Theoretical Computer Science}, year={2016}, volume={616}, pages={70--93}, doi={10.1016/j.tcs.2015.12.017} }
We present a deterministic local routing algorithm that is guaranteed to find a path between any pair of vertices in a half-$\theta_6$-graph (the half-$\theta_6$-graph is equivalent to the Delaunay triangulation where the empty region is an equilateral triangle). The length of the path is at most $5/\sqrt{3} \approx 2.887$ times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing algorithm can achieve a better routing ratio, thereby proving that our routing algorithm is optimal. This is somewhat surprising because the spanning ratio of the half-$\theta_6$-graph is 2, meaning that even though there always exists a path whose lengths is at most twice the Euclidean distance, we cannot always find such a path when routing locally.
Since every triangulation can be embedded in the plane as a half-$\theta_6$-graph using $O(\log n)$ bits per vertex coordinate via Schnyder’s embedding scheme (SODA 1990), our result provides a competitive local routing algorithm for every such embedded triangulation. Finally, we show how our routing algorithm can be adapted to provide a routing ratio of $15/\sqrt{3} \approx 8.660$ on two bounded degree subgraphs of the half-$\theta_6$-graph.
@article{bose2015optimal, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={Optimal local routing on {D}elaunay triangulations defined by empty equilateral triangles}, journal={SIAM Journal on Computing}, year={2015}, volume={44}, number={6}, pages={1626--1649}, doi={10.1137/140988103} }
For a set of points in the plane and a fixed integer $k > 0$, the Yao graph $Y_k$ partitions the space around each point into $k$ equiangular cones of angle $\theta=2\pi/k$, and connects each point to a nearest neighbor in each cone. It is known for all Yao graphs, with the sole exception of $Y_5$, whether or not they are geometric spanners. In this paper we close this gap by showing that for odd $k \geq 5$, the spanning ratio of $Y_k$ is at most $1/(1-2\sin(3\theta/8))$, which gives the first constant upper bound for $Y_5$, and is an improvement over the previous bound of $1/(1-2\sin(\theta/2))$ for odd $k \geq 7$.
We further reduce the upper bound on the spanning ratio for $Y_5$ from $10.9$ to $2+\sqrt{3} \approx 3.74$, which falls slightly below the lower bound of $3.79$ established for the spanning ratio of $\Theta_5$ ($\Theta$-graphs differ from Yao graphs only in the way they select the closest neighbor in each cone). This is the first such separation between a Yao and $\Theta$-graph with the same number of cones. We also give a lower bound of $2.87$ on the spanning ratio of $Y_5$.
In addition, we revisit the $Y_6$ graph, which plays a particularly important role as the transition between the graphs ($k > 6$) for which simple inductive proofs are known, and the graphs ($k \le 6$) whose best spanning ratios have been established by complex arguments. Here we reduce the known spanning ratio of $Y_6$ from $17.6$ to $5.8$, getting closer to the spanning ratio of 2 established for $\Theta_6$.
Finally, we present the first lower bounds on the spanning ratio of Yao graphs with more than six cones, and a construction that shows that the Yao-Yao graph (a bounded-degree variant of the Yao graph) with five cones is not a spanner.
@article{barba2014newJournal, author={Barba, Luis and Bose, Prosenjit and Damian, Mirela and Fagerberg, Rolf and Keng, Wah Loon and O'Rourke, Joseph and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander and Xia, Ge}, title={New and Improved Spanning Ratios for {Y}ao Graphs}, journal={Journal of Computational Geometry}, year={2015}, volume={6}, number={2}, pages={19--53}, note={Special issue for SoCG 2014}, doi={10.20382/jocg.v6i2a3} }
@article{bose2013theta5journal, author={Bose, Prosenjit and Morin, Pat and van Renssen, Andr\'e and Verdonschot, Sander}, title={The {$\theta_5$}-graph is a spanner}, journal={Computational Geometry: Theory and Applications}, year={2015}, volume={48}, number={2}, pages={108--119}, doi={10.1016/j.comgeo.2014.08.005} }
@article{buchin2014number, author={Buchin, Kevin and Speckmann, Bettina and Verdonschot, Sander}, title={On the Number of Regular Edge Labelings}, journal={Discrete Mathematics {\&} Theoretical Computer Science}, year={2014}, volume={16}, number={3}, pages={215--228} }
@article{aichholzer2013theta3journal, author={Aichholzer, Oswin and Bae, Sang Won and Barba, Luis and Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander}, title={Theta-3 is connected}, journal={Computational Geometry: Theory and Applications}, year={2014}, volume={47}, number={9}, pages={910--917}, note={Special issue for CCCG 2013}, doi={10.1016/j.comgeo.2014.05.001} }
@article{bose2014making, author={Bose, Prosenjit and Jansens, Dana and van Renssen, Andr\'e and Saumell, Maria and Verdonschot, Sander}, title={Making triangulations 4-connected using flips}, journal={Computational Geometry: Theory and Applications}, year={2014}, volume={47}, number={2A}, pages={187--197}, note={Special issue for CCCG 2011}, doi={10.1016/j.comgeo.2012.10.012} }
Conference papers that I presented are marked with .
(Icon by Double-J Design, used under a Creative Commons Attribution license)
@inproceedings{convex-polygons-cartesian-products-conf, author={De Carufel, Jean-Lou and Dumitrescu, Adrian and Meulemans, Wouter and Ophelders, Tim and Pennarun, Claire and T\'oth, Csaba D. and Verdonschot, Sander}, title={On Convex Polygons in Cartesian Products}, booktitle={Proceedings of the 35th Annual Symposium on Computational Geometry (SoCG 2019)}, year={2018} }
An $\omega$-wedge consists of two rays emanating from a single point (the apex), separated by an angle $\omega < \pi$. Given a convex polygon $P$, we place the $\omega$-wedge such that $P$ is inside the wedge and both rays are tangent to $P$. The $\omega$-cloud of $P$ is the curve traced by the apex of the $\omega$-wedge as it rotates around $P$ while maintaining tangency in both rays.
Previous work crucially required knowledge of the points of tangency of the $\omega$-wedge to reconstruct $P$. We show that if $\omega$ is known, the $\omega$-cloud alone uniquely determines $P$, and we give a linear-time reconstruction algorithm. Furthermore, even if we only know that $\omega < \pi/2$, we can still reconstruct $P$, albeit in cubic time in the number of vertices. This reduces to quadratic time if in addition we are given the location of one of the vertices of $P$.
@inproceedings{reconstructing-omega-cloud-conf, author={Bose, Prosenjit and De Carufel, Jean-Lou and Khramtcova, Elena and Verdonschot, Sander}, title={Reconstructing a convex polygon from its $\omega$-cloud}, booktitle={Proceedings of the 14th International Computer Science Symposium in Russia (CSR 2019)}, year={2019} }
An edge guard set of a plane graph $G$ is a subset $\Gamma$ of edges of $G$ such that each face of $G$ is incident on an endpoint of an edge in $\Gamma$. Such a set is said to guard $G$. We improve the known upper bounds on the number of edges required to guard any $n$-vertex embedded planar graph $G$:
@inproceedings{edge-guarding-plane-graphs-conf, author={Biniaz, Ahmad and Bose, Prosenjit and Ooms, Aur\'elien and Verdonschot, Sander}, title={Improved Bounds for Guarding Plane Graphs with Edges}, booktitle={Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, year={2018}, volume={101}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, pages={14:1--14:12}, doi={10.4230/LIPIcs.SWAT.2018.14} }
@inproceedings{routing-visibility-graph-isaac, author={Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Verdonschot, Sander}, title={Routing on the Visibility Graph}, booktitle={Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017)}, year={2017}, volume={92}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, pages={18:1--18:12}, doi={10.4230/LIPIcs.ISAAC.2017.18}, url={http://drops.dagstuhl.de/opus/volltexte/2017/8222} }
@inproceedings{non-visible-constrained-routing-cocoon, author={Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Verdonschot, Sander}, title={Constrained Routing Between Non-Visible Vertices}, booktitle={Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017)}, year={2017}, pages={62--74}, doi={10.1007/978-3-319-62389-4_6} }
@inproceedings{dynamic-graph-coloring-wads, author={Barba, Luis and Cardinal, Jean and Korman, Matias and Langerman, Stefan and van Renssen, Andr\'e and Roeloffzen, Marcel and Verdonschot, Sander}, title={Dynamic Graph Coloring}, booktitle={Proceedings of the 15th Algorithms and Data Structures Symposium (WADS 2017)}, year={2017}, pages={97--108}, doi={10.1007/978-3-319-62127-2_9} }
@inproceedings{power-domination-triangular-grids-cccg, author={Bose, Prosenjit and Pennarun, Claire and Verdonschot, Sander}, title={Power domination on triangular grids}, booktitle={Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017)}, year={2017}, pages={2--6} }
@inproceedings{angle-monotone-graphs, author={Bonichon, Nicolas and Bose, Prosenjit and Carmi, Paz and Kostitsyna, Irina and Lubiw, Anna and Verdonschot, Sander}, title={Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition}, booktitle={Proceedings of the 24th International Symposium on Graph drawing (GD 2016)}, year={2016}, pages={519--531} }
@inproceedings{realizing-farthest-point-VD, author={Biedl, Therese and Grimm, Carsten and Palios, Leonidas and Shewchuk, Jonathan and Verdonschot, Sander}, title={Realizing Farthest-Point {V}oronoi Diagrams}, booktitle={Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016)}, year={2016}, pages={48--56} }
@inproceedings{rectangle-of-influence-triangulations, author={Biedl, Therese and Lubiw, Anna and Mehrabi, Saeed and Verdonschot, Sander}, title={Rectangle-of-influence triangulations}, booktitle={Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016)}, year={2016}, pages={237--243} }
Let $P$ be a set of $n$ points in the plane and $S$ a set of non-crossing line segments between vertices in $P$, called constraints. Two vertices are visible if the straight line segment connecting them does not properly intersect any constraints. The constrained $\theta_m$-graph is constructed by partitioning the plane around each vertex into $m$ disjoint cones, each with aperture $\theta = 2 \pi/m$, and adding an edge to the ‘closest’ visible vertex in each cone. We consider how to route on the constrained $\theta_6$-graph.
We first show that no deterministic 1-local routing algorithm is $o(\sqrt{n})$-competitive on all pairs of vertices of the constrained $\theta_6$-graph. After that, we show how to route between any two visible vertices of the constrained $\theta_6$-graph using only 1-local information. Our routing algorithm guarantees that the returned path has length at most 2 times the Euclidean distance between the source and destination. Additionally, we provide a 1-local 18-competitive routing algorithm for visible vertices in the constrained \graph, a subgraph of the constrained $\theta_6$-graph that is equivalent to the Delaunay graph where the empty region is an equilateral triangle. To the best of our knowledge, these are the first local routing algorithms in the constrained setting with guarantees on the length of the returned path.
@inproceedings{bose2015competitive, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={Competitive local routing with constraints}, booktitle={Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015)}, year={2015}, pages={23--34}, doi={10.1007/978-3-662-48971-0_3} }
@inproceedings{bose2015flips, author={Bose, Prosenjit and Verdonschot, Sander}, title={Flips in Edge-Labelled Pseudo-Triangulations}, booktitle={Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015)}, year={2015}, pages={63--69} }
In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points $S\subset \mathbb{R}^2$ and an angle $0 < \theta \leq 2\pi$, we define the continuous Yao graph $cY(\theta)$ with vertex set $S$ and angle $\theta$ as follows. For each $p,q\in S$, we add an edge from $p$ to $q$ in $cY(\theta)$ if there exists a cone with apex $p$ and aperture $\theta$ such that $q$ is the closest point to $p$ inside this cone.
We study the spanning ratio of $cY(\theta)$ for different values of $\theta$. Using a new algebraic technique, we show that $cY(\theta)$ is a spanner when $\theta \leq 2\pi /3$. We believe that this technique may be of independent interest. We also show that $cY(\pi)$ is not a spanner, and that $cY(\theta)$ may be disconnected for $\theta > \pi$.
@inproceedings{barba2014continuous, author={Barba, Luis and Bose, Prosenjit and De Carufel, Jean-Lou and Damian, Mirela and Fagerberg, Rolf and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander}, title={Continuous {Y}ao Graphs}, booktitle={Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG 2014)}, year={2014}, pages={100--106} }
@inproceedings{barba2014weight, author={Barba, Luis and Cheong, Otfried and De Carufel, Jean-Lou and Dobbins, Michael and Fleischer, Rudolf and Kawamura, Akitoshi and Korman, Matias and Okamoto, Yoshio and Pach, J\'anos and Tang, Yuan and Tokuyama, Takeshi and Verdonschot, Sander and Wang, Tianhao}, title={Weight Balancing on Boundaries and Skeletons}, booktitle={Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014)}, year={2014}, pages={436--443}, doi={10.1145/2582112.2582142} }
For a set of points in the plane and a fixed integer $k > 0$, the Yao graph $Y_k$ partitions the space around each point into $k$ equiangular cones of angle $\theta=2\pi/k$, and connects each point to a nearest neighbor in each cone. It is known for all Yao graphs, with the sole exception of $Y_5$, whether or not they are geometric spanners. In this paper we close this gap by showing that for odd $k \geq 5$, the spanning ratio of $Y_k$ is at most $1/(1-2\sin(3\theta/8))$, which gives the first constant upper bound for $Y_5$, and is an improvement over the previous bound of $1/(1-2\sin(\theta/2))$ for odd $k \geq 7$.
We further reduce the upper bound on the spanning ratio for $Y_5$ from $10.9$ to $2+\sqrt{3} \approx 3.74$, which falls slightly below the lower bound of $3.79$ established for the spanning ratio of $\Theta_5$ ($\Theta$-graphs differ from Yao graphs only in the way they select the closest neighbor in each cone). This is the first such separation between a Yao and $\Theta$-graph with the same number of cones. We also give a lower bound of $2.87$ on the spanning ratio of $Y_5$.
Finally, we revisit the $Y_6$ graph, which plays a particularly important role as the transition between the graphs ($k > 6$) for which simple inductive proofs are known, and the graphs ($k \le 6$) whose best spanning ratios have been established by complex arguments. Here we reduce the known spanning ratio of $Y_6$ from $17.6$ to $5.8$, getting closer to the spanning ratio of 2 established for $\Theta_6$.
@inproceedings{barba2014new, author={Barba, Luis and Bose, Prosenjit and Damian, Mirela and Fagerberg, Rolf and Keng, Wah Loon and O'Rourke, Joseph and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander and Xia, Ge}, title={New and Improved Spanning Ratios for {Y}ao Graphs}, booktitle={Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014)}, year={2014}, pages={30--39}, doi={10.1145/2582112.2582143} }
@inproceedings{morin2013average, author={Morin, Pat and Verdonschot, Sander}, title={On the Average Number of Edges in {T}heta Graphs}, booktitle={Proceedings of the 11th Meeting on Analytic Algorithmics and Combinatorics (ANALCO14)}, year={2014}, pages={121--132}, doi={10.1137/1.9781611973204.12} }
@inproceedings{bose2013spanning, author={Bose, Prosenjit and van Renssen, Andr\'e and Verdonschot, Sander}, title={On the Spanning Ratio of {T}heta-Graphs}, booktitle={Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013)}, year={2013}, pages={182--194}, doi={10.1007/978-3-642-40104-6_16} }
@inproceedings{barba2013stretch, author={Barba, Luis and Bose, Prosenjit and De Carufel, Jean-Lou and van Renssen, Andr\'e and Verdonschot, Sander}, title={On the stretch factor of the {T}heta-4 graph}, booktitle={Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013)}, year={2013}, pages={109--120}, doi={10.1007/978-3-642-40104-6_10} }
@inproceedings{aichholzer2013theta3, author={Aichholzer, Oswin and Bae, Sang Won and Barba, Luis and Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander}, title={Theta-3 is connected}, booktitle={Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013)}, year={2013}, pages={205--210} }
@inproceedings{bose2013theta5, author={Bose, Prosenjit and Morin, Pat and van Renssen, Andr\'e and Verdonschot, Sander}, title={The {$\theta_5$}-graph is a spanner}, booktitle={Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013)}, year={2013}, pages={100--114}, doi={10.1007/978-3-642-45043-3_10} }
@inproceedings{bose2012competitive2, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={Competitive Routing on a Bounded-Degree Plane Spanner}, booktitle={Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012)}, year={2012}, pages={299--304} }
@inproceedings{bose2012optimal, author={Bose, Prosenjit and De Carufel, Jean-Lou and Morin, Pat and van Renssen, Andr\'e and Verdonschot, Sander}, title={Optimal Bounds on {T}heta-Graphs: More is not Always Better}, booktitle={Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012)}, year={2012}, pages={305--310} }
@inproceedings{buchin2012evolution, author={Buchin, Kevin and Speckmann, Bettina and Verdonschot, Sander}, title={Evolution Strategies for Optimizing Rectangular Cartograms}, booktitle={Proceedings of the 7th International Conference on Geographic Information Science (GIScience 2012)}, year={2012}, volume={7478}, series={Lecture Notes in Computer Science}, pages={29--42}, doi={10.1007/978-3-642-33024-7_3} }
@inproceedings{bose2012plane, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={On Plane Constrained Bounded-Degree Spanners}, booktitle={Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012)}, year={2012}, volume={7256}, series={Lecture Notes in Computer Science}, pages={85--96}, doi={10.1007/978-3-642-29344-3_8} }
@inproceedings{bose2012competitive, author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander}, title={Competitive Routing in the Half-{$\theta_6$}-Graph}, booktitle={Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)}, year={2012}, pages={1319--1328} }
@inproceedings{deberg2011rectilinear, author={de Berg, Mark and Khosravi, Amirali and Verdonschot, Sander and van der Weele, Vincent}, title={On rectilinear partitions with minimum stabbing number}, booktitle={Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011)}, year={2011}, pages={302--313}, doi={10.1007/978-3-642-22300-6_26} }
@inproceedings{bose2011making, author={Bose, Prosenjit and Jansens, Dana and van Renssen, Andr\'e and Saumell, Maria and Verdonschot, Sander}, title={Making triangulations 4-connected using flips}, booktitle={Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011)}, year={2011}, pages={241--247} }
@inproceedings{buchin2011optimizing, author={Buchin, Kevin and Speckmann, Bettina and Verdonschot, Sander}, title={Optimizing regular edge labelings}, booktitle={Proceedings of the 18th International Symposium on Graph drawing (GD 2010)}, year={2011}, publisher={Springer-Verlag}, volume={6502}, series={Lecture Notes in Computer Science}, address={Heidelberg}, pages={117--128}, doi={10.1007/978-3-642-18469-7_11} }
@incollection{bose2012history, author={Bose, Prosenjit and Verdonschot, Sander}, title={A History of Flips in Combinatorial Triangulations}, booktitle={Proceedings of the XIV Spanish Meeting on Computational Geometry (EGC 2011)}, year={2012}, editor={M\'arquez, Alberto and Ramos, Pedro and Urrutia, Jorge}, publisher={Springer Berlin Heidelberg}, volume={7579}, series={Lecture Notes in Computer Science}, pages={29--44}, doi={10.1007/978-3-642-34191-5_3} }
In this thesis, we study two different graph problems.
The first problem revolves around geometric spanners. Here, we have a set of points in the plane and we want to connect them with straight line segments, such that there is a path between each pair of points and these paths do not require large detours. If we achieve this, the resulting graph is called a spanner. We focus our attention on two graphs (the $\Theta$-graph and Yao-graph) that are constructed by connecting each point with its nearest neighbour in a number of cones. Although this construction is very straight-forward, it has proven challenging to fully determine the properties of the resulting graphs. We show that if the construction uses 5 cones, the resulting graphs are still spanners. This was the only number of cones for which this question remained unanswered. We also present a routing strategy (a way to decide where to go next, based only on our current location, its direct neighbourhood, and our destination) on the half-$\Theta_6$-graph, a variant of the graph with 6 cones. We show that our routing strategy avoids large detours: it finds a path whose length is at most a constant factor from the straight-line distance between the endpoints. Moreover, we show that this routing strategy is optimal.
In the second part, we turn our attention to flips in triangulations. A flip is a simple operation that transforms one triangulation into another. It turns out that with enough flips, we can transform any triangulation into any other. But how many flips is enough? We present an improved upper bound of $5.2 n - 33.6$ on the maximum flip distance between any pair of triangulations with $n$ vertices. Along the way, we prove matching lower bounds on each step in the current algorithm, including a tight bound of $\lfloor(3n - 9)/5\rfloor$ flips needed to make a triangulation 4-connected. In addition, we prove tight $\Theta(n \log n)$ bounds on the number of flips required in several settings where the edges have unique labels.
@phdthesis{verdonschot2015flips, author={Verdonschot, Sander}, title={Flips and Spanners}, type={PhD thesis}, school={Carleton University}, year={2015} }
@mastersthesis{verdonschot2010optimizing, author={Verdonschot, Sander}, title={Optimizing Regular Edge Labelings}, type={Master's thesis}, school={Eindhoven University of Technology}, year={2010} }
A rectangular cartogram is a type of map where every region is a rectangle. The size of the rectangles is chosen such that their areas represent a geographic variable such as population or GDP. In recent years several algorithms for the automated construction of rectangular cartograms have been proposed, some of which are based on rectangular duals of the dual graph of the input map. A map can have many different rectangular duals, and depending on the specific application, different duals might be desirable.
We present a new heuristic approach to efficiently search within the exponentially large space of all possible rectangular duals. We employ evolution strategies that find rectangular duals which can be used for rectangular cartograms with correct adjacencies and (close to) zero cartographic error. This is a considerable improvement upon previous methods that have to either relax adjacency requirements or deal with larger errors. We present extensive experimental results for a large variety of data sets.
We also consider the maximal number of rectangular duals a map can have. We show that every map with n regions has less than $O(4.6807^n)$ rectangular duals and that there are maps with $\Omega(3.0426^n)$ rectangular duals.
Generated by Publy 1.3. Last modified on 5 May 2019.