publications.bib

-- This is a comment. In fact, anything outside of entries (starting with an "at" symbol) and tags (starting with a "less-than" symbol) is ignored during parsing.

-- Authors
-- Format:
     <author short="Abbreviation for use in this file" name="Author's name, using LaTeX syntax for special characters">
-- There are a few optional arguments:
--   url: the author's website
--   group: a css class that will be applied to this author in the HTML file.
-- Example:
     <author short="padawan" name="Wan, Pada" url="http://uni.versity.edu/~pada/" group="student">
-- This author can be added to a publication by writing <<padawan>> in the author or editor field of a bibtex entry.
<author short="me"         name="Verdonschot, Sander"     url="http://cg.scs.carleton.ca/~sander/">
<author short="oswin"      name="Aichholzer, Oswin"       url="http://www.ist.tugraz.at/staff/aichholzer/">
<author short="sangwon"    name="Bae, Sang Won"           url="http://algeo.kyonggi.ac.kr/">
<author short="luis"       name="Barba, Luis"             url="http://cg.scs.carleton.ca/~lfbarba/">
<author short="mark"       name="de Berg, Mark"           url="http://www.win.tue.nl/~mdberg/">
<author short="jit"        name="Bose, Prosenjit"         url="http://jitbose.ca/">
<author short="kevin"      name="Buchin, Kevin"           url="http://www.win.tue.nl/~kbuchin/">
<author short="jeanlou"    name="De Carufel, Jean-Lou"    url="http://cg.scs.carleton.ca/~jdecaruf/">
<author short="rolf"       name="Fagerberg, Rolf"         url="http://www.imada.sdu.dk/~rolf/">
<author short="dana"       name="Jansens, Dana"           url="http://cg.scs.carleton.ca/~dana/">
<author short="amirali"    name="Khosravi, Amirali">
<author short="matias"     name="Korman, Matias"          url="http://llati.upc.es/mkorman/main.html">
<author short="pat"        name="Morin, Pat"              url="http://cg.scs.carleton.ca/~morin/">
<author short="andre"      name="van Renssen, Andr\'e"    url="http://cg.scs.carleton.ca/~andre/">
<author short="maria"      name="Saumell, Maria"          url="http://www.ulb.ac.be/di/algo/">
<author short="bettina"    name="Speckmann, Bettina"      url="http://www.win.tue.nl/~speckman/">
<author short="perouz"     name="Taslakian, Perouz"       url="http://ac.aua.am/ptaslakian/web/">
<author short="vincent"    name="van der Weele, Vincent">

-- Abbreviations
-- Format:
     <abbr short="abbreviation for use in this file" full="expanded text">
-- Abbreviations are invoked in the same way as authors, except they can occur in every field and get expanded first.
-- This means that abbreviations can contain author links (<abbr short="Group" full="<<me>> and <<padawan>>">), but not the other way around.
<abbr short="proc" full="Proceedings of the">

-- Conferences
<abbr short="analco" full="Meeting on Analytic Algorithmics and Combinatorics">
<abbr short="cccg" full="Canadian Conference on Computational Geometry">
<abbr short="esa" full="European Symposium on Algorithms">
<abbr short="gd" full="International Symposium on Graph drawing">
<abbr short="giscience" full="International Conference on Geographic Information Science">
<abbr short="isaac" full="International Symposium on Algorithms and Computation">
<abbr short="jcdcgg" full="Japan Conference on Discrete and Computational Geometry and Graphs">
<abbr short="latin" full="Latin American Symposium on Theoretical Informatics">
<abbr short="pacificvis" full="IEEE Pacific Visualization Symposium">
<abbr short="socg" full="ACM Symposium on Computational Geometry">
<abbr short="soda" full="ACM-SIAM Symposium on Discrete Algorithms">
<abbr short="wads" full="Algorithms and Data Structures Symposium">
<abbr short="wg" full="International Workshop on Graph-Theoretic Concepts in Computer Science">

-- Journals
<abbr short="cgta" full="Computational Geometry: Theory and Applications">
<abbr short="dmtcs" full="Discrete Mathematics {\&} Theoretical Computer Science">
<abbr short="ijcga" full="International Journal of Computational Geometry and Applications">
<abbr short="jap" full="Journal of Applied Probability">
<abbr short="jocg" full="Journal of Computational Geometry">
<abbr short="lncs" full="Lecture Notes in Computer Science">

