Journal papers

  1. Flipping Edge-Labelled Triangulations

    Flipping edge-labelled triangulations


    Abstract:

    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)$.

    With P. Bose, A. Lubiw, and V. Pathak.
    Accepted to Computational Geometry: Theory and Applications.
    Special Issue in Memoriam: Ferran Hurtado.
    @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={2013},
      note={Special Issue in Memoriam: Ferran Hurtado}
    }
    
  2. On the average number of edges in Theta graphs


    Abstract: Theta graphs are important geometric graphs that have many applications, including wireless networking, motion planning, real-time animation, and minimum-spanning tree construction. We give closed form expressions for the average degree of theta graphs of a homogeneous Poisson point process over the plane. We then show that essentially the same bounds—with vanishing error terms—hold for theta graphs of finite sets of points that are uniformly distributed in a square. Finally, we show that the number of edges in a theta graph of points uniformly distributed in a square is concentrated around its expected value.
    With P. Morin.
    Accepted to Online Journal of Analytic Combinatorics.
    @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}
    }
    
  3. Flips in edge-labelled pseudo-triangulations


    Abstract: Given a set of $n$ points in the plane, we show that $O(n^2)$ exchanging flips suffice to transform any edge-labelled pointed pseudo-triangulation into any other with the same set of labels. By using insertion, deletion and exchanging flips, we can transform any edge-labelled pseudo-triangulation into any other with $O(n \log c + h \log h)$ flips, where $c$ is the number of convex layers and $h$ is the number of points on the convex hull.
    With P. Bose.
    Computational Geometry: Theory and Applications, 60:45–54, 2017.
    Special issue for CCCG 2015.
    @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}
    }
    
  4. Towards tight bounds on theta-graphs: More is not always better


    Abstract:

    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.

    With P. Bose, J.-L. De Carufel, P. Morin, and A. van Renssen.
    Theoretical Computer Science, 616:70–93, 2016.
    @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}
    }
    
  5. Optimal local routing on {D}elaunay triangulations defined by empty equilateral triangles

    Optimal local routing on Delaunay triangulations defined by empty equilateral triangles


    Abstract:

    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.

    With P. Bose, R. Fagerberg, and A. van Renssen.
    SIAM Journal on Computing, 44(6):1626–1649, 2015.
    @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}
    }
    
  6. New and Improved Spanning Ratios for {Y}ao Graphs

    New and improved spanning ratios for Yao graphs


    Abstract:

    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.

    With L. Barba, P. Bose, M. Damian, R. Fagerberg, W. L. Keng, J. O’Rourke, A. van Renssen, P. Taslakian, and G. Xia.
    Journal of Computational Geometry, 6(2):19–53, 2015.
    Special issue for SoCG 2014.
    @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}
    }
    
  7. On the number of regular edge labelings


    Abstract: We prove that any irreducible triangulation on $n$ vertices has $O(4.6807^n)$ regular edge labelings and that there are irreducible triangulations on $n$ vertices with $\Omega(3.0426^n)$ regular edge labelings.
    With K. Buchin and B. Speckmann.
    Discrete Mathematics & Theoretical Computer Science, 16(3):215–228, 2014.
    @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}
    }
    
  8. The {$\theta_5$}-graph is a spanner

    The $\theta_5$-graph is a spanner


    Abstract: Given a set of points in the plane, we show that the $\theta$-graph with 5 cones is a geometric spanner with spanning ratio at most $\sqrt{50 + 22 \sqrt{5}} \approx 9.960$. This is the first constant upper bound on the spanning ratio of this graph. The upper bound uses a constructive argument that gives a (possibly self-intersecting) path between any two vertices, of length at most $\sqrt{50 + 22 \sqrt{5}}$ times the Euclidean distance between the vertices. We also give a lower bound on the spanning ratio of $\frac{1}{2}(11\sqrt{5} -17) \approx 3.798$.
    With P. Bose, P. Morin, and A. van Renssen.
    Computational Geometry: Theory and Applications, 48(2):108–119, 2015.
    @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}
    }
    
  9. Theta-3 is connected

    Theta-3 is connected


    Abstract: In this paper, we show that the $\theta$-graph with three cones is connected. We also provide an alternative proof of the connectivity of the Yao-graph with three cones.
    With O. Aichholzer, S. W. Bae, L. Barba, P. Bose, M. Korman, A. van Renssen, and P. Taslakian.
    Computational Geometry: Theory and Applications, 47(9):910–917, 2014.
    Special issue for CCCG 2013.
    @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}
    }
    
  10. Making triangulations 4-connected using flips

    Making triangulations 4-connected using flips


    Abstract: We show that any combinatorial triangulation on $n$ vertices can be transformed into a 4-connected one using at most $\lfloor(3n - 9)/5\rfloor$ edge flips. We also give an example of an infinite family of triangulations that requires this many flips to be made 4-connected, showing that our bound is tight. In addition, for $n \geq 19$, we improve the upper bound on the number of flips required to transform any 4-connected triangulation into the canonical triangulation (the triangulation with two dominant vertices), matching the known lower bound of $2n - 15$. Our results imply a new upper bound on the diameter of the flip graph of $5.2 n - 33.6$, improving on the previous best known bound of $6n - 30$.
    With P. Bose, D. Jansens, A. van Renssen, and M. Saumell.
    Computational Geometry: Theory and Applications, 47(2A):187–197, 2014.
    Special issue for CCCG 2011.
    @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