-- Publications (in the order you want them to appear in your list of publications; Publy does not sort these)
-- Format: standard BibTeX format, with a few additions:
--   The above defined author abbreviations can be used in the "author" and "editor" fields: author={<<a>> and <<b>>}
--   The above defined abbreviations can be used in the value of any field (i.e. not in the type or identifier): booktitle={<<proc>> <<soda>>}
--
-- There are a few additional optional fields. Most of these are only used in the HTML version:
--   abstract: The full abstract of the paper.
--   file: A relative path locating a digital copy of the paper.
--     file={papers/2014/On the Average Number of Edges in Theta Graphs.pdf}
--   arxiv: The identifier, and optionally primary class, of an arXiv.org preprint of the paper.
--     arxiv={1212.0570 [cs.cg]}
--   doi: The DOI of the paper.
--     doi={10.1007/978-3-642-33024-7_3}
--   image: An image that is displayed next to the citation information. Recommended formats are SVG for vector drawings, and PNG for raster images. JPEG, GIF, and BMP are also widely supported.
--     image={images/paper10.svg}
--   link: An arbitrary link. Consists of an anchor text, followed by either a relative path locating a file on the website, a "#" followed by the bibtex identifier of another publication in this list, or a fully qualified url to an external resource. Examples:
--     link={Anchor|images/anchor.png}
--     link2={Slides (pdf)|slides/AwesomeTalk.pdf}
--     link3={Full version|#fullversion}
--     link4={Demonstration|http://www.youtube.com/watch?v=SomeVideo}
--     link5={Corresponding author|mailto:author (at) example.com}
--   pubstate: The status of the manuscript. Possible values are:
--     "inpreparation" for manuscripts being prepared for publication,
--     "submitted" for manuscripts submitted to a journal or conference,
--     "accepted" for manuscripts accepted to a journal or conference,
--     "acceptedrev" for manuscripts accepted to a journal or conference, conditional on minor modifications being made,
--     "inpress" for manuscripts that are fully copy-edited and out of the author’s hands; it is in the final stages of the production process, and
--     "prepublished" for manuscripts that are published in a preliminary form or location, such as an online version in advance of print publication.
--     If pubstate is missing, it indicates that the manuscript has been published.
--   presented: If this has the value "yes", this indicates that you gave the talk for this paper. You can specify text to append after the title of your publication in this case.

@inproceedings{morin2013average,
 title={On the Average Number of Edges in Theta Graphs},
 author={<<pat>> and <<me>>},
 booktitle={<<proc>> 11th <<analco>> (ANALCO14)},
 year={2014},
 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.},
 arxiv={1304.3402},
 pubstate={submitted}
}

@inproceedings{aichholzer2013theta3,
  title={Theta-3 is connected},
  author={<<oswin>> and <<sangwon>> and <<luis>> and <<jit>> and <<matias>> and <<andre>> and <<perouz>> and <<me>>},
  booktitle={<<proc>> 25th <<cccg>> (CCCG 2013)},
  pages={205--210},
  year={2013},
  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.},
  presented={yes}
}

@inproceedings{bose2013spanning,
  title={On the Spanning Ratio of Theta-Graphs},
  author={<<jit>> and <<andre>> and <<me>>},
  booktitle={<<proc>> 13th <<wads>> (WADS 2013)},
  year={2013},
  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.}
}

@inproceedings{barba2013stretch,
  title={On the stretch factor of the Theta-4 graph},
  author={<<luis>> and <<jit>> and <<jeanlou>> and <<andre>> and <<me>>},
  booktitle={<<proc>> 13th <<wads>> (WADS 2013)},
  year={2013},
  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.},
  arxiv={1303.5473}
}

@inproceedings{bose2013theta5,
  title={The {$\theta_5$}-graph is a spanner},
  author={<<jit>> and <<pat>> and <<andre>> and <<me>>},
  booktitle={<<proc>> 39th <<wg>> (WG 2013)},
  year={2013},
  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$.},
  arxiv={1212.0570},
  presented={yes}
}

-- 2012

@inproceedings{bose2012competitive2,
  title={Competitive Routing on a Bounded-Degree Plane Spanner},
  author={<<jit>> and <<rolf>> and <<andre>> and <<me>>},
  booktitle={<<proc>> 24th <<cccg>> (CCCG 2012)},
  pages={299--304},
  year={2012},
  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.},
  presented={yes}
}

@inproceedings{bose2012optimal,
  title={Optimal Bounds on Theta-Graphs: More is not Always Better},
  author={<<jit>> and <<jeanlou>> and <<pat>> and <<andre>> and <<me>>},
  booktitle={<<proc>> 24th <<cccg>> (CCCG 2012)},
  pages={305--310},
  year={2012},
  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.}
}

@inproceedings{buchin2012evolution,
  title={Evolution Strategies for Optimizing Rectangular Cartograms},
  author={<<kevin>> and <<bettina>> and <<me>>},
  booktitle={<<proc>> 7th <<giscience>> (GIScience 2012)},
  volume={7478},
  series={<<lncs>>},
  pages={29--42},
  year={2012},
  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.},
  doi={10.1007/978-3-642-33024-7_3},
  presented={yes}
}

@article{buchin2012number,
  title={On the Number of Regular Edge Labelings},
  author={<<kevin>> and <<bettina>> and <<me>>},
  journal={<<dmtcs>>},
  year={2012},
  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.},
  link={Conference version|#buchin2011optimizing},
  pubstate={accepted}
}

@misc{dec2011tue,
  title={Making triangulations 4-connected using flips},
  author={<<me>>},
  year={2011},
  month={December},
  address={Eindhoven University of Technology},
  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.},
  presented={yes}
}

@article{bose2012making,
  title={Making triangulations 4-connected using flips},
  author={<<jit>> and <<dana>> and <<andre>> and <<maria>> and <<me>>},
  journal={<<cgta>> special issue for CCCG 2011},
  year={2012},
  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$.},
  arxiv={1110.6473},
  doi={10.1016/j.comgeo.2012.10.012},
  link2={Conference version|#bose2011making},
}

@inproceedings{bose2012plane,
  title={On Plane Constrained Bounded-Degree Spanners},
  author={<<jit>> and <<rolf>> and <<andre>> and <<me>>},
  booktitle={<<proc>> 10th <<latin>> (LATIN 2012)},
  volume={7256},
  series={<<lncs>>},
  pages={85--96},
  year={2012},
  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.},
  doi={10.1007/978-3-642-29344-3_8},
  presented={yes}
}

@incollection{bose2012history,
  title={A History of Flips in Combinatorial Triangulations},
  author={<<jit>> and <<me>>},
  booktitle={<<proc>> XIV Spanish Meeting on Computational Geometry (EGC 2011)},
  volume={7579},
  series={<<lncs>>},
  pages={29--44},
  editor={M\'arquez, Alberto and Ramos, Pedro and Urrutia, Jorge},
  publisher={Springer Berlin Heidelberg},
  year={2012},
  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.},
  arxiv={1206.0303},
  doi={10.1007/978-3-642-34191-5_3}
}

@inproceedings{bose2012competitive,
  title={Competitive Routing in the Half-{$\theta_6$}-Graph},
  author={<<jit>> and <<rolf>> and <<andre>> and <<me>>},
  booktitle={<<proc>> 23rd <<soda>> (SODA 2012)},
  pages = {1319--1328},
  year={2012},
  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.},
  link3={ACM|http://dl.acm.org/citation.cfm?id=2095116.2095220}
}

-- 2011

@inproceedings{deberg2011rectilinear,
  title={On rectilinear partitions with minimum stabbing number},
  author={<<mark>> and <<amirali>> and <<me>> and <<vincent>>},
  booktitle={<<proc>> 12th <<wads>> (WADS 2011)},
  pages = {302--313},
  year = {2011},
  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.<br>
- Computing an optimal partition is NP-hard already in $\mathbb{R}^2$.<br>
- 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.<br>
- An exact algorithm to compute optimal partitions, running in polynomial time if $r$ is a constant, and a faster 2-approximation algorithm.<br>
- An experimental investigation of various heuristics for computing rectilinear $r$-partitions in $\mathbb{R}^2$.},
  doi={10.1007/978-3-642-22300-6_26}
}

@inproceedings{bose2011making,
  title={Making triangulations 4-connected using flips},
  author={<<jit>> and <<dana>> and <<andre>> and <<maria>> and <<me>>},
  booktitle={<<proc>> 23rd <<cccg>> (CCCG 2011)},
  pages = {241--247},
  year = {2011},
  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.},
  presented={yes},
  link2={Journal version|#bose2012making}
}

@inproceedings{buchin2011optimizing,
  title={Optimizing regular edge labelings},
  author={<<kevin>> and <<bettina>> and <<me>>},
  booktitle={<<proc>> 18th <<gd>> (GD 2010)},
  series={<<lncs>>},
  volume={6502},
  pages={117--128},
  year={2011},
  publisher={Springer-Verlag},
  address={Heidelberg},
  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.},
  doi={10.1007/978-3-642-18469-7_11},
  link2={Journal version|#buchin2012number}
}

-- 2010

@mastersthesis{verdonschot2010optimizing,
  author={<<me>>},
  title={Optimizing Regular Edge Labelings},
  school={Eindhoven University of Technology},
  year={2010},
  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.}
}