Conference papers that I presented are marked with (presented).
(Icon by Double-J Design, used under a Creative Commons Attribution license)

  1. Gabriel triangulations and angle-monotone graphs: local routing and recognition


    Abstract: A geometric graph is angle-monotone if every pair of vertices has a path between them that—after some rotation—is $x$- and $y$-monotone. Angle-monotone graphs are $\sqrt 2$-spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone—specifically, we prove that the half-$\Theta_6$-graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex $s$ to any vertex $t$ whose length is within $1 + \sqrt 2$ times the Euclidean distance from $s$ to $t$. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.
    With N. Bonichon, P. Bose, P. Carmi, I. Kostitsyna, and A. Lubiw.
    In Proceedings of the 24th International Symposium on Graph drawing (GD 2016), pages 519–531, 2016.
    @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}
    }
    
  2. Realizing farthest-point Voronoi diagrams


    Abstract: The farthest-point Voronoi diagram of a set of $n$ sites is a tree with $n$ leaves. We investigate whether arbitrary trees can be realized as farthest-point Voronoi diagrams. Given an abstract ordered tree $T$ with $n$ leaves and prescribed edge lengths, we produce a set of $n$ sites $S$ in $O(n)$ time such that the farthest-point Voronoi diagram of $S$ represents $T$. We generalize this algorithm to smooth strictly convex symmetric distance functions. Furthermore, when given a subdivision $Z$ of $\mathbb{R}^k$, we check in linear time whether $Z$ realizes a $k$-dimensional farthest-point Voronoi diagram when $k$ is a constant.
    With T. Biedl, C. Grimm, L. Palios, and J. Shewchuk.
    In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016), pages 48–56, 2016.
    @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}
    }
    
  3. Rectangle-of-influence triangulations

    (presented)
    Abstract: A rectangle-of-influence (RI) drawing is a straight-line drawing where for every edge $(u,v)$ the minimum axis-aligned rectangle containing $u$ and $v$ contains no other points. In this paper, we show how to create RI-triangulations (i.e., triangulations that are RI-drawings) for any point set. Moreover, by using the $L^\infty$-Delaunay-triangulations, we show that we can flip from any RI-triangulation to any other while maintaining RI-triangulations.
    With T. Biedl, A. Lubiw, and S. Mehrabi.
    In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016), pages 237–243, 2016.
    @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}
    }
    
  4. Competitive local routing with constraints


    Abstract:

    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.

    With P. Bose, R. Fagerberg, and A. van Renssen.
    In Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015), pages 23–34, 2015.
    @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}
    }
    
  5. Flips in edge-labelled pseudo-triangulations

    (presented)
    Abstract: We show that $O(n^2)$ exchanging flips suffice to transform any edge-labelled pointed pseudo-triangulation into any other with the same set of labels. By using insertion, deletion and exchanging flips, we can transform any edge-labelled pseudo-triangulation into any other with $O(n \log c + h \log h)$ flips, where $c$ is the number of convex layers and $h$ is the number of points on the convex hull.
    With P. Bose.
    In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015), pages 63–69, 2015.
    @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}
    }
    
  6. Continuous Yao graphs


    Abstract:

    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$.

    With L. Barba, P. Bose, J.-L. De Carufel, M. Damian, R. Fagerberg, A. van Renssen, and P. Taslakian.
    In Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG 2014), pages 100–106, 2014.
    @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}
    }
    
  7. Weight balancing on boundaries and skeletons


    Abstract: Given a polygonal region containing a target point (which we assume is the origin), it is not hard to see that there are two points on the perimeter that are antipodal, i.e., whose midpoint is the origin. We prove three generalizations of this fact.
    1. For any polygon (or any bounded closed region with connected boundary) containing the origin, it is possible to place a given set of weights on the boundary so that their barycenter (center of mass) coincides with the origin, provided that the largest weight does not exceed the sum of the other weights.
    2. On the boundary of any 3-dimensional bounded polyhedron containing the origin, there exist three points that form an equilateral triangle centered at the origin.
    3. On the 1-skeleton of any 3-dimensional bounded convex polyhedron containing the origin, there exist three points whose center of mass coincides with the origin.
    With L. Barba, O. Cheong, J.-L. De Carufel, M. Dobbins, R. Fleischer, A. Kawamura, M. Korman, Y. Okamoto, J. Pach, Y. Tang, T. Tokuyama, and T. Wang.
    In Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014), pages 436–443, 2014.
    @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}
    }
    
  8. New and improved spanning ratios for Yao graphs

    (presented)
    Abstract:

    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$.

    With L. Barba, P. Bose, M. Damian, R. Fagerberg, W. L. Keng, J. O’Rourke, A. van Renssen, P. Taslakian, and G. Xia.
    In Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014), pages 30–39, 2014.
    @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}
    }
    
  9. On the average number of edges in Theta graphs


    Abstract: Theta graphs are important geometric graphs that have many applications, including wireless networking, motion planning, real-time animation, and minimum-spanning tree construction. We give closed form expressions for the average degree of theta graphs of a homogeneous Poisson point process over the plane. We then show that essentially the same bounds—with vanishing error terms—hold for theta graphs of finite sets of points that are uniformly distributed in a square. Finally, we show that the number of edges in a theta graph of points uniformly distributed in a square is concentrated around its expected value.
    With P. Morin.
    In Proceedings of the 11th Meeting on Analytic Algorithmics and Combinatorics (ANALCO14), pages 121–132, 2014.
    @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}
    }
    
  10. On the spanning ratio of Theta-graphs


    Abstract: We present improved upper bounds on the spanning ratio of a large family of $\theta$-graphs. A $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta = 2 \pi/m$. 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. We also improve the upper bounds on the competitiveness of the $\theta$-routing algorithm for these graphs to $1 + 2 \sin(\theta/2) / (\cos(\theta/2) - \sin(\theta/2))$ on $\theta$-graphs with $4k + 4$ cones and to $1 + 2 \sin(\theta/2) \cdot \cos (\theta/4) / (\cos (\theta/2) - \sin (3\theta/4))$ on $\theta$-graphs with $4k + 3$ and $4k + 5$ cones. For example, the routing ratio of the $\theta$-graph with 7 cones is decreased from at most 7.5625 to at most 4.0490.
    With P. Bose and A. van Renssen.
    In Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013), pages 182–194, 2013.
    @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}
    }
    
  11. On the stretch factor of the Theta-4 graph


    Abstract: In this paper we show that the $\theta$-graph with 4 cones has constant stretch factor, i.e., there is a path between any pair of vertices in this graph whose length is at most a constant times the Euclidean distance between that pair of vertices. This is the last $\theta$-graph for which it was not known whether its stretch factor was bounded.
    With L. Barba, P. Bose, J.-L. De Carufel, and A. van Renssen.
    In Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013), pages 109–120, 2013.
    @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}
    }
    
  12. Theta-3 is connected

    (presented)
    Abstract: In this paper, we show that the $\theta$-graph with three cones is connected. We also provide an alternative proof of the connectivity of the Yao-graph with three cones.
    With O. Aichholzer, S. W. Bae, L. Barba, P. Bose, M. Korman, A. van Renssen, and P. Taslakian.
    In Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), pages 205–210, 2013.
    @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}
    }
    
  13. The $\theta_5$-graph is a spanner

    (presented)
    Abstract: We show that the $\theta$-graph with 5 cones is a geometric spanner with spanning ratio at most $\sqrt{50 + 22 \sqrt{5}} \approx 9.960$. This is the first constant upper bound on the spanning ratio of this graph. The upper bound uses a constructive argument, giving a, possibly non-planar, spanning path between any two vertices. We also give a lower bound on the spanning ratio of $\frac{1}{2}(11\sqrt{5} -17) \approx 3.798$.
    With P. Bose, P. Morin, and A. van Renssen.
    In Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013), pages 100–114, 2013.
    @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}
    }
    
  14. Competitive routing on a bounded-degree plane spanner

    (presented)
    Abstract: We show that it is possible to route locally and competitively on two bounded-degree plane 6-spanners, one with maximum degree 12 and the other with maximum degree 9. Both spanners are subgraphs of the empty equilateral triangle Delaunay triangulation. First, in a weak routing model where the only information stored at each vertex is its neighbourhood, we show how to find a path between any two vertices of a 6-spanner of maximum degree 12, such that the path has length at most $95/\sqrt{3}$ times the straight-line distance between the vertices. In a slightly stronger model, where in addition to the neighbourhood of each vertex, we store $O(1)$ additional information, we show how to find a path that has length at most $15/\sqrt{3}$ times the Euclidean distance both in a 6-spanner of maximum degree 12 and a 6-spanner of maximum degree 9.
    With P. Bose, R. Fagerberg, and A. van Renssen.
    In Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), pages 299–304, 2012.
    @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}
    }
    
  15. Optimal bounds on Theta-graphs: more is not always better


    Abstract: We present improved upper and lower bounds for a large family of $\theta$-graphs. We show that $\theta$-graphs with $4k + 2$ cones ($k \geq 1$ and integer) have a spanning ratio of $1 + 2 \sin(\theta/2)$, where $\theta$ is $2 \pi / (4k + 2)$, and this spanning ratio is tight. We also show that $\theta$-graphs with $4k + 4$ cones have spanning ratio at least $1 + 2 \tan(\theta/2) + 4 \tan^2(\theta/2)$. 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.
    With P. Bose, J.-L. De Carufel, P. Morin, and A. van Renssen.
    In Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), pages 305–310, 2012.
    @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}
    }
    
  16. Evolution Strategies for Optimizing Rectangular Cartograms

    Evolution strategies for optimizing rectangular cartograms

    (presented)
    Abstract: 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. In this paper we present a new 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.
    With K. Buchin and B. Speckmann.
    In Proceedings of the 7th International Conference on Geographic Information Science (GIScience 2012), pages 29–42, 2012.
    @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}
    }
    
  17. On plane constrained bounded-degree spanners

    (presented)
    Abstract: Let $P$ be a set of points in the plane and $S$ a set of non-crossing line segments with endpoints in $P$. The visibility graph of $P$ with respect to $S$, denoted $Vis(P,S)$, has vertex set $P$ and an edge for each pair of vertices $u,v$ in $P$ for which no line segment of $S$ properly intersects $uv$. We show that the constrained half-$\theta_6$-graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of $Vis(P,S)$. We then show how to construct a plane 6-spanner of $Vis(P,S)$ with maximum degree $6+c$, where $c$ is the maximum number of segments adjacent to a vertex.
    With P. Bose, R. Fagerberg, and A. van Renssen.
    In Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012), pages 85–96, 2012.
    @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}
    }
    
  18. Competitive routing in the half-$\theta_6$-graph


    Abstract: We present a deterministic local routing scheme that is guaranteed to find a path between any pair of vertices in a half-$\theta_6$-graph whose length is at most $5/\sqrt{3}$ times the Euclidean distance between the pair of vertices. The half-$\theta_6$-graph is identical to the Delaunay triangulation where the empty region is an equilateral triangle. Moreover, we show that no local routing scheme can achieve a better competitive spanning ratio thereby implying that our routing scheme is optimal. This is somewhat surprising because the spanning ratio of the half-$\theta_6$-graph is 2. 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 scheme for every such embedded triangulation.
    With P. Bose, R. Fagerberg, and A. van Renssen.
    In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 1319–1328, 2012.
    @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}
    }
    
  19. On rectilinear partitions with minimum stabbing number


    Abstract: Let $S$ be a set of $n$ points in $\mathbb{R}^d$, and let $r$ be a parameter with $1 \leq r \leq n$. A rectilinear $r$-partition for $S$ is a collection $\Psi(S) := {(S_1, b_1), \dots , (S_t, b_t)}$, such that the sets $S_i$ form a partition of $S$, each $b_i$ is the bounding box of $S_i$, and $n/2r \leq |S_i| \leq 2n/r$ for all $1 \leq i \leq t$. The (rectilinear) stabbing number of $\Psi(S)$ is the maximum number of bounding boxes in $\Psi(S)$ that are intersected by an axis-parallel hyperplane $h$. We study the problem of finding an optimal rectilinear $r$-partition - a rectilinear partition with minimum stabbing number - for a given set $S$. We obtain the following results.
    - Computing an optimal partition is NP-hard already in $\mathbb{R}^2$.
    - There are point sets such that any partition with disjoint bounding boxes has stabbing number $\Omega(r^{1-1/d})$, while the optimal partition has stabbing number 2.
    - An exact algorithm to compute optimal partitions, running in polynomial time if $r$ is a constant, and a faster 2-approximation algorithm.
    - An experimental investigation of various heuristics for computing rectilinear $r$-partitions in $\mathbb{R}^2$.
    With M. de Berg, A. Khosravi, and V. van der Weele.
    In Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011), pages 302–313, 2011.
    @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}
    }
    
  20. Making triangulations 4-connected using flips

    (presented)
    Abstract: We show that any triangulation on $n$ vertices can be transformed into a 4-connected one using at most $\lfloor(3n - 6)/5\rfloor$ edge flips. We also give an example of a triangulation that requires $\lceil(3n - 10)/5\rceil$ flips to be made 4-connected, showing that our bound is tight. Our result implies a new upper bound on the diameter of the flip graph of $5.2 n - 24.4$, improving on the bound of $6n -30$ by Mori et al.
    With P. Bose, D. Jansens, A. van Renssen, and M. Saumell.
    In Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), pages 241–247, 2011.
    @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}
    }
    
  21. Optimizing regular edge labelings


    Abstract: A regular edge labeling (REL) of an irreducible triangulation $G$ uniquely defines a rectangular dual of $G$. Rectangular duals find applications in various areas: as floor plans of electronic chips, in architectural designs, as rectangular cartograms, or as treemaps. An irreducible triangulation can have many RELs and hence many rectangular duals. Depending on the specific application different duals might be desirable. In this paper we consider optimization problems on RELs and show how to find optimal or near-optimal RELs for various quality criteria. Along the way we give upper and lower bounds on the number of RELs.
    With K. Buchin and B. Speckmann.
    In Proceedings of the 18th International Symposium on Graph drawing (GD 2010), pages 117–128, 2011.
    @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}
    }
    

Chapters in Books

  1. A history of flips in combinatorial triangulations


    Abstract: Given two combinatorial triangulations, how many edge flips are necessary and sufficient to convert one into the other? This question has occupied researchers for over 75 years. We provide a comprehensive survey, including full proofs, of the various attempts to answer it.
    With P. Bose.
    In A. Márquez, P. Ramos, and J. Urrutia, editors, Proceedings of the XIV Spanish Meeting on Computational Geometry (EGC 2011), volume 7579 of Lecture Notes in Computer Science, pages 29–44. Springer Berlin Heidelberg, 2012.
    @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}
    }
    

Theses

  1. Flips and spanners


    Abstract:

    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.

    PhD thesis, Carleton University, 2015.
    @phdthesis{verdonschot2015flips,
      author={Verdonschot, Sander},
      title={Flips and Spanners},
      type={PhD thesis},
      school={Carleton University},
      year={2015}
    }
    
  2. Optimizing regular edge labelings


    Abstract: A regular edge labeling of an irreducible triangulation $G$ uniquely defines a rectangular dual of $G$. Rectangular duals find applications in various areas: as floor plans of electronic chips, in architectural designs, as rectangular cartograms, or as treemaps. An irreducible triangulation can have many regular edge labelings and hence many rectangular duals. Depending on the specific application different duals might be desirable. In this thesis we consider optimization problems on regular edge labelings and show how to find optimal or near-optimal ones for various quality criteria. We evaluate our optimization methods by applying them to generate high quality rectangular cartograms. Furthermore, we show how to efficiently enumerate the regular edge labelings of an irreducible triangulation. Since the running time of the enumeration algorithm depends on the number of regular edge labelings, we also consider the maximal number of regular edge labelings an irreducible triangulation can have. We show that every irreducible triangulation with $n$ vertices has less than $O(4.6807^n)$ regular edge labelings and that there are irreducible triangulations with $\Omega(3.0426^n)$ regular edge labelings.
    Master’s thesis, Eindhoven University of Technology, 2010.
    @mastersthesis{verdonschot2010optimizing,
      author={Verdonschot, Sander},
      title={Optimizing Regular Edge Labelings},
      type={Master's thesis},
      school={Eindhoven University of Technology},
      year={2010}
    }
    

Unpublished manuscripts

  1. Dynamic graph coloring


    Abstract:

    In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a $\mathcal{C}$-colorable graph under insertion and deletion of vertices and edges. We assume that all updates keep the graph $\mathcal{C}$-colorable and that $N$ is the maximum number of vertices in the graph at any point in time.

    We present two algorithms to maintain an approximation of the optimal coloring that, together, present a trade-off between the number of recolorings and the number of colors used: For any $d>0$, the first algorithm maintains a proper $O(\mathcal{C} dN^{1/d})$-coloring and recolors at most $O(d)$ vertices per update. The second maintains an $O(\mathcal{C} d)$-coloring using $O(dN^{1/d})$ recolorings per update. Both algorithms achieve the same asymptotic performance when $d = \log N$.

    Moreover, we show that for any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices during a sequence of $m$ updates, there is a sequence of updates that forces the algorithm to recolor at least $\Omega(m\cdot N^\frac2c(c-1))$ vertices.

    With L. Barba, J. Cardinal, M. Korman, S. Langerman, A. van Renssen, and M. Roeloffzen.
    2016.

Invited Talks

  1. Flips in edge-labelled triangulations


    Abstract: Flips in tri­an­gu­la­tions have gen­er­ated a lot of in­ter­est over the past decades, but lit­tle at­ten­tion has been given to the move­ment of in­di­vid­ual edges dur­ing a se­quence of flips. We study this ques­tion by at­tach­ing a unique label to each edge of the tri­an­gu­la­tion. We give upper and lower bounds on the di­am­e­ter of the flip graph in this set­ting, for three kinds of tri­an­gu­la­tions: tri­an­gu­la­tions of a convex poly­gon, combinatorial triangulations and pseudo-tri­an­gu­la­tions.
    University of Waterloo, February 2016.
  2. Optimizing rectangular cartograms


    Abstract:

    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.

    Tohoku University, January 2016.
  3. Flips in edge-labelled triangulations


    Abstract: Flips in triangulations have generated a lot of interest over the past decades, but little attention has been given to the movement of individual edges during a sequence of flips. We study this question by attaching a unique label to each edge of the triangulation. We give upper and lower bounds on the diameter of the flip graph in this setting, for two kinds of triangulations: triangulations of a convex polygon and combinatorial triangulations.
    Eindhoven University of Technology, June 2015.
  4. Flips in edge-labelled triangulations


    Abstract: Flips in triangulations have generated a lot of interest over the past decades, but little attention has been given to the movement of individual edges during a sequence of flips. We study this question by attaching a unique label to each edge of the triangulation. We give upper and lower bounds on the diameter of the flip graph in this setting, for two kinds of triangulations: triangulations of a convex polygon and pointed pseudo-triangulations.
    Université libre de Bruxelles, May 2015.
  5. Making triangulations 4-connected using flips


    Abstract: An edge flip is an operation that transforms one triangulation into another by replacing the diagonal of the quadrilateral formed by two adjacent triangles with the other possible diagonal. One of the most natural questions to ask, is whether this allows us to transform any given triangulation into any other (with the same number of vertices). This question was answered affirmatively by Wagner, when he introduced the flip operation in 1936. The next logical question then is, how many flips does this take? Careful analysis of Wagner’s proof shows that a number of flips quadratic in the number of vertices certainly suffices. However, more recently, Komuro showed that a linear number of flips suffices as well and Mori et al. improved this bound further to $6n - 30$ flips. Their algorithm consists of two steps; it first makes the given triangulation 4-connected and then transforms the result into a fixed canonical triangulation. We give a tight bound of $(3n - 7)/5$ flips on the first step and improve the second step to match the existing lower bound of $2n - 15$ flips, resulting in a new upper bound of $5.2n - 30.8$ flips.
    Eindhoven University of Technology, December 2011.

Generated by Publy 1.1.  Last modified on 16 January 2017.