<html> <head> <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> <meta name="Author" content="Csaba David Toth"> <meta name="Description" content="List of Publications Csaba D. Toth"> <meta name="Keywords" content="computational geometry, combinatorial geometry, distance problems, visibility, BSP"> <title>List of Publications, Csaba D. T&oacute;th</title> </head> <b>Csaba D. T&oacute;th</b><br> Associate Professor<br><A href="http://www.csun.edu/math">Department of Mathematics</A><BR><A href="http://www.csun.edu">California State University, Northridge</A><br> Room SN 434, 18111 Nordhoff St.<br> <a href="http://en.wikipedia.org/wiki/Northridge,_Los_Angeles">Northridge</a>, CA 91330-8313 <BR>Phone: (818) 677-2826<BR><TT>cdtoth &spades; acm.org<BR></TT> <br> <hr> <div align="center"><big><big><big>Publications</big></big><br> in reverse chronological order (see also <a href="http://www.informatik.uni-trier.de/~ley/pers/hd/t/T=oacute=th:Csaba_D=.html">DBLP</a>)<br> </big></div> <br> <br> <ul> <li> <b>Crossing minimization in perturbed drawings</a></b>, <ul type="circle"> <li>Radoslav Fulek and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="https://dccg.upc.edu/gd2018/">26th International Symposium on Graph Drawing and Network Visualization</a> (Barcelona, 2018)</i>, LNCS, Springer, to appear.</li> <li> <span onmouseover="weakcrossing.style.display=''" onmouseout="weakcrossing.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="weakcrossing" style="display: none;"><font size="-1"> Due to data compression or low resolution, nearby vertices and edges of a graph drawing may be bundled to a common node or arc. We model such a "compromised"' drawing by a piecewise linear map &phi;:G&rarr;<b>R</b><sup>2</sup>. We wish to perturb &phi; by an arbitrarily small &epsilon;>0 into a proper drawing (in which the vertices are distinct points, any two edges intersect in finitely many points, and no three edges have a common interior point) that minimizes the number of crossings. An &epsilon;-perturbation, for every &epsilon;>0, is given by a piecewise linear map &psi;<sub>&epsilon;</sub>:G&rarr;<b>R</b><sup>2</sup> with |&phi;-&psi;<sub>&epsilon;</sub>|<&epsilon;, where |.| is the uniform norm (i.e., sup norm). We present a polynomial-time solution for this optimization problem when <i>G</i> is a cycle and the map &phi; has no <i>spurs</i> (i.e., no two adjacent edges are mapped to overlapping arcs). We also show that the problem becomes NP-complete (i) when <i>G</i> is an arbitrary graph and &phi; has no spurs, and (ii) when &phi; may have spurs and <i>G</i> is a cycle or a union of disjoint paths. </font> </span></li> </ul> </li> <br> <li><b><a href="http://www.cs.umanitoba.ca/~cccg2018/papers/session2A-p2.pdf">Compatible paths on labelled point sets</a></b>, <ul type="circle"> <li>Yeganeh Bahoo, Ahmad Biniaz, Pilar Cano, Farah Chanchary, John Iacono, Kshitij Jain, Elena Khramtcova, Anna Lubiw, Debajyoti Mondal, Khadijeh Sheikhan, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.cs.umanitoba.ca/~cccg2018/">30th Canadian Conference on Computational Geometry</a> (Winnipeg, MB, 2018)</i>.</li> <li> <span onmouseover="CompPaths.style.display=''" onmouseout="CompPaths.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="CompPaths" style="display: none;"><font size="-1"> Let <i>P</i> and <i>Q</i> be finite point sets of the same cardinality in <b>R</b><sup>2</sup>, each labelled from 1 to <i>n</i>. Two noncrossing geometric graphs <i>G<sub>P</sub></i> and <i>G<sub>Q</sub></i> spanning <i>P</i> and <i>Q</i>, respectively, are called <i>compatible</i> if for every face <i>f</i> in <i>G<sub>P</sub></i>, there exists a corresponding face in <i>G<sub>Q</sub></i> with the same clockwise ordering of the vertices on its boundary as in <i>f</i>. In particular, <i>G<sub>P</sub></i> and <i>G<sub>Q</sub></i> must be straight-line embeddings of the same connected <i>n</i>-vertex graph <i>G</i>. No polynomial-time algorithm is known for deciding whether two labelled point sets admit compatible geometric graphs. The complexity of the problem is open, even when the graphs are constrained to be triangulations, trees, or simple paths. We give polynomial-time algorithms to find compatible paths or report that none exist in three scenarios: O(<i>n</i>) time for points in convex position; O(<i>n</i><sup>2</sup>) time for two simple polygons, where the paths are restricted to remain inside the closed polygons; and O(<i>n</i><sup>2</sup> log <i>n</i>) time for points in general position if the paths are restricted to be monotone. </font> </span></li> </ul> </li> <br> <li> <b><a href="https://arxiv.org/abs/1806.09562">Maximum area axis-aligned square packings</a></b>, <ul type="circle"> <li>Hugo A. Akitaya, Matthew D. Jones, David Stalfa, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://mfcs2018.csc.liv.ac.uk/">43rd Symposium on Mathematical Foundations of Computer Science</a> (Liverpool, 2018)</i>, LIPIcs 117, Schloss Dagstuhl, to appear. </li> <li> <span onmouseover="reach.style.display=''" onmouseout="reach.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="reach" style="display: none;"><font size="-1"> Given a point set <i>S</i>={<i>s<sub>1</sub>,...,s<sub>n</sub></i>} in the unit square <i>U</i>=[0,1]<sup>2</sup>, an <i>anchored square packing</i> is a set of <i>n</i> interior-disjoint squares in <i>U</i> such that <i>s</i><sub>i</sub> is a corner of the <i>i</i>th square. The <i>reach R(S)</i> of <i>S</i> is the set of points that may be covered by such a packing (i.e., the union of all squares anchored at points in <i>S</i>). It is shown that area(<i>R</i>(<i>S</i>))&ge;1/2 for every <I>S&subset;U</i>, and this bound is the best possible. The region <i>R(S)</i> can be computed in O(<i>n</i> log <i>n</i>) time. Finally, we show that finding a maximum area anchored square packing is NP-complete. This is the first hardness proof for a square packing problem where the possible sizes of the squares are not part of the input. </font> </span></li> </ul> </li> <br> <li> <b>Transition operations over plane trees</b>, <ul type="circle"> <li>Torrie L. Nichols, Alexander Pilz, Csaba D. T&oacute;th, and Ahad N. Zehmakan,</li> <li>in <i>Proc. <a href="http://latin2018.dc.uba.ar/">13th Latin American Theoretical INformatics Symposium</a> (Buenos Aires, 2018)</i>, LNCS <a href="https://doi.org/10.1007/978-3-319-77404-6_60">10807</a>, Springer, pp. 835-838.</li> <li> <span onmouseover="treeoperations.style.display=''" onmouseout="treeoperations.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="treeoperations" style="display: none;"><font size="-1"> The operation of transforming one spanning tree into another by replacing an edge has been considered widely, both for general and geometric graphs. For the latter, several variants have been studied (e.g., edge slides and edge rotations). In a transition graph on the set <i>T (S)</i> of noncrossing straight-line spanning trees on a finite point set <i>S</i> in the plane, two spanning trees are connected by an edge if one can be transformed into the other by such an operation. We study bounds on the diameter of these graphs, and consider the various operations both on general point sets and sets in convex position. In addition, we address the problem variant where operations may be performed simultaneously. We prove new lower and upper bounds for the diameters of the corresponding transition graphs and pose open problems. </font> </span></li> </ul> </li> <br> <li> <b><a href="https://arxiv.org/abs/1709.09209">Recognizing weak embeddings of graphs</a></b>, <ul type="circle"> <li>Hugo A. Akitaya, Radoslav Fulek, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="https://www.siam.org/meetings/da18/">ACM-SIAM Symposium on Discrete Algorithms</a> (New Orleans, LA, 2018)</i>, pp. 274-292.</li> <li> <span onmouseover="weakembedding.style.display=''" onmouseout="weakembedding.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="weakembedding" style="display: none;"><font size="-1"> We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An <i>embedding</i> &phi;:G&rarr;M of a graph <i>G</i> into a manifold <i>M</i> maps the vertices in <i>V(G)</i> to distinct points and the edges in <i>E(G)</i> to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. This raises the computational problem of deciding whether a given map &phi;:G&rarr;M comes from an embedding. A map &phi;:G&rarr;M is a <i>weak embedding</i> if it can be perturbed into an embedding &psi;<sub>&epsilon;</sub>:G&rarr;M with &#8741;&phi;-&psi;<sub>&epsilon;</sub>&#8741;<&epsilon; for every &epsilon;>0. <br> A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kyn&#269;l (2017): It reduces to solving a system of linear equations over <b>Z</b><sub>2</sub>, and it runs in O(<i>n</i><sup>2&omega;</sup>)&le;O(<i>n</i><sup>4.75</sup>) time, where &omega;<2.373 is the matrix multiplication exponent and <i>n</i> is the number of vertices and edges of <i>G</i>. We improve the running time to O(<i>n</i> log <i>n</i>). Our algorithm is also conceptually simpler: We perform a sequence of <i>local operations</i> that gradually ``untangles'' the image &phi;(<i>G</i>) into an embedding &psi;(<i>G</i>), or reports that &phi; is not a weak embedding. It generalizes a recent technique developed for the case that <i>G</i> is a cycle and the embedding is a simple polygon, and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations. </font> </span></li> </ul> </li> <br> <li> <b><a href="https://arxiv.org/abs/1708.07653">Gap-planar graphs</a></b>, <ul type="circle"> <li>Sang Won Bae, Jean-Francois Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, Seok-Hee Hong, Matias Korman, Fabrizio Montecchiani, Ignaz Rutter, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="https://gd2017.ccis.northeastern.edu/">25th Symposium on Graph Drawing & Network Visualization</a> (Boston, MA, 2017)</i>, LNCS <a href="https://doi.org/10.1007/978-3-319-73915-1_41">10692</a>, Springer, 531-545.</li> <li><a href="https://doi.org/10.1016/j.tcs.2018.05.031">Theoretical Computer Science</a> (2018), to appear.</li> <li> <span onmouseover="gapplanar.style.display=''" onmouseout="gapplanar.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="gapplanar" style="display: none;"><font size="-1"> We introduce the family of <i>k</i>-gap-planar graphs, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned with at most <i>k</i>&ge;0 of its crossings. This definition finds motivation in edge casing, as a <i>k</i>-gap-planar graph can be drawn crossing-free after introducing at most <i>k</i> local gaps per edge. We obtain results on the maximum density, drawability of complete graphs, complexity of the recognition problem, and relationships with other families of beyond-planar graphs. </font> </span></li> </ul> </li> <br> <li> <b><a href="http://arxiv.org/abs/1708.02662">Online unit clustering in higher dimensions</a></b>, <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="https://algo2017.ac.tuwien.ac.at/waoa/">15th Workshop on Approximation and Online Algorithms</a> (Vienna, 2017)</i>, LNCS <a href="https://doi.org/10.1007/978-3-319-89441-6_18">10787</a>, Springer, pp. 238-252.</li> <li> <span onmouseover="onlinecluster.style.display=''" onmouseout="onlinecluster.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="onlinecluster" style="display: none;"><font size="-1"> We revisit the online <i>Unit Clustering</i> problem in higher dimensions: Given a set of <i>n</i> points in <b>R</b><sup><i>d</i></sup>, that arrive one by one, partition the points into clusters (subsets) of diameter at most one, so as to minimize the number of clusters used. In this paper, we work in <b>R</b><sup><i>d</i></sup> using the L<sub>&infin;</sub> norm. We show that the competitive ratio of any algorithm (deterministic or randomized) for this problem must depend on the dimension <i>d</i>. This resolves an open problem raised by Epstein and van Stee (WAOA 2008). We also give a randomized online algorithm with competitive ratio O(<i>d</i><sup>2</sup>) for <i>Unit Clustering</i> of integer points (i.e., points in <b>Z</b><sup><i>d</i></sup>, d&in;<b>N</b>, under L<sub>&infin;</sub> norm). We complement these results with some additional lower bounds for related problems in higher dimensions. </font> </span></li> </ul> </li> <br> <li> <b><a href="https://arxiv.org/abs/1705.05569">Two-planar graphs are quasiplanar</a></b>, <ul type="circle"> <li>Michael Hoffmann and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://mfcs2017.cs.aau.dk/">42nd Symposium on Mathematical Foundations of Computer Science</a> (Aalborg, 2017)</i>, LIPIcs 83, Schloss Dagstuhl, <a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.47">article 47</a>.</li> <li> <span onmouseover="quasiplanar.style.display=''" onmouseout="quasiplanar.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="quasiplanar" style="display: none;"><font size="-1"> It is shown that every 2-planar graph is quasiplanar, that is, if a simple graph admits a drawing in the plane such that every edge is crossed at most twice, then it also admits a drawing in which no three edges pairwise cross. We further show that quasiplanarity is witnessed by a simple topological drawing, that is, any two edges cross at most once and adjacent edges do not cross. </font> </span></li> </ul> </li> <br> <li> <b><a href="http://arxiv.org/abs/1508.07289">A problem on track runners</a></b>, <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://2017.cccg.ca/">29th Canadian Conference on Computational Geometry</a> (Ottawa, ON, 2017)</i>, pp. 198-201.</li> <li> <span onmouseover="TrackRunners.style.display=''" onmouseout="TrackRunners.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="TrackRunners" style="display: none;"><font size="-1"> Consider the unit circle <i>C</i> and a circular arc <i>A</i> of length <i>l</i>=|<i>A</i>|<1. It is shown that there exists <i>k=k(l)</i>&in;<b>N</b>, and a schedule for <i>k</i> runners with <i>k</i> distinct but constant speeds so that at any time <i>t</i> &ge; 0, at least one of the <i>k</i> runners is <i>not</i> in <i>A</i>. </font> </span></li> </ul> </li> <br> <li> <b><a href="https://arxiv.org/abs/1612.04780">Minimum weight connectivity augmentation for planar straight-line graphs</a></b>, <ul type="circle"> <li>Hugo A. Akitaya, Rajasekhar Inkulu, Torrie L. Nichols, Diane L. Souvaine, Csaba D. T&oacute;th, and Charles R. Winston,</li> <li>preliminary results in <i>Abstracts of the <a href="http://matthewpjohnson.org/fwcg2016/">26th Fall Workshop on Computational Geometry</a> (New York, NY, 2016)</i>;</li> <li>in <i>Proc. <a href="http://walcom2017.nctu.edu.tw/index.html">11th International Conference and Workshops on Algorithms and Computation</a> (Hsinchu, 2017)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-319-53925-6_16">10167</a>, Springer, pp. 204-216.<br> <li><a href="https://doi.org/10.1016/j.tcs.2018.05.031">Theoretical Computer Science</a> (2018), to appear.</li> <li> <span onmouseover="WSedges.style.display=''" onmouseout="WSedges.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="WSedges" style="display: none;"><font size="-1"> We consider edge insertion and deletion operations that increase the connectivity of a given planar straight-line graph (PSLG), while minimizing the total edge length of the output. We show that every connected PSLG <i>G</i>=(<i>V,E</i>) in general position can be augmented to a 2-connected PSLG (<i>V,E</i>&cup;<i>E</i><sup>+</sup>) by adding new edges of total Euclidean length &#8214;<i>E</i><sup>+</sup>&#8214;&le;2&#8214;<i>E</i>&#8214;, and this bound is the best possible. An optimal edge set <i>E</i><sup>+</sup> can be computed in O(|<i>V</i>|<sup>4</sup>) time; however the problem becomes NP-hard when <i>G</i> is disconnected. Further, there is a sequence of edge insertions and deletions that transforms a connected PSLG <i>G</i>=(<i<>V,E</i>) into a planar straight-line cycle <i>G</i>2 =(<i>V,E</i>2 ) such that &#8214;<i>E</i>2 &#8214;d"2&#8214;MST(<i>V</i>)&#8214;, and the graph remains connected with edge length below &#8214;<i>E</i>&#8214;+&#8214;MST(<i>V</i>)&#8214; at all stages. These bounds are the best possible. </font> </span></li> </ul> </li> <br> <li> <b><a href="https://arxiv.org/abs/1610.00361">Reconstruction of weakly simple polygons from their edges</a></b>, <ul type="circle"> <li>Hugo A. Akitaya and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://rp-www.cs.usyd.edu.au/~visual/isaac2016/">27th International Symposium on Algorithms and Computation</a> (Sydney, 2016)</i>, LIPIcs 64, Schloss Dagstuhl, <a href="http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=6779">article 10</a>.</li> <li><a href="https://doi.org/10.1142/S021819591860004X">Internat. J. Comput. Geom. Appl.</a> <b>28</b> (2) (2018) 161-180.</li> <li> <span onmouseover="WSegment.style.display=''" onmouseout="WSegment.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="WSegment" style="display: none;"><font size="-1"> Given <i>m</i> line segments in the plane, do they form the edge set of a <i>weakly simple polygon</i>; that is, can the segment endpoints be perturbed by at most &epsilon;, for any &epsilon;>0, to obtain a simple polygon? While the analogous question for <i>simple polygons</i> can easily be answered in O(<i>m</i>log <i>m</i>) time, we show that it is NP-complete for weakly simple polygons. We give O(<i>m</i>)-time algorithms in two special cases: when all segments are collinear, or the segment endpoints are in general position. These results extend to the variant in which the segments are <i>directed</i>, and the counterclockwise traversal of a polygon should follow the orientation.<br> We study relaxations of the problem when the union of the <i>m</i> input segments is connected. (i) If each segment can be subdivided into several segments, find the minimum number of subdivision points to form a weakly simple polygon. (ii) If new line segments can be added, find the minimum total length of new segments that create a weakly simple polygon. We give worst-case upper and lower bounds for both problems. </font> </span></li> </ul> </li> <br> <li> <b><a href="http://arxiv.org/abs/1608.07056">Multi-colored spanning graphs</a></b>, <ul type="circle"> <li>Hugo A. Akitaya, Maarten L&ouml;ffler, and Csaba D. T&oacute;th,</li> <li>in <i><a href="http://arxiv.org/html/1609.02443">Proc.</a> <a href="http://algo.math.ntua.gr/~gd2016/">24th Symposium on Graph Drawing and Network Visualization</a> (Athens, 2016)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-319-50106-2_7">9801</a>, Springer, pp. 81-93.</li> <li> <span onmouseover="RBP.style.display=''" onmouseout="RBP.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="RBP" style="display: none;"><font size="-1"> We study a problem proposed by Hurtado et al. (2016) motivated by sparse set visualization. Given <i>n</i> points in the plane, each labeled with one or more primary colors, a <i>colored spanning graph</i> (CSG) is a graph such that for each primary color, the set of vertices of that color induce connected subgraph. The Min-CSG}problem asks for the minimum sum of edge length in a colored spanning graph. We show that the problem is NP-hard for <i>k</i> primary colors when <i>k</i>&ge;3 and provide a (2-(1/(3+2&rho;)))-approximation algorithm for <i>k</i>=3 that runs in polynomial time, where &rho; is the Steiner ratio. Further, we give a O(<i>n</i>) time algorithm in the special case that the input points are collinear and <i>k</i> is constant. </font> </span></li> </ul> </li> <br> <li> <b><a href="http://arxiv.org/abs/1506.07903">Constant-factor approximation for TSP with disks</a></b>, <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. T&oacute;th,</li> <li>in <i><a href="https://doi.org/10.1007/978-3-319-44479-6_15">Journey Through Discrete Mathematics: A Tribute to Ji&#345;&iacute; Matou&#353;ek</a></i>, Springer, 2017, pp. 375-390.</li> <li> <span onmouseover="TSPNdisks.style.display=''" onmouseout="TSPNdisks.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="TSPNdisks" style="display: none;"><font size="-1"> We revisit the traveling salesman problem with neighborhoods (TSPN) and present the first constant-ratio approximation for disks in the plane: Given a set of n disks in the plane, a TSP tour whose length is at most O(1) times the optimal with high probability can be computed in time that is polynomial in n. Our result is the first constant-ratio approximation for a class of planar convex bodies of arbitrary size and arbitrarily overlaps. In order to achieve a O(1)-approximation, we reduce the traveling salesman problem with disks, up to constant factors, to a minimum weight hitting set problem in a geometric hypergraph. The connection between TSPN and hitting sets in geometric hypergraphs, established here, is likely to have future applications. </font> </span></li> </ul> </li> <br> <li><b><a href="https://arxiv.org/abs/1608.04812">Monotone paths in geometric triangulations</a></b>, <ul type="circle"> <li>Adrian Dumitrescu, Ritankar Mandal, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://iwoca2016.cs.helsinki.fi/">27th International Workshop on Combinatorial Algorithms</a> (Helsinki, 2016)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-319-44543-4_32">9843</a>, Springer, pp. 411-422.</li> <li><a href="https://doi.org/10.1007/s00224-018-9855-4">Theory of Computing Systems</a> <b>62</b> (6) (2018), 1490-1524.</li> <li> <span onmouseover="MonPathTri.style.display=''" onmouseout="MonPathTri.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="MonPathTri" style="display: none;"><font size="-1"> We prove that the (maximum) number of monotone paths in a triangulation of <i>n</i> points in the plane is O(1.8026<sup><i>n</i></sup>). This improves an earlier upper bound of O(1.8393<sup><i>n</i></sup>) established by L&ouml;ffler et al. (2013). The current best lower bound of &Omega;(1.7034<sup><i>n</i></sup>) is due to the same authors. Given a planar straight-line graph <i>G</i> with <i>n</i> vertices, we show that the number of monotone paths in <i>G</i> can be computed in O(<i>n</i><sup>2</sup>) time. </font> </span></li> </ul> </li> <br> <li><a href="http://arxiv.org/abs/1410.3637"><b>A note on independent hyperplanes and general position subsets in <i>d</i>-space</b></a>, <ul type="circle"> <li>Jean Cardinal, Csaba D. T&oacute;th, and David R. Wood,</li> <li><a href="http://dx.doi.org/10.1007/s00022-016-0323-5">Journal of Geometry</a> <b>108</b> (1) (2017), 33-43.</li> </ul> </li> <br> <li> <b><a href="http://arxiv.org/abs/1603.07401">Recognizing weakly simple polygons</a></b>, <ul type="circle"> <li>Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://socg2016.cs.tufts.edu/socg.html">32nd Symposium on Computational Geometry</a> (Boston, MA, 2016)</i>, LIPIcs <a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.8">51</a>, article 8.</li> <li><a href="http://rdcu.be/vl6J">Discrete and Computational Geometry</a> <b>58</b> (4) (2017), 785 821.</li> <li> <span onmouseover="weaklysimple.style.display=''" onmouseout="weaklysimple.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="weaklysimple" style="display: none;"><font size="-1"> We present an O(<i>n</i> log <i>n</i>)-time algorithm that determines whether a given planar <i>n</i>-gon is weakly simple. This improves upon an O(<i>n</i><sup>2</sup> log <i>n</i>)-time algorithm by Chang, Erickson, and Xu (2015). Weakly simple polygons are required as input for several geometric algorithms. As such, how to recognize simple or weakly simple polygons is a fundamental question. </font> </span></li> </ul> </li> <br> <li> <b><a href="http://arxiv.org/abs/1603.00060">Anchored rectangle and square packings</a></b>, <ul type="circle"> <li>Kevin Balas, Adrian Dumitrescu, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://socg2016.cs.tufts.edu/socg.html">32nd Symposium on Computational Geometry</a> (Boston, MA, 2016)</i>, LIPIcs <a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.13">51</a>, article 13.</li> <li><a href="https://doi.org/10.1016/j.disopt.2017.08.003">Discrete Optimization</a> <b>26</b> (2017), 131-162.</li> <li> <span onmouseover="anycorner.style.display=''" onmouseout="anycorner.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="anycorner" style="display: none;"><font size="-1"> For points <i>p<sub>1</sub>,...,p<sub>n</sub></i> in the unit square [0,1]<sup>2</sup>, an <i>anchored rectangle packing</i> consists of interior-disjoint axis-aligned empty rectangles <i>r<sub>1</sub>,...,r<sub>n</sub></i> &subset; [0,1]<sup>2</sup> such that point <i>p<sub>i</sub></i> is a corner of the rectangle <i>r<sub>i</sub></i> (that is, <i>r<sub>i</sub></i> is <i>anchored</i> at <i>p<sub>i</sub></i>) for <i>i</i>=1,...,<i>n</i>. We show that for every set of <i>n</i> points in [0,1]<sup>2</sup>, there is an anchored rectangle packing of area at least 7/12-O(1/<i>n</i>), and for every <i>n</i>&in;<b>N</b>, there are <i>n</i>-element point sets for which the area of every anchored rectangle packing is at most 2/3. If the rectangles are required to be squares, we show that the maximum area of an anchored square packing is always at least 9/47 and sometimes at most 7/27. </font> </span></li> </ul> </li> <br> <li> <b><a href="http://arxiv.org/abs/1603.07737">The planar tree packing theorem</a></b>, <ul type="circle"> <li>Markus Geyer, Michael Hoffmann, Michael Kaufmann, <a href="http://vincentkusters.org/">Vincent Kusters</a>, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://socg2016.cs.tufts.edu/socg.html">32nd Symposium on Computational Geometry</a> (Boston, MA, 2016)</i>, LIPIcs <a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.41">51</a>, article 41.</li> <li><a href="http://dx.doi.org/10.20382/jocg.v8i2a6">J. Comput. Geom.</a> <b>8</b> (2) (2017), 109 177.</li> <li> <span onmouseover="treepacking.style.display=''" onmouseout="treepacking.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="treepacking" style="display: none;"><font size="-1"> Packing graphs is a combinatorial problem where several given graphs are being mapped into a common host graph such that every edge is used at most once. Much research has been devoted to the packing of trees, and especially to the case where the host graph is planar. In the planar tree packing problem we are given two trees <i>T</i><sub>1</sub> and <i>T</i><sub>2</sub> on <i>n</i> vertices and have to find a planar graph on n vertices that is the edge-disjoint union of <i>T</i><sub>1</sub> and <i>T</i><sub>1</sub>. A clear exception that must be made is the star which cannot be packed together with any other tree. But according to a conjecture of Garc&iacute;a et al. from 1997 this is the only exception, and all other pairs of trees admit a planar packing. Previous results addressed various special cases, such as a tree and a spider tree, a tree and a caterpillar, two trees of diameter four, two isomorphic trees, and trees of maximum degree three. Here we settle the conjecture in the affirmative and prove its general form, thus making it the planar tree packing theorem. The proof is constructive and provides a polynomial time algorithm to obtain a packing for two given non-star trees. </font> </span></li> </ul> </li> <br> <li> <b><A href="https://arxiv.org/abs/1611.05746">A note on <i>k</i>-planar crossing numbers</a></b>, <ul type="circle"> <li>J&aacute;nos Pach, L&aacuteszl&oacute; Sz&eacute;kely, Csaba D. T&oacute;th, and G&eacute;za T&oacute;th,</li> <li><a href="https://doi.org/10.1016/j.comgeo.2017.06.015">Computational Geometry: Theory and Applications</a> <b>68</b> (2018), 2-6.</li> <li> <span onmouseover="kplanar.style.display=''" onmouseout="kplanar.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="kplanar" style="display: none;"><font size="-1"> The <i>crossing number</i> cr(<i>G</i>) of a graph <i>G=(V,E)</i> is the smallest number of edge crossings over all drawings of <i>G</i> in the plane. For any <i>k&ge; 1</i>, the <i>k-planar crossing number</i> of <i>G</i>, cr<sub>k</sub>(<i>G</i>), is defined as the minimum of cr(<i>G</i><sub>0</sub>)+cr(<i>G</i><sub>1</sub>)+...+cr(<i>G</i><sub>k-1</sub>) over all graphs <i>G</i><sub>0</sub>, <i>G</i><sub>1</sub>,...,<i>G</i><sub>k-1</sub> with <i>G</i>=<i>G</i><sub>0</sub>&cup;<i>G</i><sub>1</sub>&cup;...&cup;<i>G</i><sub>k-1</sub>. It is shown that for every <i>k</i>&ge;1, we have cr<sub>k</sub>(<i>G</i>)&le; ((2/<i>k</i><sup>2</sup>)-(1/<i>k</i><sup>3</sup>))cr(<i>G</i>). This bound does not remain true if we replace the constant ((2/<i>k</i><sup>2</sup>)-(1/<i>k</i><sup>3</sup>)) by any number smaller than 2/<i>k</i><sup>2</sup>. Some of the results extend to the rectilinear variants of the <i>k</i>-planar crossing number. </font> </span></li> </ul> </li> <br> <li><b>Linear-size universal point sets for one-bend drawings</b>, <ul type="circle"> <li>Maarten L&ouml;ffler and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.csun.edu/gd2015">23rd Symposium on Graph Drawing and Network Visualization</a> (Los Angeles, CA, 2015)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-319-27261-0_35">9411</a>, Springer, pp. 423-429.</li> <li> <span onmouseover="benduniversal.style.display=''" onmouseout="benduniversal.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="benduniversal" style="display: none;"><font size="-1"> For every integer <i>n</i>&ge; 4, we construct a planar point set <i>S<sub>n</sub></i> of size 6<i>n</i>-10 such that every <i>n</i>-vertex planar graph admits a plane embedding in which the vertices are mapped to points in <i>S<sub>n</sub></i>, and every edge is either a line segment or a polyline with one bend, where the bend point is also in <i>S<sub>n</sub></i>. </font> </span></li> </ul> </li> <br> <li><b>Realization of simply connected polygonal linkages and recognition of unit disk contact trees</b>, <ul type="circle"> <li>Clinton Bowen, Stephane Durocher, Maarten L&ouml;ffler, Anika Rounds, Andr&eacute; Schulz, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.csun.edu/gd2015">23rd Symposium on Graph Drawing and Network Visualization</a> (Los Angeles, CA, 2015)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-319-27261-0_37">9411</a>, Springer, pp. 447-459.</li> <li> <span onmouseover="hinged.style.display=''" onmouseout="hinged.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="hinged" style="display: none;"><font size="-1"> We wish to decide whether a simply connected flexible polygonal structure can be realized in Euclidean space. Two models are considered: polygonal linkages (body-and-joint framework) and contact graphs of unit disks in the plane. (1) We show that it is strongly NP-hard to decide whether a given polygonal linkage is realizable in the plane when the bodies are convex polygons and their contact graph is a tree; the problem is weakly NP-hard already for a chain of rectangles. (2) We also show that it is strongly NP-hard to decide whether a given tree is the contact graph of interior-disjoint unit disks in the plane. </font> </span></li> </ul> </li> <br> <li> <b><a href="http://dx.doi.org/10.1016/j.tcs.2016.03.007">On the number of anchored rectangle packings for a planar point set</a></b>, <ul type="circle"> <li>Kevin Balas and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://cocoon2015.bjut.edu.cn/home.html">21st Computing and Combinatorics Conference</a> (Beijing, 2015)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-319-21398-9_30">9198</a>, Springer, 2015, pp. 377-389.</li> <li><a href="http://dx.doi.org/10.1016/j.tcs.2016.03.007">Theoretical Computer Science</a> <b>654</b> (2016), 143 154.</li> <li> <span onmouseover="anchorcount.style.display=''" onmouseout="anchorcount.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="anchorcount" style="display: none;"><font size="-1"> We consider packing axis-aligned rectangles <i>r<sub>1</sub>,... , r<sub>n</sub></i> in the unit square [0,1]<sup>2</sup> such that a vertex of each rectangle <i>r<sub>i</sub></i> is a given point <i>p<sub>i</sub></i> (i.e., <i>r<sub>i</sub></i> is <b>anchored</b> at <i>p<sub>i</sub></i>); and explore the combinatorial structure of all locally maximal configurations. When the given points are lower-left corners of the rectangles, then the number of maximal packings is shown to be at most 2<i><sup>n</sup>C<sub>n</sub></i>, where <i>C<sub>n</sub></i> is the <i>n</i>th Catalan number. The number of maximal packings remains exponential in <i>n</i> when the points may be arbitrary corners of the rectangles. Our upper bounds are complemented with exponential lower bounds. </font> </span></li> </ul> </li> <br> <li> <b><a href="http://arxiv.org/abs/1411.1303">Convex polygons in geometric triangulations</a></b>, <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.wads.org/">WADS</a> (Victoria, BC, 2015)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-319-21840-3_24">9214</a>, Springer, 2015, pp. 289-300.</li> <li><a href="https://doi.org/10.1017/S0963548317000141">Combinatorics, Probability, and Computing</a> <b>26</b> (5) (2017), 641-659.</li> <li> <span onmouseover="cxintri.style.display=''" onmouseout="cxintri.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="cxintri" style="display: none;"><font size="-1"> We show that the maximum number of convex polygons in a triangulation of <i>n</i> points in the plane is O(1.5029<sup><i>n</i></sup>). This improves an earlier bound of O(1.6181<sup><i>n</i></sup>) established by van Kreveld, L&ouml;ffler, and Pach (2012) and almost matches the current best lower bound of &Omega;(1.5028<sup><i>n</i></sup>) due to the same authors. Given a planar straight-line graph <i>G</i> with <i>n</i> vertices, we show how to compute efficiently the number of convex polygons in <i>G</i>. </font> </span></li> </ul> </li> <br> <li> <b><a href="http://dx.doi.org/10.1007/978-3-642-27848-8_511-1">Binary Space Partitions</a></b>, <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. T&oacute;th,</li> <li>in <i>Encyclopedia of Algorithms </i> (Ming-Yang Kao, ed.), 2nd edition, 2015, Springer.</li> </ul> </li> <br> <li> <b><a href="https://arxiv.org/abs/1611.02541">Arc diagrams, flip distances, and Hamiltonian triangulations</a></b>, <ul type="circle"> <li>Jean Cardinal, Michael Hoffmann, Vincent Kusters, Csaba D. T&oacute;th, and Manuel Wettstein,</li> <li>in <i>Proc. <a href="http://www14.in.tum.de/STACS2015/">32nd Sympos. Theoretical Aspects of Computer Science</a> (Munich, 2015)</i>, <a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2015.197">LIPIcs 30</a>, pp. 197-210.</li> <li><a href="https://doi.org/10.1016/j.comgeo.2017.06.001">Computational Geometry: Theory and Applications</a> <b>68</b> (2018), 206-225.</li> <li> <span onmouseover="arcdiagram.style.display=''" onmouseout="arcdiagram.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="arcdiagram" style="display: none;"><font size="-1"> We show that every triangulation (maximal planar graph) on <i>n</i>&ge; 6 vertices can be flipped into a Hamiltonian triangulation using a sequence of less than <i>n</i>/2 combinatorial edge flips. The previously best upper bound uses 4-connectivity as a means to establish Hamiltonicity. But in general about 3<i>n</i>/5 flips are necessary to reach a 4-connected triangulation. Our result improves the upper bound on the diameter of the combinatorial flip graph of triangulations on <i>n</i> vertices from 5.2<i>n</i>-33.6 to 5<i>n</i>-23. We also show that for every triangulation on <i>n</i> vertices there is a simultaneous flip of less than 2<i>n</i>/3 edges to a 4-connected triangulation. The bound on the number of edges is tight, up to an additive constant. As another application we show that every planar graph on <i>n</i> vertices admits an arc diagram with less than <i>n</i>/2 biarcs, that is, after subdividing less than <i>n</i>/2 (of potentially 3<i>n</i>-6) edges the resulting graph admits a 2-page book embedding. </font> </span></li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1406.2726">Disjoint edges in topological graphs and the tangled-thrackle conjecture</a></b>, <ul type="circle"> <li>Andres J. Ruiz-Vargas, Andrew Suk, and Csaba D. T&oacute;th</li> <li>in <i>Proc. <a href="http://lamut.informatik.uni-wuerzburg.de/">22nd Sympos. Graph Drawing</a> (W&uuml;rzburg, 2014)</i>, LNCS <a href="http://dx.goi.org/10.1007/978-3-662-45803-7_24">8871</a>, Springer, pp. 284-293.</li> <li><a href="http://dx.doi.rg/10.1016/j.ejc.2015.07.004">European J. Combinatorics</a> <b>51</b> (2016), 398 406.</li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1401.6070">On fence patrolling by mobile agents</a></b>, <ul type="circle"> <li>Adrian Dumitrescu, Anirban Ghosh, and Csaba D. T&oacute;th,</li> <li>preliminary version in <i>Proc. 25th Canadian Conference on Computational Geometry (Waterloo, ON, 2013)</i>.</li> <li><a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/4063">Electronic Journal of Combinatorics</a> <b>21</b> (3) (2014), P3.4.</li> <li> <span onmouseover="fence.style.display=''" onmouseout="fence.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="fence" style="display: none;"><font size="-1"> Suppose that a fence needs to be protected (perpetually) by <i>k</i> mobile agents with maximum speeds <i>v<sub>1</sub>,...,v<sub>k</sub></i> so that no point on the fence is left unattended for more than a given amount of time. The problem is to determine if this requirement can be met, and if so, to design a suitable patrolling schedule for the agents. Alternatively, one would like to find a schedule that minimizes the idle time, that is, the longest time interval during which some point is not visited by any agent. We revisit this problem, introduced by Czyzowicz et al. (2011), and discuss several strategies for the cases where the fence is an open and a closed curve, respectively.<br> In particular: (i) we disprove a conjecture by Czyzowicz et al. regarding the optimality of their Algorithm <i>A<sub>2</sub></i> for unidirectional patrolling of a closed fence; (ii) we present an algorithm with a lower idle time for patrolling an open fence, improving an earlier result of Kawamura and Kobayashi. </font> </span></li> </ul> </li> <br> <li><b><a href="https://projects.cs.dal.ca/cccg2014/proceedings/papers/paper45.pdf">Covering grids by trees</a></b>, <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="https://projects.cs.dal.ca/cccg2014/">26th Canadian Conference on Computational Geometry</a> (Halifax, NS, 2014)</i>.</li> <li> <span onmouseover="cccg14.style.display=''" onmouseout="cccg14.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="cccg14" style="display: none;"><font size="-1"> Given <i>n</i> points in the plane, a <i>covering tree</i> is a tree whose edges are line segments that jointly cover all the points. Let <i>G</i><sup>d</sup><sub style='position: relative; left: -.5em;'>n</sub> be a <i>n &times;... &times; n</i> grid in <b>Z</b><sup>d</sup>. It is known that <i>G</i><sup>3</sup><sub>n</sub> can be covered by an axis-aligned polygonal path with (3/2)<i>n</i><sup>2</sup>+O(<i>n</i>) edges, thus in particular by a polygonal tree with that many edges. Here we show that every covering tree for the <i>n</i><sup>3</sup> points of <i>G</i><sup>3</sup><sub style='position: relative; left: -.5em;'>n</sub> has at least (1+c<sub>3</sub>)<i>n</i><sup>2</sup> edges, for some constant c<sub>3</sub>>0. On the other hand, there exists a covering tree for the <i>n</i><sup>3</sup> points of <i>G</i><sup>3</sup><sub style='position: relative; left: -.5em;'>n</sub> consisting of only <i>n</i><sup>2</sup>+<i>n</i>+1 line segments, where each segment is either a single edge or a sequence of collinear edges. Extensions of these problems to higher dimensional grids (i.e., <i>G</i><sup>d</sup><sub style='position: relative; left: -.5em;'>n</sub>for <i>d</i> &ge; 3) are also examined. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/math/0305283">The Szemer&eacute;di-Trotter Theorem in the complex plane</a></b>, <ul type="circle"> <li>Csaba D. T&oacute;th,</li> <li><a href="http://dx.doi.org/10.1007/s00493-014-2686-2">Combinatorica</a> <b>35</b> (1) (2015), 95-126.</li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.128">Computing opaque interior barriers &agrave; la Shermer</a></b>, <ul type="circle"> <li>Adrian Dumitrescu, Minghui Jiang, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://cui.unige.ch/tcs/random-approx/2014/">17th APPROX</a> (Barcelona, 2014)</i>, LIPIcs 28, Dagstuhl, pp. 128-143.</li> <li><a href="http://dx.doi.org/10.1137/14098805X">SIAM Journal on Discrete Mathematics</a> <b>29</b> (3) (2015), 1372 1386.</li> <li> <span onmouseover="Shermer.style.display=''" onmouseout="Shermer.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="Shermer" style="display: none;"><font size="-1"> The problem of finding a collection of curves of minimum total length that meet all the lines intersecting a given polygon was initiated by Mazurkiewicz in 1916. Such a collection forms an <i>opaque barrier</i> for the polygon. In 1991 Shermer proposed an exponential-time algorithm that computes an interior-restricted barrier made of segments for any given convex <i>n</i>-gon. He conjectured that the barrier found by his algorithm is optimal, however this was refuted recently by Provan et al. Here we give a Shermer like algorithm that computes an interior polygonal barrier whose length is at most 1.7168 times the optimal and that runs in O(<i>n</i>) time. As a byproduct, we also deduce upper and lower bounds on the approximation ratio of Shermer's algorithm. </font> </span></li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1402.5303">Diffuse reflection radius in a simple polygon</a></b>, <ul type="circle"> <li>Eli Fox-Epstein, Csaba D. T&oacute;th, and Andrew Winslow</li> <li>in <i>Proc. <a href="http://www.cs.gsu.edu/COCOON2014/">20th Computing and Combinatorics Conference</a> (Atlanta, GA, 2014)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-319-08783-2_21">8591</a>, Springer, pp. 239-250.</li> <li><a href="http://dx.doi.org/10.1007/s00453-015-0031-9">Algorithmica</a> <b>76</b> (4) (2016), 910-931.</li> <li> <span onmouseover="diffuseradius.style.display=''" onmouseout="diffuseradius.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="diffuseradius" style="display: none;"><font size="-1"> It is shown that every simple polygon with <i>n</i> walls can be illuminated from a single point light source <i>s</i> after at most &lfloor;(<i>n</i>-2)/4&rfloor; diffuse reflections, and this bound is the best possible. A point <i>s</i> with this property can be computed in O(<i>n</i> log <i>n</i>) time. </font> </span></li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/bendcount36.pdf">A census of plane graphs with polyline edges</a></b>, <ul type="circle"> <li>Andrea Francke and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.dais.is.tohoku.ac.jp/~socg2014/">30th Sympos. on Computational Geometry</a> (Kyoto, 2014)</i>, ACM Press, pp. 242-250.</li> <li><a href="https://doi.org/10.1137/15M1046484">SIAM J. Discrete Math.</a> <b>31</b> (2) (2017), 1174-1195.</li> <li> <span onmouseover="bendcount.style.display=''" onmouseout="bendcount.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="bendcount" style="display: none;"><font size="-1"> It is shown that on every <i>n</i>-element point set in the plane, at most exp(O(<i>kn</i>)) labeled planar graphs can be embedded using polyline edges with <i>k</i> bends per edge. This is the first exponential upper bound for the number of labeled plane graphs where the edges are polylines of constant size. Several standard tools developed for the enumeration of straight-line graphs, such as triangulations and crossing numbers, are unavailable in this scenario. Furthermore, the exponential upper bound does not carry over to other popular relaxations of straight-line edges: for example, the number of plane graphs realizable with <i>x</i>-monotone edges on <i>n</i> points is already super-exponential. </font> </span></li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/edgelength60.pdf">Free edge lengths in plane graphs</a></b>, <ul type="circle"> <li>Zachary Abel, Robert Connelly, Sarah Eisenstat, Radoslav Fulek, Filip Mori&#263, Yoshio Okamoto, Tibor Szab&oacute;, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.dais.is.tohoku.ac.jp/~socg2014/">30th Sympos. on Computational Geometry </a> (Kyoto, 2014)</i>, ACM Press, pp. 426-435.</li> <li><a href="http://dx.doi.org/10.1007/s00454-015-9704-z">Discrete and Computational Geometry</a> <b>54</b> (1) (2015), 259-289.</li> <li> <span onmouseover="edgelengths.style.display=''" onmouseout="edgelengths.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="edgelengths" style="display: none;"><font size="-1"> We study straight-line embeddings of planar graphs subject to metric constraints. A planar graph <i>G</i> is <i>free</i> in a planar ``host'' graph <i>H</i>, <i>G</i>&sube;<i>H</i>, if the edges if <i>G</i> have arbitrary positive lengths, that is, for any choice of positive lengths for the edges of <i>G</i>, the host <i>H</i> has a straight-line embedding that realizes these lengths. A planar graph <i>G</i> is <i>extrinsically free</i> in <i>H</i>, <i>G</i>&sube;<i>H</i>, if any constraint on the edge lengths of <i>G</i> depends on <i>G</i> alone, irrespective of any additional edges of the host <i>H</i>. We characterize all planar graphs <i>G</i> that are free in every host <i>H</i>, <i>G</i>&sube;<i>H</i>, and all the planar graphs <i>G</i> that are extrinsically free in every host <i>H</i>, <i>G</i>&sube;<i>H</i>. The case of cycles <i>G=C<sub>k</sub></i> provides a new version of the celebrated carpenter's rule problem. Even though cycles <i>C<sub>k</sub></i>, <i>k &ge; 4</i>, are not extrinsically free in all triangulations, it turns out that ``nondegenerate'' edge lengths are always realizable, where the edge lengths are considered degenerate if the cycle can be flattened (into a line) in two different ways. Separating triangles, and separating cycles in general, play an important role in our arguments. We show that every star is free in a 4-connected triangulation (which has no separating triangle). </font> </span></li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1312.4429">The flip diameter of rectangulations and convex subdivisions</a></b>, <ul type="circle"> <li>Eyal Ackerman, Michelle M. Allen, Gill Barequet, Maarten L&ouml;ffler, Joshua Mermelstein, Diane L. Souvaine, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.fing.edu.uy/eventos/latin2014">Latin American Theoretical INformatics</a> (Montevideo, 2014)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-54423-1_42">8392</a>, Springer, 2014, pp. 478-489.</li> <li><a href="http://dmtcs.episciences.org/1413">Discrete Mathematics and Theoretical Computer Science</a> <b>18</b> (3) (2016), article 4.</li> <li> <span onmouseover="floorflip.style.display=''" onmouseout="floorflip.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="floorflip" style="display: none;"><font size="-1"> We study the configuration space of rectanulations and convex subdivisions of <i>n</i> points in the plane. It is shown that a sequence of O(<i>n</i> log <i>n</i>) elementary <i>flip</i> and <i>rotate</i> operations can transform any rectangulation to any other rectangulation on the same set of <i>n</i> points. This bound is the best possible for some point sets, while &Theta;(<i>n</i>) operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of <i>n</i> points in the plane. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1007/978-3-319-03841-4_1">On the upward planarity of mixed plane graphs</a></b>, <ul type="circle"> <li>Fabrizio Frati, Michael Kaufmann, J&aacute;nos Pach, Csaba D. T&oacute;th, and David Wood,</li> <li>in <i>Proc. <a href="http://gd2013.labri.fr/">21st Symposium on Graph Drawing</a> (Bordeaux, 2013)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-319-03841-4_1">8242</a>, Springer, pp 1-12.</li> <li><a href="http://dx.doi.org/10.7155/jgaa.00322">J. Graph Algorithms and Applications</a> <b>18</b> (2) (2014), 253-279.</li> <li> <span onmouseover="mixed.style.display=''" onmouseout="mixed.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="mixed" style="display: none;"><font size="-1"> A <i>mixed plane graph</i> is a plane graph whose edge set is partitioned into a set of directed edges and a set of undirected edges. An <i>orientation</i> of a mixed plane graph <i>G</i> is an assignment of directions to the undirected edges of <i>G</i> resulting in a directed plane graph <i>G'</i>. In this paper, we study the computational complexity of testing whether a given mixed plane graph <i>G</i> is <i>upward planar</i>, i.e., whether it admits an orientation resulting in a directed plane graph <i>G'</i> such that <i>G'</i> admits a planar drawing in which each edge is represented by a curve monotonically increasing in the <i>y</i>-direction according to its orientation. Our contribution is threefold. First, we show that the upward planarity testing problem is solvable in cubic time for <i>mixed outerplane graphs</i>. Second, we show that the problem of testing the upward planarity of mixed plane graphs reduces in quadratic time to the problem of testing the upward planarity of <i>mixed plane triangulations</i>. Third, we exhibit linear-time testing algorithms for two classes of mixed plane triangulations, namely <i>mixed plane 3-trees</i> and mixed plane triangulations in which <i>the undirected edges induce a forest</i>. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/EdgePacking50.pdf">On the total perimeter of homothetic convex bodies in a convex container</a></b>,<br> <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. T&oacute;th,</li> <li>preliminary version: "Packing disks that touch the boundary of a square" in <i>Abstracts of <a href="www.umiacs.umd.edu/conferences/fwcg2012/">22nd Fall Workshop on Computational Geometry</a> (College Park, MD, 2012).</i></li> <li>in <i>Proc. <a href="http://cui.unige.ch/tcs/random-approx/2013/index.php">16th APPROX</a> (Berkeley, CA, 2013)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-40328-6_8">8096</a>, Springer, pp. 96-109.</li> <li><a href="http://dx.doi.org/10.1007/s13366-014-0219-1">Contributions to Algebra and Geometry</a> <b>56</b> (2) (2015), 515-532.</li> <li> <span onmouseover="perimeter.style.display=''" onmouseout="perimeter.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="perimeter" style="display: none;"><font size="-1"> For two convex bodies, <i>C</i> and <i>D</i>, consider a packing <i>S</i> of <i>n</i> positive homothets of <i>C</i> contained in <i>D</i>. We estimate the total perimeter of the bodies in <i>S</i>, denoted per(<i>S</i>), in terms of <i>n</i>. When all homothets of <i>C</i> touch the boundary of the container <i>D</i>, we show that either per(<i>S</i>)=O(log <i>n</i>) or per(<i>S</i>)=O(<i>1</i>), depending on how <i>C</i> and <i>D</i> "fit together,"' and these bounds are the best possible apart from the constant factors. Specifically, we establish an optimal bound per(<i>S</i>)=O(log <i>n</i>) unless <i>D</i> is a convex polygon and every side of <i>D</i> is parallel to a corresponding segment on the boundary of <i>C</i> (for short, <i>D</i> is <i>parallel to C</i>). When <i>D</i> is parallel to <i>C</i> but the homothets of <i>C</i> may lie anywhere in <i>D</i>, we show that per(<i>S</i>)=O((1+esc(<i>S</i>)) log <i>n</i>/log log <i>n</i>), where esc(<i>S</i>) denotes the total distance of the bodies in <i>S</i> from the boundary of <i>D</i>. Apart from the constant factor, this bound is also the best possible. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1702.01277">Geometric biplane graphs II: Graph augmentation</a></b>, <ul type="circle"> <li>Alfredo Garc&iacute;a, Ferran Hurtado, Matias Korman, In&ecirc;s Matos, Maria Saumell, Rodrigo I. Silveira, Javier Tejel, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.matem.unam.mx/jorgefest/">Mexican Conf. on Discrete Math. and Computational Geometry</a> (Oaxaca, 2013)</i>.</li> <li><a href="http://dx.doi.org/10.1007/s00373-015-1547-0">Graphs and Combinatorics</a> <b>31</b> (2) (2015), 427-452.</li> <li> <span onmouseover="biplane2.style.display=''" onmouseout="biplane2.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="biplane2" style="display: none;"><font size="-1"> We study biplane graphs drawn on a finite point set <i>S</i> in the plane in general position. This is the family of geometric graphs whose vertex set is <i>S</i> and can be decomposed into two plane graphs. We show that every sufficiently large point set admits a 5-connected biplane graph and that there are arbitrarily large point sets that do not admit any 6-connected biplane graph. Furthermore, we show that every plane graph (other than the wheel or the fan) can be augmented into a 4-connected biplane graph. However, there are arbitrarily large plane graphs that cannot be augmented to a 5-connected biplane graph by adding pairwise noncrossing edges. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1702.01275">Geometric biplane graphs I: Maximal graphs</a></b>, <ul type="circle"> <li>Alfredo Garc&iacute;a, Ferran Hurtado, Matias Korman, In&ecirc;s Matos, Maria Saumell, Rodrigo I. Silveira, Javier Tejel, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.matem.unam.mx/jorgefest/">Mexican Conf. on Discrete Math. and Computational Geometry</a> (Oaxaca, 2013)</i>.</li> <li><a href="http://dx.doi.org/10.1007/s00373-015-1546-1">Graphs and Combinatorics</a> <b>31</b> (2) (2015), 407-425.</li> <li> <span onmouseover="biplane1.style.display=''" onmouseout="biplane1.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="biplane1" style="display: none;"><font size="-1"> We study biplane graphs drawn on a finite point set <i>S</i> in the plane in general position. This is the family of geometric graphs whose vertex set is <i>S</i> and can be decomposed into two plane graphs. We show that two maximal biplane graphs in the sense that no edge can be added while staying biplane may differ in the number of edges, and we provide an efficient algorithm for adding edges to a biplane graph to make it maximal. We also study extremal properties of maximal biplane graphs such as the maximum number of edges and the largest maximum connectivity over <i>n</i>-element point sets. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1410.1579">Counting carambolas</a></b>, <ul type="circle"> <li>Maarten L&ouml;ffler, Andr&eacute; Schulz, and Csaba D. T&oacute;th,</li> <li>in <i><a href="https://cs.uwaterloo.ca/conferences/cccg2013/proceedings.pdf">Proc. 25th Canadian Conf. on Comput. Geom.</a> (Waterloo, ON, 2013)</i>, pp. 163-168.</li> <li><a href="http://dx.doi.org/10.1007/s00373-015-1621-7">Graphs and Combinatorics</a> <b>32</b> (3) (May, 2016), 923-942.</li> <li> <span onmouseover="carambolas.style.display=''" onmouseout="carambolas.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="carambolas" style="display: none;"><font size="-1"> We give upper and lower bounds on the maximum and minimum number of certain geometric configurations hidden in a triangulation of <i>n</i> points in the plane. Configurations of interest include <i>star-shaped polygons</i> and <i>monotone paths</i>. We also consider related problems in <i>directed</i> planar straight-line graphs. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/curvilinear_cgta.pdf">A tight bound for point guards in piece-wise convex art galleries</a>,</b> <ul type="circle"> <li><a href="http://www.fciencias.unam.mx/directorio/66198">Javi&eacute;r Cano</a>, Csaba D. T&oacute;th, and <a href="http://www.matem.unam.mx/urrutia/">Jorge Urrutia</a>,</li> <li>in <i>Abstracts of the <a href="http://www.cs.tufts.edu/research/geometry/FWCG09/">19th Fall Workshop on Comput. Geom.</a> (Medford, MA, 2009)</i>, pp. 43-44.</li> <li><a href="http://dx.doi.org/10.1016/j.comgeo.2013.04.004">Comput. Geom. Theory Appl.</a> <b>46</b> (8) (2013), 945 958.</li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1007/978-3-642-40104-6_31">Planar packing of binary trees</a></b>,<br> <ul type="circle"> <li><a href="http://algo.inf.uni-tuebingen.de/?site=mitarbeiter/markusgeyer/index">Markus Geyer</a>, <a href="http://algo.inf.uni-tuebingen.de/?site=mitarbeiter/michaelkaufmann/index">Michael Kaufmann</a>, <a href="http://www.inf.ethz.ch/~hoffmann">Michael Hoffmann</a>, <a href="http://vincentkusters.org/">Vincent Kusters</a>, Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.wads.org/">WADS</a> (London, ON, 2013)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-40104-6_31">8037</a>, Springer, pp. 353 364.</li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1212.6148">Universal point sets for planar three-trees</a>,</b> <ul type="circle"> <li><a href="http://dcg.epfl.ch/page-18454.html">Radoslav Fulek</a> and Csaba D. T&oacute;th,</li> <li>preliminary version in <i>Proc. <a href="http://www.wads.org/">WADS</a> (London, ON, 2013)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-40104-6_30">8037</a>, Springer, pp. 341 352.</li> <li><a href="http://dx.doi.org/10.1016/j.jda.2014.12.005">Journal of Discrete Algorithms</a> <b>30</b> (2015), 101-112.</li> <li> <span onmouseover="universal.style.display=''" onmouseout="universal.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="universal" style="display: none;"><font size="-1"> For every positive integer <i>n</i>, we present a set <i>S<sub>n</sub></i> of O(<i>n</i><sup>3/2</sup>log <i>n</i>) points in the plane such that every planar 3-tree with <i>n</i> vertices has a straight-line embedding in the plane in which the vertices are mapped to a subset of <i>S<sub>n</sub></i>. This is the first subquadratic upper bound on the size of universal point sets for planar 3-trees, as well as for the class of 2-trees and serial parallel graphs. </font> </span></li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/colored-encom.pdf">Vertex-colored encompassing graphs</a>,</b> <ul type="circle"> <li><a href="http://www.inf.ethz.ch/~hoffmann">Michael Hoffmann</a> and Csaba D. T&oacute;th,</li> <li><a href="http://dx.doi.org/10.1007/s00373-013-1320-1">Graphs and Combinatorics</a> <b>30</b> (4) (2014), 933-947.</li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1302.2271">Diffuse reflections in simple polygons</a></b>,<br> <ul type="circle"> <li><a href="www.cs.technion.ac.il/~barequet/">Gill Barequet</a>, <a href="http://www.eecs.tufts.edu/~scanno01/">Sarah M. Cannon</a>, Eli Fox-Epstein, <a href="www.cs.tufts.edu/~hescott/">Benjamin Hescott</a>, <a href="http://www.cs.tufts.edu/~dls/">Diane L. Souvaine</a>, Csaba D. T&oacute;th, and <a href="http://www.eecs.tufts.edu/~awinslow/">Andrew Winslow</a>,</li> <li>in <i>Proc. <a href="http://xamanek.izt.uam.mx/LAGOS2013/">VII Latin-American Algorithms, Graphs and Optimization Symposium</a> (Playa del Carmen, 2013)</i>, <a href="http://dx.doi.org/10.1016/j.endm.2013.10.054">Electronic Notes in Discrete Mathematics</a> <b>44</b> (5) (2013), 345 350.</li> <li><a href="http://dx.doi.org/10.1016/j.dam.2015.04.025">Discrete Applied Mathematics</a> <b>210</b> (2016), 123-132.</li> <li> <span onmouseover="diffuse.style.display=''" onmouseout="diffuse.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="diffuse" style="display: none;"><font size="-1"> We prove a conjecture of Aanjaneya et al. that the maximum number of <i>diffuse reflections</i> needed for a point light source to illuminate the interior of simple polygon with <i>n</i> walls is floor(<i>n</i>/2)-1. Light reflecting diffusely leaves a surface in all directions, rather than at an identical angle as with specular reflections. </font> </span></li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1303.6659">The traveling salesman problem for lines, balls and planes</a>,</b> <ul type="circle"> <li><a href="http://www.cs.uwm.edu/faculty/ad/">Adrian Dumitrescu</a> and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.siam.org/meetings/da13/">24th ACM-SIAM Symposium on Discrete Algorithms</a> (New Orleans, LA, 2013)</i>, SIAM, pp. 828-843.</li> <li><a href="http://dx.doi.org/10.1145/2850418">Transactions on Algorithms</a> <b>12</b> (3) (2016), article 43.</li> <li> <span onmouseover="tspn.style.display=''" onmouseout="tspn.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="tspn" style="display: none;"><font size="-1"> We revisit the traveling salesman problem with neighborhoods (TSPN) and obtain several approximation algorithms. These constitute either improvements over previously best approximations achievable in comparable times (for unit disks in the plane), or first approximations ever (for planes, lines and unit balls in 3-space).<br> (I) Given a set of <i>n</i> planes in 3-space, a TSP tour that is at most 2.31 times longer than the optimal can be computed in O(<i>n</i>) time.<br> (II) Given a set of <i>n</i> lines in 3-space, a TSP tour that is at most O(log<sup>3</sup><i>n</i>) times longer than the optimal can be computed in polynomial time.<br> (III) Given a set of <i>n</i> unit disks in the plane (resp., unit balls in 3-space), we improve the approximation ratio using a black box that computes an approximate tour for a set of points (the centers of a subset of disks).</font> </span></li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1303.0262">Covering paths for planar point sets</a>,</b> <ul type="circle"> <li><a href="http://www.cs.uwm.edu/faculty/ad/">Adrian Dumitrescu</a>, <a href="http://www.renyi.hu/~gerbner/">D&aacute;niel Gerbner</a>, <a href="http://www.renyi.hu/~keszegh/">Bal&aacute;zs Keszegh</a>, Csaba D. T&oacute;th,</li> <li>preliminary version in <i>Proc. <a href="http://www.gd2012.org/">20th Symposium on Graph Drawing</a> (Redmond, WA, 2012)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-36763-2_27">7704</a>, Springer, 2013, pp. 303 314.</li> <li><i>Proc. <a href="http://www.cs.bme.hu/~jh2013/">8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications</a> (Veszpr&eacute;m, 2013)</i>.</li> <li><a href="http://dx.doi.org/10.1007/s00454-013-9563-4">Discrete Comput. Geom.</a> <b>51</b> (2) (2014), 462-484.</li> <li> <span onmouseover="coveringpaths.style.display=''" onmouseout="coveringpaths.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="coveringpaths" style="display: none;"><font size="-1"> Given a set of points, a <i>covering path</i> is a directed polygonal path that visits all the points. If no three points are collinear, every covering path requires at least <i>n</i>/2 segments, and <i>n-1</i> straight line segments obviously suffice even if the covering path is required to be noncrossing. We show that for any <i>n</i> points in the plane, there exists a (possibly self-crossing) covering path consisting of <i>n</i>/2 +O(<i>n</i>/log <i>n</i>) straight line segments. If the path is required to be noncrossing, we prove that (1-&epsilon;)<i>n</i> straight line segments suffice for a small constant &epsilon;>0, and we exhibit <i>n</i>-element point sets that require at least 5<i>n</i>/9 -O(1) segments in any such path. Further, we show that computing a non-crossing covering path for <i>n</i> points in the plane requires &Omega;(<i>n</i> log <ui>n</i>) time in the worst case.</font> </span></li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/PolyhedralEdgeGuards14.pdf">Edge guards for polyhedra in three-space</a>,</b> <ul type="circle"> <li>Javi&eacute;r Cano, Csaba D. T&oacute;th, and <a href="http://www.math.unam.mx/~urrutia/">Jorge Urrutia</a>,</li> <li>in <i>Proc. <a href="http://2012.cccg.ca/">24th Canadian Conf. Comput. Geom.</a> (Charlottetown, PE, 2012)</i>, pp. 155-160.</li> </ul> </li> <br> <li><b><a href="http://jgaa.info/getPaper?id=329">Crossing angles of geometric graphs</a>,</b> <ul type="circle"> <li>Karin Arikushi and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.cocoa2012.ca/">6th Conference on Combinatorial Optimization and Applications</a> (Banff, AB, 2012)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-31770-5_10">7402</a>, Springer, pp. 103-114.</li> <li><a href="http://jgaa.info/">J. Graph Algorithms and Applications</a> <b>18</b> (3) (2014), 401-420. <li> <span onmouseover="crossingangles.style.display=''" onmouseout="crossingangles.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="crossingangles" style="display: none;"><font size="-1"> The <i>crossing angle number</i> of a graph <i>G</i>, denoted can(<i>G</i>) is the minimum number of angles between crossing edges in a straight line drawing of <i>G</i>. It is shown that an <i>n</i>-vertex graph <i>G</i> with can(<i>G</i>) = O(1) has O(<i>n</i>) edges, but there are bounded degree graphs <i>G</i> with arbitrarily large can(<i>G</i>). There are bounded degree graphs <i>G = (V,E)</i> such that for any two straight-line drawings of <i>G</i> with the same prescribed crossing angles, there is a subset <i>U</i> of <i>V</i>, of vertices of size <i>|U|&ge;|V|/2</i> whose two drawings are similar. </font> </span></li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/monotonepath26.pdf">Monotone paths in convex subdivisions and polytopes</a>,</b> <ul type="circle"> <li><a href="http://www.cs.uwm.edu/faculty/ad/">Adrian Dumitrescu</a>, <a href="http://page.mi.fu-berlin.de/rote/">G&uuml;nter Rote</a>, and Csaba D. T&oacute;th,</li> <li>preliminary results in <i>Abstracts of the <a href="http://www-cs.engr.ccny.cuny.edu/~peter/fwcg11/">21st Fall Workshop on Comput. Geom.</a> (New York, NY, 2011)</i>.</li> <li>in <i>Proc. <a href="http://cocoon.it.usyd.edu.au/">18th Computing and Combinatorics Conference</a> (Sydney, 2012)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-32241-9_21">7434</a>, Springer, pp. 240?251.</li> <li>in <a href="http://www.springer.com/mathematics/geometry/book/978-3-319-00199-9">Discrete Geometry and Optimization</a>, vol 69 of Fields Institute Communications, 2013, Springer, pp. 79-104.</li> <li> <span onmouseover="monotonepath.style.display=''" onmouseout="monotonepath.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="monotonepath" style="display: none;"><font size="-1"> It is shown that for every subdivision of the plane into <i>n</i> convex faces, exactly <k>k</i> of which are unbounded, there is a monotone polygonal path on the boundaries of the faces that consists of at least &Omega;(log (<i>n</i>/<i>k</i>)/log log (<i>n</i>/<i>k</i>)) segments, and this bound is the best possible. </font> </span></li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1112.1124">Minimum convex partitions and maximum empty polytopes</a>,</b> <ul type="circle"> <li><a href="http://www.cs.uwm.edu/faculty/ad/">Adrian Dumitrescu</a>, <a href="valis.cs.uiuc.edu/~sariel/">Sariel Har-Peled</a>, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://swat2012.helsinki.fi/">13th Scandinavian Symposium and Workshops on Algorithm Theory</a> (Helsinki, 2012)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-31155-0_19">7357</a>, Springer, pp. 213-224.</li> <li><a href="http://jocg.org/index.php/jocg/article/view/112">Journal of Computational Geometry</a> <b>5</b> (1) (2014), 86 103.</li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1203.3256">Conflict-free graph orientations with parity constraints</a>,</b> <ul type="circle"> <li><a href="http://www.eecs.tufts.edu/~scanno01/">Sarah Cannon</a>, <a href="http://www.eecs.tufts.edu/~mishaq01/">Mashhood Ishaque</a>, and Csaba D. T&oacute;th,</li> <li>preliminary results "<a href="http://csabatoth.org/EvenOrientations.pdf">Even orientations with forbidden pairs and demands</a>" in the <i>Abstracts of the <a href="http://www.ams.sunysb.edu/~jsbm/fwcg-2010.html">20th Fall Workshop on Comput. Geom.</a> (Stony Brook, NY, 2010)</i>.</li> <li>in <i>Proc. <a href="http://www.dsi.unive.it/~fun2012/">6th Conf. on Fun with Algorithms</a> (Venice, 2012)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-30347-0_9">7288</a>, Springer, pp. 57-68.</li> <li> <span onmouseover="evenorientation.style.display=''" onmouseout="evenorientation.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="evenorientation" style="display: none;"><font size="-1"> It is known that every multigraph with an even number of edges has an even orientation (i.e., all indegrees are even). We study parity constrained graph orientations under additional constraints. We consider three types of constraints for a multigraph <i>G=(V,E)</i>: (1) an <i>exact conflict</i> is an edge set <i>C&sube; E</i> and a vertex <i>v&isin; V</i> such that <i>C</i> should not equal the set of incoming edges at <i>v</i>; (2) a <i>subset conflict</i>is an edge set <i>C&sube; E</i> and a vertex <i>v&isin; V</i> such that <i>C</i> should not be a subset of incoming edges at <i>v</i>; (3) a <i>vertex demand</i> <i>f(v),v&isin; V</i>, is a minimum indegree for <i>v</i>. We show that it is NP-complete to decide whether $G$ has an even orientation with exact or subset conflicts, for all conflict sets of size two or higher. We present efficient algorithms for computing parity constrained orientations with <i>disjoint</i> exact or subset conflict pairs and with demands.</font> </span></li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1107.5102">Packing anchored rectangles</a>,</b> <ul type="circle"> <li><a href="http://www.cs.uwm.edu/faculty/ad/">Adrian Dumitrescu</a> and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.siam.org/meetings/da12/">23rd ACM-SIAM Sympos. on Discrete Algorithms</a> (Kyoto, 2012)</i>, SIAM, 2012, pp. 294-305.</li> <li><a href="http://dx.doi.org/10.1007/s00493-015-3006-1">Combinatorica</a> <b>35</b> (1) (2015), 39-61.</li> <li> <span onmouseover="anchored.style.display=''" onmouseout="anchored.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="anchored" style="display: none;"><font size="-1"> Let <i>S</i> be a set of <i>n</i> points in the unit square [0,1]<sup>2</sup>, one of which is the origin. We construct <i>n</i> pairwise interior-disjoint axis-aligned empty rectangles such that the lower-left corner of each rectangle is a point in <i>S</i>, and the rectangles jointly cover at least a positive constant area. This is a first step towards the solution of a longstanding conjecture that the rectangles in such a packing can jointly cover an area of at least 1/2. </font> </span></li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/AugmSurvey.pdf">Plane geometric graph augmentation: a generic perspective</a>,</b> <ul type="circle"> <li><a href="http://www-ma2.upc.edu/hurtado/">Ferran Hurtado</a> and Csaba D. T&oacute;th,</li> <li>in <i><a href="http://dx.doi.org/10.1007/978-1-4614-0110-0_17">Thirty Essays on Geometric Graph Theory</a> (J. Pach, ed.)</i>, Springer, 2013, pp. 327-354.</li> <li> <span onmouseover="augmentsurvey.style.display=''" onmouseout="augmentsurvey.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="augmentsurvey" style="display: none;"><font size="-1"> Graph augmentation problems are motivated by network design, and have been studied ex- tensively in optimization. We consider augmentation problems over plane geometric graphs, that is, graphs given with a crossing-free straight-line embedding in the plane. The geomet- ric constraints on the possible new edges render some of the simplest augmentation problems intractable, and in many cases only extremal results are known. We survey recent results, highlight common trends, and gather numerous conjectures and open problems. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/3vd16.pdf">Constrained tri-connected planar straight line graphs</a>,</b> <ul type="circle"> <li>Marwan Al-Jubeh, <a href="http://www.cs.technion.ac.il/~barequet/">Gill Barequet</a>, <a href="http://www.eecs.tufts.edu/~mishaq01/">Mashhood Ishaque</a>, <a href="http://www.cs.tufts.edu/~dls/">Diane L. Souvaine</a>, Csaba D. Tth, and <a href="http://www.eecs.tufts.edu/~awinslow/">Andrew Winslow</a>,</li> <li>preliminary results in <i>Abstracts of the <a href="http://www.ams.sunysb.edu/~jsbm/fwcg-2010.html">20th Fall Workshop on Comput. Geom.</a> (Stony Brook, NY, 2010)</i>.</li> <li>preliminary results "Connecting obstacles in vertex-disjoint paths" in <i>Abstracts of the <a href="http://2010.eurocg.org/">26th European Workshop Comput. Geom. (Dortmund, 2010)</a></i>.</li> <li>in <i><a href="http://dx.doi.org/10.1007/978-1-4614-0110-0_5">Thirty Essays on Geometric Graph Theory</a> (J. Pach, ed.)</i>, Springer, 2013, pp. 49-70.</li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/untangling.pdf">Upper bound constructions for untangling planar geometric graphs</a>,</b> <ul type="circle"> <li>Javier Cano, Csaba D. T&oacute;th, and <a href="http://www.math.unam.mx/~urrutia/">Jorge Urrutia</a>,</li> <li>in <i>Proc. <a href="http://www.win.tue.nl/GD2011/">19th Sympos. Graph Drawing</a> (Eindhoven, 2011)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-25878-7_28">7034</a>, Springer, pp. 290-295.</li> <li><a href="http://dx.doi.org/10.1137/130924172">SIAM J. Discrete Math.</a> <b>28</b> (4) (2014), 1935-1943.</li> <li> <span onmouseover="untangling.style.display=''" onmouseout="untangling.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="untangling" style="display: none;"><font size="-1"> For every positive integer <i>n</i>, there is a straight-line drawing <i>D<sub>n</sub></i> of a planar graph on <i>n</i> vertices such that in any <i>crossing-free</i> straight-line drawing of the graph, at most O(<i>n<sup>0.4982</sup></i>) vertices lie at the same position as in <i>D<sub>n</sub></i>. This improves on an earlier bound of O(<i>&radic;n</i>) by Goaoc <i>et al.</i>. </font> </span> </li> </ul> </li> <br> <li><b><a href=""http://2011.cccg.ca/PDFschedule/papers/paper58.pdf">Open guard edges and edge guards in simple polygons</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th, <a href="http://cgm.cs.mcgill.ca/~godfried/">Godfried Toussaint</a>, and <a href="http://www.eecs.tufts.edu/~awinslow/">Andrew Winslow</a>,</li> <li>in <i>Proc. <a href="http://2011.cccg.ca/">23rd Canadian Conf. Comput. Geom.</a> (Toronto, ON, 2011)</i>, pp. 449-454.</li> <li>in <i>Computational Geometry (A. Marquez et al., eds.)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-34191-5_5">7579</a>, Springer, 2012, pp. 54-64.</li> <li> <span onmouseover="openguardedge.style.display=''" onmouseout="openguardedge.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="openguardedge" style="display: none;"><font size="-1"> An <i>open edge</i> of a simple polygon is the set of points in the relative interior of an edge. We revisit several art gallery problems, previously considered for closed edge guards, using open edge guards. A <i>guard edge</i> of a polygon is an edge that sees every point inside the polygon. We show that every simple non-starshaped polygon admits at most one open guard edge, and give a simple new proof that it admits at most three closed guard edges. We characterize open guard edges, and derive an algorithm that finds all open guard edges of a simple <i>n</i>-gon in <i>O(n)</i> time in the RAM model of computation. Finally, we present lower bound constructions for simple polygons with <i>n</i> vertices that require <i>[n/3]</i> open edge guards, and conjecture that this bound is tight. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1105.3078">Collinearities in kinetic points</a>,</b> <ul type="circle"> <li>Ben D. Lund, <a href="http://www.cs.uc.edu/~gpurdy/">George B. Purdy</a>, Justin W. Smith, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://2011.cccg.ca/">23rd Canadian Conf. Comput. Geom.</a> (Toronto, ON, 2011)</i>, pp. 223-227.</li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/SimFlippable+.pdf">Simultaneously flippable edges in triangulations</a>,</b> <ul type="circle"> <li><a href="http://www.cs.tufts.edu/~dls/">Diane L. Souvaine</a>, Csaba D. T&oacute;th, and <a href="http://www.eecs.tufts.edu/~awinslow/">Andrew Winslow</a>,</li> <li>in <i>Proc. <a href="http://www2.uah.es/egc2011/">XIV Spanish Meeting on Comput. Geom.</a> (Alcal&aacute; de Henares, 2011)</i>, pp. 137-140.</li> <li>in <i>Computational Geometry (A. Marquez et al., eds.)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-34191-5_13">7579</a>, Springer, 2012, pp. 138-145.</li> <li><span onmouseover="simultaneous.style.display=''" onmouseout="simultaneous.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="simultaneous" style="display: none;"><font size="-1"> We show that every straight-line triangulation on <i>n</i> vertices contains at least <i>(n - 4)/5</i> simultaneously flippable edges. This bound is the best possible, and resolves an open problem by Galtier <i>et al.</i>. </font> </span></li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1012.0591">Counting plane graphs: flippability and its applications</a>,</b> <ul type="circle"> <li><a href="http://www.inf.ethz.ch/~hoffmann">Michael Hoffmann</a>, <a href="http://cs.uni-muenster.de/u/schulz/">Andr&eacute; Schulz</a>, <a href="http://www.math.tau.ac.il/~michas/">Micha Sharir</a>, <a href="http://www.cs.tau.ac.il/~sheffera/">Adam Sheffer</a>, Csaba D. T&oacute;th, and <a href="http://www.inf.ethz.ch/personal/emo/">Emo Welzl</a>,</li> <li>in <i>Proc. <a href="http://www.wads.org/">WADS</a> (Brooklyn, NY, 2011)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-22300-6_44 ">6844</a>, Springer, pp. 524-535.</li> <li>in <i><a href="http:/dx.doi.org/10.1007/978-1-4614-0110-0_16">Thirty Essays on Geometric Graph Theory</a> (J. Pach, ed.)</i>, Springer, 2013, pp. 303-326.</li> <li> <span onmouseover="psflippable.style.display=''" onmouseout="psflippable.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="psflippable" style="display: none;"><font size="-1"> We generalize the notions of flippable and simultaneously-flippable edges in a triangulation of a set <i>S</i> of points in the plane, into so called pseudo-simultaneously flippable edges. Such edges are related to the notion of convex decompositions spanned by <i>S</i>. We derive a worst-case tight lower bound on the number of pseudo-simultaneously flippable edges in any triangulation, and use this bound to obtain upper bounds for the maximal number of several types of plane graphs that can be embedded (with crossing-free straight edges) on a fixed set of <i>N</i> points in the plane. More specifically, denoting by tr(<i>N</i>) &lt; 30<sup>N</sup> the maximum possible number of triangulations of a set of <i>N</i> points in the plane, we show that every set of <i>N</i> points in the plane can have at most 6.9283<sup>N</sup>&middot;tr(<i>N</i>) &lt; 207.85<sup>N</sup> plane graphs, O(4.8895<sup>N</sup>)&middot;tr(<i>N</i>) = O(146.69<sup>N</sup>) spanning trees, and O(5.4723<sup>N</sup>)&middot;tr(<i>N</i>) = O(164.17<sup>N</sup>) forests (that is, cycle-free graphs). We also obtain upper bounds for the number of crossing-free straight-edge graphs with at most <i>cN</i> edges and for the number of such graphs with at least <i>cN</i> edges. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/twotrees.pdf">Disjoint compatible geometric matchings</a>,</b> <ul type="circle"> <li><a href="http://www.eecs.tufts.edu/~mishaq01/">Mashhood Ishaque</a>, <a href="http://www.cs.tufts.edu/~dls/">Diane L. Souvaine</a>, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://socg2011.inria.fr/">27th Sympos. on Comput. Geom.</a> (Paris, 2011)</i>, ACM Press, pp. 125-134.</li> <li><a href="http://dx.doi.org/10.1007/s00454-012-9466-9">Discrete Comput. Geom.</a><b>49</b> (1) (2013), 89-131.</li> <li> <span onmouseover="disjointmatchings.style.display=''" onmouseout="disjointmatchings.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="disjointmatchings" style="display: none;"><font size="-1"> We prove that for every set of <i>n</i> pairwise disjoint line segments in the plane in general position, there is another set of <i>n</i> segments such that the <i>2n</i> segments form pairwise disjoint simple polygons in the plane. This settles in the affirmative the <i>Disjoint Compatible Matching Conjecture</i> by Aichholzer <i>et al.</i>. The key tool in our proof is a novel subdivision of the free space around <i>n</i> disjoint line segments into at most <i>n+1</i> convex cells such that the dual graph of the subdivision contains two edge-disjoint spanning trees.</font> </span> </li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1012.5664">Bounds on the maximum multiplicity of some common geometric graphs</a>,</b> <ul type="circle"> <li><a href="http://www.cs.uwm.edu/faculty/ad/">Adrian Dumitrescu</a>, <a href="http://wwwmath.uni-muenster.de/logik/Personen/Schulz/">Andr&eacute; Schulz</a>, <a href="http://www.cs.tau.ac.il/~sheffera/">Adam Sheffer</a>, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.stacs-conf.org/">28th Sympos. on Theoretical Aspects of Comp. Sci.</a> (Dortmund, 2011)</i>, vol. 5 of LIPICS, Schloss Dagstuhl, pp. 637-648.</li> <li><a href="http://epubs.siam.org/doi/abs/10.1137/110849407">SIAM Discrete Math.</a> <b>27</b> (2) (2013), 802 826.</li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/colorful-r8.pdf">The union of colorful simplices spanned by a colored point set</a>,</b> <ul type="circle"> <li><a href="http://wwwmath.uni-muenster.de/logik/Personen/Schulz/">Andr&eacute; Schulz</a> and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://theory.utdallas.edu/COCOA2010/">4th Conf. on Combin. Optimization and Appl.</a> (Kailua Kona, HI, 2010)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-17458-2_27">6508</a>, Springer, pp. 324-338.</li> <li><a href="http://dx.doi.org/10.1016/j.comgeo.2012.01.006">Comput. Geom. Theory Appl.</a> <b>46</b> (2013), 574-590.</li> <li> <span onmouseover="colorunion.style.display=''" onmouseout="colorunion.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="colorunion" style="display: none;"><font size="-1"> A simplex spanned by a colored point set in Euclidean <i>d</i>-space is <em>colorful</em> if all vertices have distinct colors. The union of all full-dimensional colorful simplices spanned by a colored point set is called the <em>colorful union</em>. We show that in every dimension <i>d</i>, the maximum combinatorial complexity of the colorful union of <i>n</i> colored points is between &Omega;(<i>n</i><sup>(<i>d</i>-1)<sup>2</sup></sup>) and O(<i>n</i><sup>(<i>d</i>-1)<sup>2</sup></sup> log <i>n</i>). For <i>d=2</i>, the upper bound is known to be O(<i>n</i>), and for <i>d=3</i> we present an upper bound of O(<i>n</i><sup>4</sup> &alpha;(<i>n</i>)), where &alpha;(.) is the extremely slowly growing inverse Ackermann function. We also prove several structural properties of the colorful union. In particular, we show that the boundary of the colorful union is covered by O(<i>n</i><sup>d-1</sup>) hyperplanes, and the colorful union is the union of <i>d+1</i> star-shaped polyhedra. These properties lead to efficient data structures for point inclusion queries in the colorful union. </font> </span> </li> </ul> </li> <br> <li><b><a href="AC20110815.pdf">Graphs that admit polyline drawings with few crossing angles</a>,</b> <ul type="circle"> <li><a href="http://sci.haifa.ac.il/~ackerman/">Eyal Ackerman</a>, <a href="http://dcg.epfl.ch/page-18454-en.html">Radoslav Fulek</a>, and Csaba D. T&oacute;th,</li> <li>preliminary version "On the size of graphs that admit polyline drawings with few bends and crossing angles" in <i>Proc. <a href="http://www.graphdrawing.org/gd2010/">18th Sympos. on Graph Drawing</a> (Konstanz, 2010)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-18469-7">6502</a>, Springer, 2011, pp. 1-12.</li> <li><a href="http://dx.doi.org/10.1137/100819564">SIAM J. Discrete Math.</a> <b>26</b> (1) (2012), 305-320.</li> <li> <span onmouseover="polylineangle.style.display=''" onmouseout="polylineangle.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="polylineangle" style="display: none;"><font size="-1"> We consider graphs that admit polyline drawings where all crossings occur at the same angle &alpha; &isin; (0, &pi;/2]. We prove that every graph on <i>n</i> vertices that admits such a polyline drawing with at most two bends per edge has <i>O(n)</i> edges. This result remains true when each crossing occurs at an angle from a small set of angles. We also provide several extensions that might be of independent interest. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://www.cs.umanitoba.ca/~cccg2010/electronicProceedings/paper22.pdf">Watchman tours for polygons with holes</a>,</b> <ul type="circle"> <li><a href="http://www.cs.uwm.edu/faculty/ad/">Adrian Dumitrescu</a> and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.cs.umanitoba.ca/~cccg2010/">22nd Canadian Conf. Comput. Geom.</a> (Winnipeg, MB, 2010)</i>, pp. 113-116.</li> <li><a href="http://dx.doi.org/10.1016/j.comgeo.2012.02.001">Comput. Geom. Theory Appl.</a> <b>45</b> (7) (2012), 326-333.</li> <li> <span onmouseover="watchman.style.display=''" onmouseout="watchman.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="watchman" style="display: none;"><font size="-1"> A watchman tour in a polygonal domain (for short, polygon) is a closed curve such that every point in the polygon is visible from at least one point of the tour. The problem of finding a shortest watchman tour is NP-hard for polygons with holes. We show that the length of a minimum watchman tour in a polygon <i>P</i> with <i>k</i> holes is O(per(<i>P</i>)+ <i>k</i><sup>1/2</sup> diam(<i>P</i>)), where per(<i>P</i>) and diam(<i>P</i>) denote the perimeter and the diameter of <i>P</i>, respectively. Apart from the multiplicative constant, this bound is tight in the worst case. A watchman tour of this length can be computed in O(<i>n</i> log <i>n</i>) time, where <i>n</i> is the total number of vertices. We generalize our results to watchman tours in polyhedra with holes in 3-space. Our upper bound, O(per(<i>P</i>)+ &radic;<span style="text-decoration:overline;"><i>k</i>&nbsp;diam(<i>P</i>)per(<i>P</i>)&nbsp;</span>+<i>k</i><sup>2/3</sup> diam(<i>P</i>)), is again tight in the worst case. </font> </span></li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/RAC_Drawings_2010-11-08.pdf">Graphs that admit right angle crossing drawings</a>,</b> <ul type="circle"> <li><a href="http://math.ucalgary.ca/profiles/karin-arikushi">Karin Arikushi, <a href="http://dcg.epfl.ch/page-18454-en.html">Radoslav Fulek</a>, <a href="http://www.renyi.hu/~keszegh/">Bal&aacute;zs Keszegh</a>, <a href="http://dcg.epfl.ch/page-18456.html">Filip Mori&#263</a>;, and Csaba D. T&oacute;th,</li> <li>preliminary results in <i>Abstracts of the <a href="http://www.cs.tufts.edu/research/geometry/FWCG09/">19th Fall Workshop on Comput. Geom.</a> (Medford, MA, 2009)</i>, pp. 41-42,<br> "Drawing graphs with 90&#176; crossings and at most 1 or 2 bends per edge."</li> <li>in <i>Proc. <a href="http://wg2010.thilikos.info/">36th Workshop on Graph Theoretic Concepts in Comp. Sci.</a> (Zar&oacute;s, 2010)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-16926-7">6410</a>, Springer, pp. 135-146.</li> <li><a href="http://dx.doi.org/10.1016/j.comgeo.2011.11.008">Comput. Geom. Theory Appl.</a> <b>45</b> (4) (2012), 169-177.</li> <li> <span onmouseover="orthogonalcrossing.style.display=''" onmouseout="orthogonalcrossing.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="orthogonalcrossing" style="display: none;"><font size="-1"> We consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with <i>n</i> vertices admits an RAC drawing with at most 1 bend or 2 bends per edge, then the number of edges is at most 6.5<i>n</i> and 74.2<i>n</i>, respectively. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/0909.4094">Long non-crossing configurations in the plane</a>,</b> <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://stacs.loria.fr/">27th Sympos. Theoretical Aspects of Comp. Sci.</a> (Nancy, 2010)</i>, <a href="http://www.dagstuhl.de/en/publications/lipics/">Leibniz International Proceedings in Informatics</a>, Schloss Dagstuhl, pp. 311-322.</li> <li><a href="http://dx.doi.org/10.1007/s00454-010-9277-9">Discrete Comput. Geom.</a> <b>44</b> (4) (2010), 727-752.</li> <li> <span onmouseover="noncross.style.display=''" onmouseout="noncross.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="noncross" style="display: none;"><font size="-1"> We revisit some maximization problems for geometric networks design under the non-crossing constraint, first studied by Alon, Rajagopalan and Suri in the early 1990s. Given a set of <i>n</i> points in the plane in general position (no three points collinear), compute a longest non-crossing configuration composed of straight line segments that is: (a) a matching; (b) a Hamiltonian path; (c) a spanning tree. Here we obtain some new results for (b) and (c), as well as for the Hamiltonian cycle problem. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/1002.0345">New bounds on the average distance from the Fermat-Weber center of a planar convex body</a>,</b> <ul type="circle"> <li><a href="http://www.cs.uwm.edu/faculty/ad/">Adrian Dumitrescu</a>, <a href="http://digital.cs.usu.edu/~mjiang/">Minghui Jiang</a>, and Csaba D. T&oacute;th,</li> <li>preliminary versions in <i>Abstracts of the <a href="http://www.cs.rpi.edu/fwcg2008/">18th Fall Workshop on Comput. Geom.</a> (Troy, NY, 2008)</i>, pp. 61-62.</li> <li>and in <i>Proc. <a href="http://theory.utdallas.edu/ISAAC2009/">20th Internat. Sympos. on Algorithms and Computation</a> (Honolulu, HI, 2009)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-10631-6_15">5878</a>, Springer, pp. 132-141.</li> <li><a href="http://dx.doi.org/10.1016/j.disopt.2011.02.004">Discrete Optimization</a> <b>8</b> (3) (2011), 417-427.</dd> </li> <li> <span onmouseover="webercenter.style.display=''" onmouseout="webercenter.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="webercenter" style="display: none;"><font size="-1"> The Fermat-Weber center of a planar body <i>Q</i> is a point in the plane from which the average distance to the points in <i>Q</i> is minimal. We show that for any convex body <i>Q</i> in the plane, the average distance from the Fermat-Weber center of <i>Q</i> to the points of <i>Q</i> is larger than &Delta;(<i>Q</i>)/6, where &Delta;(<i>Q</i>) is the diameter of <i>Q</i>. This proves a conjecture of Paz Carmi, Sariel Har-Peled and Matthew Katz. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://www.combinatorics.org/Volume_17/Abstracts/v17i1n35.html">A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets</a>,</b> <ul type="circle"> <li>Ond&#345;ej B&iacute;lka, Kevin Buchin, Radoslav Fulek, Masashi Kiyomi, Yoshio Okamoto, Shin-ichi Tanigawa, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.jaist.ac.jp/~uehara/JCCGG09/">7th Japan Conference on Computational Geometry and Graphs</a> (Kanazawa, 2009)</i>, JAIST.</li> <li><a href="http://www.combinatorics.org/">Electronic Journal of Combinatorics</a> <b>17</b> (1) (2010), article N35.</li> <li> <span onmouseover="minkowski.style.display=''" onmouseout="minkowski.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="minkowski" style="display: none;"><font size="-1"> For every <i>m</i> and <i>n</i>, there exist point sets <i>P</i> and <i>Q</i> in the plane with <i>|P| = m</i> and <i>|Q| = n</i> such that the Minkowski sum <i>P+Q</i> contains a convexly independent subset of size <i>&Omega;(m<sup>2/3</sup>n<sup>2/3</sup> + m + n)</i>. This bound is best possible by a recent result due to Eisenbrand, Pach, and Rothvo&szlig;.</font> </span> </li> </ul> </li> <br> <li><b><a href="3edgeconnect19.pdf">Augmenting the edge connectivity of planar straight line graphs to three</a>,</b> <ul type="circle"> <li>Marwan Al-Jubeh, Mashhood Ishaque, Krist&oacute;f R&eacute;dei, Diane L. Souvaine, Csaba D. T&oacute;th, and Pavel Valtr,</li> <li>preliminary results (with Pavel Valtr) in <i>Proc. <a href="http://metodosestadisticos.unizar.es/~egc09/english.htm">XIII Encuentros de Geometr&iacute;a Computacional</a> (Zaragoza, 2009)</i>.</li> <li>preliminary results (with Marwan Al-Jubeh, Mashhood Ishaque, Krist&oacute;f R&eacute;dei, Diane L. Souvaine) "<a href="http://dx.doi.org/10.1007/978-3-642-10631-6_91">Tri-edge-connectivity augmentation for planar straight line graphs</a>," in <i>Proc. <a href="http://theory.utdallas.edu/ISAAC2009/">20th Internat. Sympos. on Algorithms and Computation</a> (Honolulu, HI, 2009)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-10631-6_91">5878</a>, Springer, pp. 902-911.</li> <li><a href="http://dx.doi.org/10.1007/s00453-011-9551-0">Algorithmica</a> <b>61</b> (4) (2011), 971-999.</li> <li> <span onmouseover="augmentable.style.display=''" onmouseout="augmentable.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="augmentable" style="display: none;"><font size="-1"> We characterize the planar straight line graphs (PSLGs) that can be augmented to 3-connected and 3-edge-connected PSLGs, respectively. We show that if a PSLG with <i>n</i> vertices can be augmented to a 3-edge-connected PSLG, then at most <i>2n-2</i> new edges are always sufficient and sometimes necessary for the augmentation. If the input PSLG is, in addition, already 2-edge-connected, then <i>n-2</i> new edges are always sufficient and sometimes necessary for the augmentation to a 3-edge-connected PSLG. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1007/s10878-010-9310-1">Convex partitions with 2-edge connected dual graphs</a>,</b> <ul type="circle"> <li>Marwan Al-Jubeh, Michael Hoffmann, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. T&oacute;th,</li> <li>in <i>Abstracts of the <a href="http://www.cs.rpi.edu/fwcg2008/">18th Fall Workshop on Comput. Geom.</a> (Troy, NY, 2008)</i>, pp. 63-64.</li> <li>in <i>Proc. <a href="http://www.cse.buffalo.edu/cocoon2009/">15th Internat. Computing and Combin. Conf.</a> (Niagara Falls, NY, 2009)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-642-02882-3_20">5609</a>, Springer, pp. 192-204.</li> <li><a href="http://www.springer.com/mathematics/numbers/journal/10878">J. Combinatorial Optimization</a> <b>22</b> (3) (2010), 409-425.</li> <li> <span onmouseover="fwcg08.style.display=''" onmouseout="fwcg08.style.display='none'"> <font color="#660000">(abstract)</font> </span> (<a href="Partitioning.pdf">pdf</a>) <span id="fwcg08" style="display: none;"><font size="-1"> Every set of <i>k</i> disjoint convex polygonal obstacles with a total of <i>n</i> vertices in the plane, there is a partition of the free space into <i>n-k+1</i> convex cells whose dual graph is 2-edge connected. Every convex cell corresponds to a node in the dual graph, and every vertex of an obstacle corresponds to an edge between two incident convex cells. We also refute a recent conjecture of Aicholzer et al. and present 15 disjoint segments such that if a convex partition is constructed by successively extending the segments along straight lines, then its dual graph has a bridge. Questions about the dual graph of a convex partition are motivated by the still unresolved conjecture about compatible disjoint geometric matchings. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://doi.acm.org/10.1145/1542362.1542375">Binary plane partitions for disjoint line segments</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.madalgo.au.dk/socg2009/">25th Sympos. on Comput. Geom.</a> (Aarhus, 2009)</i>, ACM Press, pp. 71-79.</li> <li><a href="http://dx.doi.org/10.1007/s00454-011-9341-0">Discrete Comput. Geom.</a> <b>45</b> (4) (2011), 617-646.</li> <li> <span onmouseover="bspsegment.style.display=''" onmouseout="bspsegment.style.display='none'"> <font color="#660000">(abstract)</font> </span> (<a href="bsp16.pdf">pdf</a>) <span id="bspsegment" style="display: none;"><font size="-1"> A binary space partition (BSP) for a set of disjoint objects in Euclidean space is a recursive decomposition, where each step partitions the space (and some of the objects) along a hyperplane and recurses on the objects clipped in each of the two open halfspaces. The size of a BSP is defined as the number of resulting fragments of the input objects. It is shown that every set of <i>n</i> disjoint line segments in the plane admits a BSP of size O(<i>n</i> log <i>n</i>/log log <i>n</i>). This bound is best possible apart from the constant factor. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1137/100804310">Shooting permanent rays among disjoint polygons in the plane</a>,</b> <ul type="circle"> <li>Mashhood Ishaque, Bettina Speckmann, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.madalgo.au.dk/socg2009/">25th Sympos. on Comput. Geom.</a> (Aarhus, 2009)</i>, ACM Press, pp 51-60.</li> <li><a href="http://dx.doi.org/10.1137/100804310">SIAM J. Comput.</a> <b>41</b> (4) (2012), 1005-1027.</li> <li> <span onmouseover="rayinsert.style.display=''" onmouseout="rayinsert.style.display='none'"> <font color="#660000">(abstract)</font> </span> (<a href="rayinsert.pdf">pdf</a>) <span id="rayinsert" style="display: none;"><font size="-1"> We present a data structure for ray shooting and insertion in the free space among disjoint polygonal obstacles in the plane with a total of n vertices. The portion of each query ray between the starting point and the first obstacle hit is inserted permanently as a new obstacle. Our data structure uses O(<i>n</i> log <i>n</i>) space and preprocessing time, and it supports m successive ray shooting and insertion queries in O(<i>n</i> log<sup>2</sup> <i>n</i> + <i>m</i> log <i>m</i>) total time. In contrast, if the query rays are not inserted as new obstacles, then m successive independent queries take O(<i>m</i>&radic;<i>n</i>) time with currently known near-linear space data structures. Our data structure supports a near linear time computation of the convex partition of the free space around disjoint obstacles. If we are given disjoint polygons in the plane with a total of n vertices, a permutation of the reflex vertices, and a half-line at each reflex vertex that partitions the reflex angle into two convex angles, then the convex partitioning algorithm draws a ray emanating from each reflex vertex in the prescribed order in the given direction until it hits another obstacle, a previous ray, or infinity. The best previous implementation of the convex partition algorithm with a semi-dynamic ray shooting data structure in O(<i>n<sup>1+&epsilon;</sup></i>) space requires O(n<sup>3/2-&epsilon;/2</sup>) time for any &epsilon; > 0. Our data structure improves the runtime of the convex partition algorithm to O(<i>n</i> log<sup>2</sup> <i>n</i>). </font> </span> </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1016/j.comgeo.2008.11.002">Guarding curvilinear art galleries with vertex or point guards</a>,</b> <ul type="circle"> <li>Menelaos I. Karavelas, Csaba D. T&oacute;th, and Elias P. Tsigaridas,</li> <li><a href="http://dx.doi.org/10.1016/j.comgeo.2008.11.002">Comput. Geom. Theory Appl.</a> <b>42</b> (6-7) (2009), 522-535.</li> <li> <span onmouseover="curvilinear.style.display=''" onmouseout="curvilinear.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="curvilinear" style="display: none;"><font size="-1"> It is shown that for monitoring a piecewise convex polygon with <i>n &ge; 2</i> vertices, <i>floor(2n/3)</i> vertex guards are always sufficient and sometimes necessary. For the number of point guards that can be stationed at any point in the polygon, our upper bound <i>floor(2n/3)</i> carries over and we prove a lower bound of <i>ceiling(n/2)</i>. For monitoring a piecewise concave polygon with <i>n &ge; 3</i> vertices, <i>2n-4</i> point guards are always sufficient and sometimes necessary, whereas there are piecewise concave polygons where some points in the interior are hidden from all vertices, hence they cannot be monitored by vertex guards. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://arxiv.org/PS_cache/arxiv/pdf/0806/0806.4858v1.pdf">On stars and Steiner stars II</a>,</b> <ul type="circle"> <li>Adrian Dumitrescu, Csaba D. T&oacute;th, and Guangwu Xu,</li> <li>in <i>Proc. <a href="http://www.siam.org/meetings/da09/"> 20th ACM-SIAM Sympos. on Discrete Algorithms</a> (New York, NY, 2009)</i>, ACM Press, pp. 311-317.<br></li> <li><a href="http://dx.doi.org/10.1016/j.disopt.2009.04.003">Discrete Optimization</a> <b>6</b> (3) (2009), 324-332.</li> <li> <span onmouseover="steinerstar2.style.display=''" onmouseout="steinerstar2.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="steinerstar2" style="display: none;"><font size="-1"> A <i>Steiner star</i> for a set <i>P</i> of <i>n</i> points in <i>d</i>-space connects an arbitrary center point to all points of <i>P</i>, while a <i>star</i> connects a point <i>p&isin; P</i> to the remaining <i>n-1</i> points of <i>P</i>. All connections are realized by straight line segments. Fekete and Meijer showed that the minimum star is at most &radic;2 times longer than the minimum Steiner star for any finite point configuration in <i>d</i>-space. The maximum ratio between them, over all finite point configurations in <i>d</i>-space, is called the <i>star Steiner ratio</i> in <i>d</i>-space. It is conjectured that this ratio is 4/&pi; = 1.2732... in the plane and 4/3=1.3333... in three dimensions. Here we give upper bounds of 1.3631 in the plane, and 1.3833 in 3-space, thereby substantially improving recent upper bounds of 1.3999, and &radic;2 -10<sup>-4</sup>, respectively. </font> </span> (<a href="http://arxiv.org/abs/0806.4858">arxiv</a>)</li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/cx-stabbing-rev.pdf">Stabbing numbers of convex subdivisions</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th,</li> <li><a href="http://dx.doi.org/10.1007/s10998-008-8217-7">Periodica Mathematica Hungarica</a> <b>57</b> (2) (2008), 217-225.</li> <li> <span onmouseover="cxstab.style.display=''" onmouseout="cxstab.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="cxstab" style="display: none;"><font size="-1"> It is shown that for every subdivision of the <i>d</i>-dimensional Euclidean space, <i>d&ge; 2</i>, into <i>n</i> convex cells, there is a straight line that stabs at least &Omega;((log <i>n,</i>/loglog <i>n</i>)<sup>1/<i>(d-1)</i></sup>) cells. This bound is best possible apart from a constant factor. In other words, if a convex subdivision of <i>d</i>-space has the property that any line stabs at most <i>k</i> convex cells, then the subdivision has at most exp(O(<i>k</i><sup>{d-1}</sup>log <i>k</i>)) cells. Previously, this was only known in the case <i>d=2</i>. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1112/jlms/jdq087">Intersection patterns of curves</a>,</b> <ul type="circle"> <li>Jacob Fox, J&aacute;nos Pach, and Csaba D. T&oacute;th,</li> <li><a href="http://www.lms.ac.uk/publications/journal/">J. London Math. Soc.</a> <b>83</b> (2) (2011), 389-406.<br> </li> <li> <span onmouseover="justcurves.style.display=''" onmouseout="justcurves.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="justcurves" style="display: none;"><font size="-1">We prove that there are constants <i>c &gt;0</i> and <i>c<sub>k</sub> &gt;0</i> for every <i>k</i> such that if a set <i>C</i> of <i>n &gt;1</i> curves in the plane, any two of which intersects in at most <i>k</i> points, contains at most <i>&epsilon; n<sup>2</sup></i> intersecting pairs of curves, then there are two disjoint subsets <i>A,B&sub; C</i>, each of size at least <i>c<sub>k</sub>&epsilon;<sup>c</sup> n</i>, with the property that every curve in <i>A</i> intersects every curve in <i>B</i>. It follows that for every <i>k</i>, there is a constant <i>c'<sub>k</sub> &gt;0</i> such that for every collection <i>C</i> of <i>n > 1</i> curves in the plane with no pair intersecting in more than <i>k</i> points, the intersection graph <i>G</i> of <i>C</i> or its complement <i><span style="text-decoration: overline;">G</span></i> contains a balanced complete bipartite graph <i>K<sub>t,t</sub></i> with <i>t&ge; c'<sub>k</sub> n</i>; in other words, the family of intersection graphs of <i>k</i>-intersecting curves in the plane satisfies the strong Erd&#337;s-Hajnal property. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1007/s00453-012-9679-6">Relative convex hulls in semi-dynamic arrangements</a>,</b> <ul type="circle"> <li>Mashhood Ishaque and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://algo2008.org/doku.php/esa">16th European Symposium on Algorithms</a> (Karlsruhe, 2008)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-540-87744-8_65">5193</a>, Springer, pp. 780-792.</li> <li>Algorithmica <b>68</b> (2) (2014), 448-482.</li> <li> <span onmouseover="relativecx.style.display=''" onmouseout="relativecx.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="relativecx" style="display: none;"><font size="-1"> We present a data structure for maintaining the relative convex hull of a set of point sites in the presence of pairwise non-crossing line segment barriers that subdivide a bounding box into simply connected faces. For <i>n</i> sites and <i>m</i> barriers, our data structures have <i>O((n+m)</i> log <i>n)</i> size. They support <i>m</i> barrier insertions and O(<i>n</i>) site deletions in O((<i>n+m</i>)polylog (<i>mn</i>)) total time, and can answer analogues of standard convex hull queries in O(polylog(<i>mn</i>)) time. <br> The semi-dynamic maintenance of the relative convex hull (with barrier insertions and site deletions) is motivated by a generalization of the sweep line technique, one of the most powerful methods in computational geometry. A sweep <i>line</i> scans a set of sites in a left-to-right order, which can be computed by sorting the sites by <i>x</i>-coordinate. Our data structures allow the sweep wavefront to have arbitrary polygonal shape, which is used in applications where the sweep wavefront has to bend around obstacles or stay in a configuration space. With previously known techniques, the <i>m</i> updates of a polygonal sweep wavefront required <i>m</i> simplex range reporting queries, hence O(<i>m n<sup>1/2</sup></i> polylog <i>n</i>) total time. Our data structure reduces the runtime to O((<i>m+n</i>)polylog(<i>mn</i>)). </font> </span> </li> </ul> </li> <br> <li><b><a href="http://arxiv.org/math.CO/0701392">On a question of Bourgain about geometric incidences</a>,</b> <ul type="circle"> <li>J&oacute;zsef Solymosi and Csaba D. T&oacute;th,</li> <li><a href="http://journals.cambridge.org/repo_A19CBIXw">Combinatorics Probability and Computing</a> <b>17</b> (4) (2008), 617-625.</li> <li> <span onmouseover="bourgain.style.display=''" onmouseout="bourgain.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="bourgain" style="display: none;"><font size="-1"> Given a set of <i>s</i> points and a set of <i>n<sup>2</sup></i> lines in three-dimensional Euclidean space such that each line is incident to <i>n</i> points but no <i>n</i> lines are coplanar, then we have <i>s=&Omega;(n<sup>11/4</sup>)</i>. This is the first nontrivial answer to a question recently posed by Jean Bourgain. </font> </span> </li> </ul> </li> <br> <li><b><a href="2edgecon20.pdf">Connectivity augmentation in planar straight line graphs</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://tggt.cams.ehess.fr/">Conf. on Topological & Geometric Graph Theory</a> (Paris, 2008)</i>, pp. 51-54.</li> <li><a href="http://dx.doi.org/10.1016/j.ejc.2011.09.002">European J. Combinatorics</a> <b>33</b> (3) (2012), 408-425.</li> <li> <span onmouseover="connaug.style.display=''" onmouseout="connaug.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="connaug" style="display: none;"><font size="-1"> It is shown that every connected plane straight line graph with <i>n</i>&ge; 3 vertices can be augmented to a 2-edge connected plane straight line graph by adding at most &lfloor;(2<i>n</i>-2)/3&rfloor; edges. It is also shown that every connected plane straight line tree with <i>n</i>&ge; 3 vertices can be augmented to a 2-edge connected plane topological graph by adding at most &lfloor;<i>n</i>/2&rfloor; edges. Both bounds are best possible. However, for every <i>n</i>&ge; 3, there are plane straight line trees with <i>n</i> vertices that cannot be augmented to a 2-edge-connected plane straight line graph by adding fewer than (6/11)<i>n</i>-O(1) edges, improving the previously known best lower bound of &lfloor;<i>n</i>/2&rfloor;. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://arxiv.org/abs/0710.4109">Extremal problems on triangle areas in the plane and three-space</a>,</b> <ul type="circle"> <li>Adrian Dumitrescu, Micha Sharir, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.umiacs.umd.edu/conferences/socg2008/">24th Sympos. Comput. Geom.</a> (College Park, MD, 2008)</i>, ACM Press, pp. 208-217.</li> <li><a href="http://dx.doi.org/10.1016/j.jcta.2009.03.008">J. Combin. Theory Ser. A</a> <b>116</b> (2009), 1177-1198.</li> <li> <span onmouseover="extriangle.style.display=''" onmouseout="extriangle.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="extriangle" style="display: none;"><font size="-1"> In the plane we prove: (i) The number of unit area triangles in the plane is <i>O(n<sup>44/19</sup>) =O(n<sup>2.3158</sup>)</i>. The best previous bound, <i>O(n<sup>7/3</sup>)</i>, is due to Pach and Sharir from 1992. (ii) For points in convex position, there exist <i>n</i>-element point sets that span &Omega;<i>(n</i> log <i>n)</i> triangles of unit area. (iii) The number of triangles of minimum (nonzero) area determined by <i>n</i> points is at most <i>(2/3)(n<sup>2</sup>-n)</i>; there exist <i>n</i>-element point sets that span <i>(6/&pi;<sup>2</sup>-o(1))n<sup>2</sup></i> minimum area triangles. (iv) The number of acute triangles of minimum area determined by <i>n</i> points is <i>O(n)</i>; this is asymptotically tight. (v) For <i>n</i> points in convex position, the number of triangles of minimum area is <i>O(n)</i>; this is asymptotically tight. (vi) If no three points are allowed to be collinear, there exist <i>n</i>-element point sets that span &Omega;<i>(n</i> log <i>n)</i> minimum area triangles. In three-space we prove: (i) The number of unit area triangles spanned by <i>n</i> points is at most <i>O(n<sup>17/7</sup>&beta;(n))</i>, where <i>&beta;(n)</i> is an extremely slowly growing function. (ii) A set of <i>n</i> points, not all on a line, determines at least &Omega;<i>(n<sup>2/3</sup>/&beta;(n))</i> triangles of distinct areas that share a common side. (iii) The number of minimum area triangles is <i>O(n<sup>2</sup>)</i>; this is asymptotically tight. (iv) There exist <i>n</i>-element point sets that span &Omega;<i>(n<sup>4/3</sup>)</i> triangles of maximum area. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1007/s00453-009-9329-9">Minimum weight convex Steiner partitions</a>, </b> <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.siam.org/meetings/da08/"> 19th ACM-SIAM Sympos. on Discrete Algorithms</a> (San Francisco, CA, 2008)</i>, ACM Press, pp. 581-590.<br></li> <li>Algorithmica <b>60</b> (3) (2011), 627-652.</li> </ul> </li> <br> <li><b><a href="http://dl.acm.org/citation.cfm?id=1347082.1347216">On stars and Steiner stars</a>, </b> <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.siam.org/meetings/da08/"> 19th ACM-SIAM Sympos. on Discrete Algorithms</a> (San Francisco, CA, 2008)</i>, ACM Press, pp. 1233-1240.<br></li> </ul> </li> <br> <li><b><a href="http://www-math.mit.edu/%7Etoth/TuranAndErdosHajnal041107.pdf">Tur&aacute;n-type results for partial orders and intersection graphs of convex sets</a>,</b> <ul type="circle"> <li>Jacob Fox, J&aacute;nos Pach, and Csaba D. T&oacute;th,</li> <li><a href="http://www.ma.huji.ac.il/~ijmath/">Israel J. of Math.</a> <b>178</b> (2010), 29-50.</li> <li> <span onmouseover="erdoshajnal.style.display=''" onmouseout="erdoshajnal.style.display='none'"> <font color="#660000">(abstract)</font> </span> <span id="erdoshajnal" style="display: none;"><font size="-1"> We prove several Ramsey-type results for intersection graphs of arrangements geometric shapes in the plane. In particular, we prove the following bounds, all of which are tight apart from the constant <i>c</i>. There is a constant <i>c&gt;0</i> such that if <i>n&isin;<b>N</b></i>, <i>n&gt;2</i>, and <i>S</i> is a family of convex bodies in the plane, then the intersection graph of <i>S</i> or its complement contains a complete bipartite graph with <i>cn</i> vertices in either of its vertex classes. There is a constant <i>c&gt;0</i> such that if <i>n&isin;<b>N</b></i>, <i>n&gt;2</i>, and <i>S</i> is a family of <i>x</i>-monotone curves in the plane, then the intersection graph <i>G</i> of <i>S</i> contains a complete bipartite graph with <i>cn/</i>log<i>n</i> vertices in each of its vertex classes or the complement of <i>G</i> contains a complete bipartite graph with <i>cn</i> vertices in each of its vertex classes. Similar results were previously known for semialgebraic sets only, we show that algebraic properties are not necessary. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://www.jucs.org/jucs_13_11/analysis_of_two_sweep/jucs_13_11_1615_1627_dumitrescu.pdf">Analysis of two sweep-line algorithms for constructing spanning trees and Steiner trees</a>, </b> <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. Tth,</li> <li>in Abstracts of <i><a href="http://http://www.research.ibm.com/people/l/lenchner/fwcg2007/">17th Fall Workshop on Computational and Combinatorial Geometry</a> (Hawthorne, NY, 2007)</i>.<br></li> <li><a href="http://www.jucs.org/;internal&action=noaction&Parameter=1189625349589">J. Universal Comp. Sci.</a> <b>13</b> (11) (2007), 1615-1627.<br></li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/2-edge.pdf">Disjoint segments have a convex partition with a 2-edge connected dual graph</a>, </b> (<a href="erratum.pdf">Erratum</a>) <ul type="circle"> <li>Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tth,</li> <li>in <i>Proc. <a href="http://2007.cccg.ca">19th Canadian Conf. Comp. Geom.</a> (Ottawa, ON, 2007)</i>, pp. 13-16.<br></li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1016/j.jctb.2009.03.005">A bipartite strengthening of the Crossing Lemma</a>,</b> <ul type="circle"> <li>Jacob Fox, J&aacute;nos Pach, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="httP://www.cs.usyd.edu.au/~visual/gd2007/">15th Sympos. on Graph Drawing</a> (Sydney, 2007)</i>, LNCS 4875, Springer, 2008, pp. 13-24.<br></li> <li>J. Combin. Theory, Ser. B <b>100</b> (1) (2010), 23-35.</li> <li> <span onmouseover="strengthening.style.display=''" onmouseout="strengthening.style.display='none'"> <font color="#660000">(abstract)</font> </span> (<a href="http://www.princeton.edu/~jacobfox/papers/crossinglemma111608.pdf">pdf</a>) <span id="strengthening" style="display: none;"><font size="-1"> The celebrated Crossing Lemma states that, in every drawing of a graph with <i>n</i> vertices and <i>m &ge; 4n</i> edges there are at least &Omega;<i>(m<sup>3</sup>/n<sup>2</sup>)</i> crossing edges; or equivalently, there is an edge that crosses &Omega;<i>(m<sup>2</sup>/n<sup>2</sup>)</i> other edges. We strengthen the Crossing Lemma for drawings in which no two edges intersect in more than a constant number of points. We prove for every integer <i>k</i> that every graph <i>G=(V,E)</i> with <i>n</i> vertices and <i>m &ge; 3n</i> edges drawn in the plane such that any two edges intersect in at most <i>k</i> points has two disjoint subsets <i>E<sub>1</sub> , E<sub>2</sub> &sub; E</i>, each of size &Omega;<i>(m<sup>2</sup>/n<sup>2</sup>)</i>, such that every edge in <i>E<sub>1</sub></i> crosses every edge in <i>E<sub>2</sub></i>. We also show that this result does not remain true if we drop the assumption that no pair of edges intersect in more than a constant number of points.</font> </span> </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1007/s00454-009-9158-2">Cuttings for disks and axis-aligned rectangles in three-space</a>,</b> <ul type="circle"> <li>Eynat Rafalin, Diane L. Souvaine, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://projects.cs.dal.ca/wads07/">10th Workshop on Algorithms and Data Structures</a> (Halifax, NS, 2007)</i>, LNCS 4619, Springer, pp. 470-482.</li> <li>Discrete Comput. Geom. <b>43</b> (2) (2010), pp. 221-241.</li> <li> <SPAN onMouseOver="disks.style.display=''" onMouseOut="disks.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> (<a href="13disks.pdf">pdf</a>) <span ID="disks" STYLE="display:none"><font size="-1"> For <i>n</i> objects in Euclidean space and an integer <i>1&le;r&le;n</i> an (1/r)<i>-cutting</i> is a partition of the space into simplices such that the interior each simplex intersects at most <i>n/r</i> objects. Cuttings play a central role in proofs based on a divide-and-conquer strategy (for example, incidence bounds and range counting). Tight bounds are known for the cuttings of hyperplanes in <i>d</i>space, for any <i>d&ge;2</i> (Chazelle and Friedman, 1990). However, little seems to be known about cuttings for disjoint objects. We show that there is an (1/r)-cutting of size <i>O(r<sup>2</sup>)</i> for every finite set of disjoint disks in 3-space; and there is an (1/r)-cutting of size <i>O(r<sup>3/2</sup>)</i> for every finite set of disjoint axis-aligned rectangles in 3-space. Both bounds are best possible. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1007/978-3-540-73545-8">Improved throughput bounds for interference-aware wireless networks</a>,</b> <ul type="circle"> <li>Chiranjeeb Buragohain, Subhash Suri, Csaba D. T&oacute;th, and Yunhong Zhou,</li> <li>in <i>Proc. <a href="http://www.cs.ualberta.ca/~cocoon07/">13th Computing and Combinatorics Conference</a> (Banff, AB, 2007)</i>, LNCS 4598, Springer, pp. 210-221.</li> <li> <SPAN onMouseOver="cocoon07.style.display=''" onMouseOut="cocoon07.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="cocoon07" STYLE="display:none"><font size="-1"> (1) Suppose we have <i>n</i> arbitrarily paired <i>s-t</i> pairs in an <i>&Theta;(&#8730; n) &times &Theta;(&#8730; n)</i> size grid network. We show that if the average (hop) distance among the <i>s-t</i> pairs is <i>d</i>, then it is always possible to achieve a total throughput of &Omega;<i>(n/d)</i>. There are instances where this bound is tight. The upper bound on the throughput follows easily from a packing argument; our contribution is to show that &Omega;<i>(n/d)</i> throughput is <i>always</i> achievable. <br> (2) The &Omega;<i>(n/d)</i> throughput in a grid network can be achieved by a simple routing scheme that routes each flow along a single path. Both the routing and the scheduling algorithms are simple, deterministic, and distributed. Thus, for the grid topology networks, one can achieve (asymptotic) worst-case optimal throughput without resorting to computationally expensive LP type methods. <br> (3) Our third result concerns an approximation bound for the throughput in a general network: arbitrary network topology and arbitrary <i>s-t</i> pairs. We capture the interference constraints at the node level, and impose an ordering on the nodes. As a result of these two ideas, we achieve an approximation ratio of 3 for the optimal throughput, improving all previous bounds. <br> (4) We show that three straightforward routing schemes can have arbitrarily small throughput. On the other hand, in the special case of grid networks, we show that one can efficiently compute a single path route whose end to end throughput is within a constant factor of the optimal single path throughput. </font> </span> <SPAN onMouseOver="cocoonerr.style.display=''" onMouseOut="cocoonerr.style.display='none'"> <font color="#6600000">(erratum)</font> </SPAN> <span ID="cocoonerr" STYLE="display:none"><font size="-1"> There is a fatal error in our 3rd result. The solution of our <i>LP-node</i> linear program is not always schedulabable, as pointed out by Himanshu Gupta from SUNY Stone Brook. While <i>LP-edge</i> is still correct, it only gives a factor-5 approximation, instead of factor-3 claimed in the paper using <i>LP-node</i>. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1007/978-3-540-72792-7_10">Distinct triangle areas in a planar point set</a>,</b> <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://ipco2007.orie.cornell.edu/"> 12th Conf. on Integer Programming and Optimization</a> (Ithaca, NY, 2007)</i>, LNCS 4513, Springer, pp. 119-129.</li> <li> <SPAN onMouseOver="distincttri.style.display=''" onMouseOut="distincttri.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="distincttri" STYLE="display:none"><font size="-1"> Erd&#337;s, Purdy, and Straus (1977) conjectured that <i>n</i> noncollinear points in the plane determine at least &lfloor;(<i>n</i>-1)/2&rfloor; triangles of distinct areas. This bound is attained for equally spaced points distributed two parallel lines. We show that this number is at least 17<i>n</i>/38-<i>O(1)</i>&asymp; 0.4473<i>n</i>. The best previous bound, (&radic;2 -1)n-<i>O(1)</i>&asymp;0.4142<i>n</i>, follows from the combination of a results of Burton and Purdy (1979) and Ungar (1982). The new bound relies on considering consecutive elements in allowable sequences. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1016/j.jda.2008.07.007">Light orthogonal networks with constant geometric dilation</a>,</b> <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www-i7.informatik.rwth-aachen.de/stacs07">24th Sympos. Theoretical Aspects of Comp. Sci.</a> (Aachen, 2007)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-540-70918-3_16">4393</a>, Springer, pp. 175-187.</li> <li><a href="http://dx.doi.org/10.1016/j.jda.2008.07.007">J. Discrete Algorithms</a> <b>7</b> (1) (2009), 112-129. <li> <SPAN onMouseOver="dila.style.display=''" onMouseOut="dila.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="dila" STYLE="display:none"><font size="-1"> An orthogonal network for a given set of <i>n</i> points in the plane is an axis-aligned planar straight line graph that connects all input points. We show that for any set of <i>n</i> points in the plane, there is an orthogonal network that (i) is <i>short</i> having a total edge length of <i>O(|T|)</i>, where <i>|T|</i> denotes the length of a minimum Euclidean spanning tree for the point set; (ii) is <i>small</i> having <i>O(n)</i> vertices and edges; and (iii) has <i>bounded geometric dilation</i>, which means that for any two points <i>u</i> and <i>v</i> at vertices or in edges of the network, the shortest path between <i>u</i> and <i>v</i> is at most constant times longer than the (Euclidean) distance between <i>u</i> and <i>v</i>. </font> </span> (<a href="dilation-final.pdf">pdf</a>) </li> </ul> </li> <br> <li><b><a href="http://www-math.mit.edu/%7Etoth/tetra.ps.gz">On the number of tetrahedra with minimal, unit, and distinct volumes in three-space</a>,</b> <ul type="circle"> <li>Adrian Dumitrescu and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.siam.org/meetings/da07/">18th ACM-SIAM Sympos. on Discrete Algorithms</a> (New Orleans, LA, 2007)</i>, ACM Press, pp. 1114-1123.</li> <li><a href="http://dx.doi.org/10.1017/S096354830700884X">Combinatorics Probability and Computing</a> <b>17</b> (2008), 203-224.</li> <li> <SPAN onMouseOver="tetra.style.display=''" onMouseOut="tetra.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="tetra" STYLE="display:none"><font size="-1"> We formulate and give partial answers to several combinatorial problems on four-tuples of <i>n</i> points in three-space. (i) The number of minimum (nonzero) volume tetrahedra spanned by <i>n</i> points in <b>R</b><sup>3</sup> is &Theta;<i>(n<sup>3</sup>)</i>. (ii) The number of unit-volume tetrahedra determined by <i>n</i> points in <b>R</b><sup>3</sup> is <i>O(n<sup>7/2</sup>)</i>, and there are point sets for which this number is &Omega;<i>(n<sup>3</sup></i>log log <i>n)</i>. (iii) The tetrahedra determined by <i>n</i> points in <b>R</b><sup>3</sup>, not all on a plane, have at least &Omega;<i>(n)</i> distinct volumes, and there are point sets for which this number is <i>O(n)</i>; this gives a first partial answer for the three-dimensional case to an old question of Erd&#337;s, Purdy, and Straus. We also give an <i>O(n<sup>3</sup>)</i> time algorithm for reporting all tetrahedra of minimum nonzero volume, and thereby extend an early algorithm of Edelsbrunner, O'Rourke, and Seidel. </font> </span> </li> </ul> </li> <br> <li><b><a href="crossdecay.pdf">On the decay of crossing numbers</a>,</b> <ul type="circle"> <li>Jacob Fox and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.gd2006.org/">14th Sympos. on Graph Drawing</a> (Karlsruhe, 2006)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-540-70904-6_18">4372</a>, Springer, pp. 174-183.</li> <li><a href="http://dx.doi.org/10.1016/j.jctb.2007.03.005">J. Combin. Theory Ser. B</a> <b>98</b> (1) (2008), 33-42.</li> <li> <SPAN onMouseOver="crossdecay.style.display=''" onMouseOut="crossdecay.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="crossdecay" STYLE="display:none"><font size="-1"> Our research is motivated by an old conjecture of Richter and Thomassen (1993) that says that every graph has an edge such that the removal of this edge decreases the crossing number by an amount proportional to the square root of the crossing number. We show here that one can remove a constant fraction of the edges so that the crossing number also decreases by at most a constant factor. Along the way, we also prove a new lower bound on the crossing number in terms of the sum of degree squares. </font> </span> </li> </ul> </li> <br> <li><b> <a href="http://dx.doi.org/10.1007/s00373-007-0752-x">Decompositions, partitions, and coverings with convex polygons and pseudo-triangles</a>,</b><br> <ul type="circle"> <li>Oswin Aichholzer, Clemens Huemer, Sarah Kappes, Bettina Speckmann, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.mfcs.sk/mfcs2006/">31st Sympos. Math. Foundations Comp. Sci.</a> (Star&aacute; Lesn&aacute;, 2006)</i>, LNCS 4162, Springer, pp. 86-97.</li> <li><a href="http://dx.doi.org/10.1007/s00373-007-0752-x">Graphs and Combinatorics</a> <b>23</b> (5) (2007), 481-507.</li> <li> <SPAN onMouseOver="pseudoconvex.style.display=''" onMouseOut="pseudoconvex.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="pseudoconvex" STYLE="display:none"><font size="-1"> We propose a novel subdivision of the plane that consists of both convex polygons and pseudo- triangles. This pseudo-convex decomposition is significantly sparser than either convex decompositions or pseudo-triangulations for planar point sets and simple polygons. We also introduce pseudo-convex partitions and coverings. We establish some basic properties and give combinatorial bounds on their complexity. Our upper bounds depend on new Ramsey-type results concerning disjoint empty convex <i>k</i>-gons in point sets. </font> </span> (<a href="pseudoconvex.pdf">pdf</a>) </li> </ul> </li> <br> <li><b><a href="http://www.cs.queensu.ca/cccg/papers/cccg26.pdf">Spanning trees across axis-parallel segments</a>,</b> <ul type="circle"> <li>Michael Hoffmann and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.cs.queensu.ca/cccg/">18th Canadian Conf. Comput. Geom.</a> (Kingston, ON, 2006)</i>, pp. 101-104.</li> <li> <SPAN onMouseOver="kingston.style.display=''" onMouseOut="kingston.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="kingston" STYLE="display:none"><font size="-1"> Given <i>n</i> disjoint axis-parallel line segments in the plane and a set of points (also disjoint from the segments), the points can be connected by a straight line spanning tree such that every line segment crosses at most three edges of the tree. The bound three cannot be improved. If we drop the condition on the direction of the segments, then no tight bound is known. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1007/s00454-007-9025-y">Tight bounds for connecting sites across barriers</a>,</b> <ul type="circle"> <li>David Krumme, Eynat Rafalin, Diane L. Souvaine, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.cs.arizona.edu/~socg06/">22nd Sympos. Comput. Geom.</a> (Sedona, AZ, 2006)</i>, ACM Press, pp. 439-448.</li> <li><a href="http://www.springerlink.com/content/100356/">Discrete Comput. Geom.</a> <b>40</b> (3) (2008), 377-394.</li> <li> <SPAN onMouseOver="barriers.style.display=''" onMouseOut="barriers.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="barriers" STYLE="display:none"><font size="-1"> This result was motivated by a multi-point location problem, a central question in computational geometry. Assume that we are given <i>n</i> pairwise non-crossing line segments in the plane that subdivides the plane into <i>n+1</i> convex cells, and we are also a point in the interior of each cell. Then these <i>n+1</i> points can be connected by a straight line spanning tree such that every line segment crosses at most two edges of the tree. There is also a spanning tree such that the total number of segment-edge crossings is at most <i>5n/3+O(&radic;n)</i>. Both bounds are best possible. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1007/s00454-006-1232-4">Distinct distances in homogeneous sets in Euclidean space</a>,</b> <ul type="circle"> <li>J&oacute;zsef Solymosi and Csaba D. T&oacute;th,</li> <li><a href="http://link.springer-ny.com/link/service/journals/00454/tocs.html">Discrete Comput. Geom.</a> <b>35</b> (4) (2006), 537-549.</li> <li> <SPAN onMouseOver="homodist.style.display=''" onMouseOut="homodist.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="homodist" STYLE="display:none"><font size="-1"> The minimum number of distinct distances determined by <i>n</i> points in d-space is between the upper bound <i>O(n<sup>2/d</sup>)</i> (in the integer lattice section); and the lower bounds <i>&Omega;(n<sup>2/d-2/d(d+2)</sup>)</i> for <i>d&ge;4</i> (Solymosi and Vu, 2005) and <i>&Omega;(n<sup>.5460</sup>)</i> in 3-space (Aronov, Pach, Sharir, and Tardos, 2004). In this paper, we improve all the above lower bounds for homogeneous point set, that is, when <i>n</i> points lie in cube of volume <i>n</i> and every unit cube contains <i>O(1)</i> points. Such a set of <i>n</i> points determines at least <i>&Omega;(n<sup>2d/(d<sup>2</sup>+1)</sup>)</i> distinct distances in d-space and <i>&Omega;(n<sup>.6091</sup>)</i> distinct distances in 3-space. </font> </span> </li> </ul> </li> <br> <li><b><a href="assign.ps.gz">A vertex-face assignment for plane graphs</a>,</b> <ul type="circle"> <li>Diane L. Souvaine and Csaba D. T&oacute;th, </li> <li>in <i>Proc. <a href="http://cccg.cs.uwindsor.ca/">17th Canadian Conf. on Comput. Geom.</a> (Windsor, ON, 2005)</i>, pp. 131-134.</li> <li><a href="http://dx.doi.org/10.1016/j.comgeo.2008.06.005">Comput. Geom. Theory Appl.</a> <b>42</b> (5) (2009), 388-394.</li> <li> <SPAN onMouseOver="assign.style.display=''" onMouseOut="assign.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="assign" STYLE="display:none"><font size="-1"> We show an interesting relation between the faces and vertices of a planar straight line graph. Every face can be assigned to an incident vertex such that every vertex is assigned to at most two faces, and every reflex vertex is assigned to at most one face. (A vertex is <i>reflex</i> if it is the apex of a reflex angle in an incident face.) It was used to prove the above result on vertex-colored encompassing graphs for arbitrary planar straight line graphs (without this result, it would hold only for plane <i>forests</i>, graphs with a single face). The proof relies on a new construction of <i>combinatorial pseudo-triangulations</i> by (Haas et al., 2005), extending Henneberg operations. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://scitation.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&id=SJDMEC000022000003001187000001">Axis-aligned subdivisions with low stabbing numbers</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.wads.org">9th Workshop on Algorithms and Data Structures</a> (Waterloo, ON, 2005)</i>, LNCS <a href="http://www.springerlink.com/openurl.asp?genre=article&amp;id=doi:10.1007/11534273_23">3608</a>, Springer, pp. 256-268.</li> <li><a href="http://link.aip.org/link/?SJD/22/1187">SIAM J. Discrete Math.</a> <b>22</b> (3) (2008), 1187-1204.</li> <li> <SPAN onMouseOver="orthostab.style.display=''" onMouseOut="orthostab.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="orthostab" STYLE="display:none"><font size="-1"> An orthogonal subdivision in <i>d</i>-space is the partition of the space into axis-aligned boxes. It is shown that for any orthogonal subdivision of size <i>n</i>, there is an axis-parallel line that intersects the interior of (that is, <i>stabs</i>) at least <i>&Omega;(</i>log<i><sup>1/(d-1)</sup>n)</i> boxes. Constructions are also given for <i>d&ge;2</i>, where this bound is attained. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://portal.acm.org/citation.cfm?id=1065167.1065211">Space complexity of hierarchical heavy hitters in multi-dimensional data streams</a>,</b> <ul type="circle"> <li>John Hershberger, Nisheeth Shrivastava, Subhash Suri, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://cimic.rutgers.edu/%7Esigmod05/">24th Sympos. on Principles of Database Systems</a> (Baltimore, MD, 2005)</i>, ACM Press, pp. 338-347.</li> <li> <SPAN onMouseOver="hhh.style.display=''" onMouseOut="hhh.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="hhh" STYLE="display:none"><font size="-1"> <i>Heavy hitters</i> are items occurring with frequency above a given threshold, they are an important aggregation and summary tool for processing data streams. Hierarchical heavy hitters (HHHs) have been introduced as a generalization for hierarchical data domains, including multi-dimensional data. An item <i>x</i> in a hierarchy is called a &phi;-HHH if its frequency <i>after discounting the frequencies of all its descendant hierarchical heavy hitters</i> exceeds &phi;<i>n</i>, where &phi; is a user-specified parameter and <i>n</i> is the size of the data set. Recently, single-pass schemes have been proposed for computing &phi;-HHHs using space roughly O(log(&phi;<i>n</i>)/&phi;). The frequency estimates of these algorithms, however, hold only for the <i>total frequencies</i> of items, and not the discounted frequencies; this leads to <i>false positives</i> because the discounted frequency can be significantly smaller than the total frequency. This paper attempts to explain the difficulty of finding hierarchical heavy hitters with better accuracy. We show that a single-pass deterministic scheme that computes &phi;-HHHs in a <i>d</i>-dimensional hierarchy with any approximation guarantee must use &Omega;(1/&phi;<sup>d+1</sup>) space. This bound is tight: we present a data stream algorithm that can report the &phi;-HHHs without false positives in O(1/&phi;<sup>d+1</sup>) space. </font> </span> </li> </ul> </li> <br> <li><b><a href="http://doi.acm.org/10.1145/1064092.1064098">Incidences of not-too-degenerate hyperplanes</a>,</b> <ul type="circle"> <li>Gy&ouml;rgy Elekes and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.socg05.org/">21st Sympos. Comput. Geom.</a> (Pisa, 2005)</i>, ACM Press, pp. 16-21.</li> <li> <SPAN onMouseOver="elest.style.display=''" onMouseOut="elest.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="elest" STYLE="display:none"><font size="-1"> We prove a new Szemer&eacute;di-Trotter-type bound on point-hyperplane incidences in <i>d</i>-space. One have to make some restriction on the incidences, otherwise <i>m</i> hyperplane can contain a line incident to all <i>n</i> points, the number of incidences is <i>mn</i>, and there's no non-trivial upper bound. In this paper we consider <i>saturated</i> hyperplanes only. In 3-space a plane containing <i>k</i> points is <i>saturated</i> if these points span at least <i>&Omega;(k<sup>2</sup>)</i> distinct lines. We show that the number of saturated planes containing <i>k</i> or more points is bounded by <i>O(n<sup>d</sup>/k<sup>d+1</sup>+n<sup>d-1</sup>/k<sup>d-1</sup>)</i>. This is equivalent with the Szemer&eacute;di-Trotter Theorem for <i>d=2</i>, and it is tight for all <i>d&ge;2</i>. </font> </span> (<a href="elest.pdf">pdf</a>) </li> </ul> </li> <br> <li><b><a href="encomp.ps.gz">Pointed and colored binary encompassing trees</a>,</b> <ul type="circle"> <li>Michael Hoffmann and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.socg05.org/">21st Sympos. Comput. Geom.</a> (Pisa, 2005)</i>, ACM Press, pp. 81-90.</li> <li> <SPAN onMouseOver="pointcolored.style.display=''" onMouseOut="pointcolored.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="pointcolored" STYLE="display:none"><font size="-1"> This is a generalization of several previous results on augmenting planar straight line graphs (Bose, Houle, and Toussaint, 2001) and on bounded degree spanning trees for colored points in the plane (Kaneko, 2000). Assume that we are given a disconnected vertex-colored planar straight line graph <i>G</i>, with no singleton component. We want to augment <i>G</i> to a connected graph <i>G'</i>, <i>G&sube;G'</i>, by adding new straight line edges that respect the coloring and keep the graph plane. It is shown that this can be done so that the degree of every vertex increases by at most two. The bound <i>two</i> is best possible. </font> </span> </li> </ul> </li> <br> <li><b> <a href="http://dx.doi.org/10.1016/j.comgeo.2006.12.005">Pointed binary encompassing trees: simple and optimal</a>,</b> <ul type="circle"> <li>Michael Hoffmann, Bettina Speckmann, and Csaba D. T&oacute;th,</li> <li><i>Abstracts of <a href="http://cgw2004.csail.mit.edu/">14th Annual Fall Workshop on Computational Geometry</a> (Cambridge, MA, 2004),</i> pp. 28-29.</li> <li><i>Abstracts of <a href="http://www.win.tue.nl/EWCG2005/">21st European Workshop on Comput. Geom.</a> (Eidhoven, 2005),</i> pp. 93-96.</li> <li><a href="http://www.sciencedirect.com/science/journal/09257721">Comput. Geom. Theory Appl.</a> <b>43</b> (1) (2010), 35-41.</li> </ul> </li> <br> <li><b><a href="http://csabatoth.org/sentinel.pdf">Detecting cuts in sensor networks</a>,</b> <ul type="circle"> <li>Nisheeth Shrivastava, Subhash Suri, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.ece.wisc.edu/%7Eipsn05/">4th International Conference on Information Processing in Sensor Networks</a> (Los Angeles, CA, 2005)</i>, IEEE, pp. 210-217.</li> <li><a href="http://doi.acm.org/10.1145/1340771.1340776"><i>ACM Transactions on Sensor Networks</i></a> <b>4</b> (2) (2008), article 10.</li> <li> <SPAN onMouseOver="sentinel.style.display=''" onMouseOut="sentinel.style.display='none'"> <font color="#6600000">(abstract)</font> </SPAN> <span ID="sentinel" STYLE="display:none"><font size="-1"> This is a result about "two-sided" &epsilon;-nets. Given a set <i>P</i> of <i>n</i> points in the plane, an <i>&epsilon;-sentinel set</i> is a subset <i>S&sube;P</i> such that for every directed query line <i>L</i> we can decide whether at least <i>&epsilon;|P|</i> points of less than <i>&epsilon;|P|/2</i> lie on the left side of <i>L</i> based on how <i>L</i> partitions the sentinel set <i>S</i>. By contrast, if <i>&epsilon;|P|</i> points are on the left side of <i>L</i>, then a point of any &epsilon;-net <i>N</i> must also be on the that side; but if a point of <i>N</i> is on the left side of <i>L</i>, then there might be as few as just one point on that side. We show that there is an &epsilon;-sentinel set of size <i>O(</i>1/&epsilon;<i>)</i> for every set of <i>n</i> points in the plane, which is best possible, and we propose efficient algorithms to compute an &epsilon;-sentinel set of size <i>O(</i>1/&epsilon;<i>)</i>. </font> </span> </li> </ul> </li> <br> <li><b><a href="msri.ps.gz">Binary space partitions: recent developments</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th,</li> <li>in <i>Combinatorial and Computational Geometry</i>, vol. <a href="http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=0521848628">52</a> of MSRI Publications, Cambridge University Press, 2005, pp. 529-556.</li> </ul> </li> <br> <li><b><a href="hsst.pdf">Adaptive spatial partitioning for multidimensional data streams</a>,</b> <ul type="circle"> <li>John Hershberger, Nisheeth Shrivastava, Subhash Suri, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://www.cs.ust.hk/%7Eisaac04">15th International Symposium on Algorithms and Computation</a> (Hong Kong, 2004)</i>, LNCS <a href="http://dx.doi.org/10.1007/978-3-540-30551-4_46">3341</a>, Springer, pp. 522-533.</li> <li><i><a href="http://dx.doi.org/10.1007/s00453-006-0070-3">Algorithmica</a></i> <b>46</b> (2006), 97-117. </li> </ul> </li> <br> <li><b><a href="fincaan.ps.gz">Congestion games, load balancing, and price of anarchy,</a></b> <ul type="circle"> <li>Anshul Kothari, Subhash Suri, Csaba D. T&oacute;th, and Yunhong Zhou, </li> <li>in <i>Proc. <a href="http://db.uwaterloo.ca/%7Ealopez-o/caan.html">Workshop on Combinatorial and Algorithmic Aspects of Networking</a> (Banff, AB, 2004)</i>, LNCS <a href="http://dx.doi.org/10.1007/11527954_3">3405</a>, Springer, 2005, pp. 13-27.</li> </ul> </li> <br> <li><b><a href="hkrt.ps.gz">Encompassing colored crossing-free geometric graphs,</a></b> <ul type="circle"> <li>Ferran Hurtado, Mikio Kano, David Rappaport, and Csaba D. T&oacute;th, </li> <li>in <i> Proc. <a href="http://www.cs.concordia.ca/cccg">16th Canadian Conf. Comput. Geom.</a> (Montr&eacute;al, QC, 2004),</i> pp. 48-52.</li> <li><a href="http://dx.doi.org/10.1016/j.comgeo.2007.05.006">Comput. Geom. Theory Appl.</a> <b>39</b> (2008), 14-23. </li> </ul> </li> <br> <li><b><a href="encomptree.ps.gz">Pointed binary encompassing trees,</a></b> <ul type="circle"> <li><a href="http://www.inf.ethz.ch/personal/hoffmann/">Michael Hoffmann</a>, <a href="http://www.win.tue.nl/%7Especkman/">Bettina Speckmann</a>, and Csaba D. T&oacute;th, </li> <li><i>Abstracts of <a href="http://www.us.es/ewcg04/">20th European Workshop on Comput. Geom.</a> (Seville, 2004),</i> pp. 131-314. </li> <li>in <i>Proc. <a href="http://swat.diku.dk/">9th Scandinavian Workshop on Algorithm Theory</a> (Humleb&aelig;k, 2004)</i>, LNCS 3111, Springer, pp. 442-454.</li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1007/s00453-006-1211-4">Selfish load balancing and atomic congestion games,</a></b> <ul type="circle"> <li>Subhash Suri, Csaba D. T&oacute;th, and Yunhong Zhou, </li> <li>in <i>Proc. <a href="http://www.cs.dartmouth.edu/SPAA/">16th ACM Sympos. on Parallelism in Algorithms and Architectures</a> (Barcelona, 2004)</i>, ACM Press, 2004, pp. 188-195.</li> <li><i><a href="http://www.springerlink.com/openurl.asp?genre=journal&amp;issn=0178-4617">Algorithmica</a></i> <b>47</b> (1) (2007), 79-96.<br> </li> <li>(<a href="stz.pdf">pdf</a>)</li> </li> </ul> </li> <br> <li><b><a href="range.ps.gz">Range counting over multidimensional data streams,</a></b> <ul type="circle"> <li>Subhash Suri, Csaba D. T&oacute;th, and Yunhong Zhou,</li> <li>in <i>Proc. <a href="http://socg.poly.edu/home.htm">20th Sympos. Comput. Geom.</a> (Brooklyn, NY, 2004)</i>, ACM Press, pp. 160-169.</li> <li><a href="http://dx.doi.org/10.1007/s00454-006-1269-4">Discrete Comput. Geom.</a> <b>36</b> (2006), 633-655.<br> </li> </ul> </li> <br> <li><b><a href="subdiv.ps.gz"> Binary space partition of orthogonal subdivisions,</a></b> <ul type="circle"> <li>John Hershberger, Subhash Suri, and Csaba D. T&oacute;th, </li> <li>in <i>Proc. <a href="http://socg.poly.edu/home.htm">20th Sympos. Comput. Geom.</a> (Brooklyn, NY, 2004)</i>, ACM Press, pp. 230-238.</li> <li><a href="http://www.siam.org/journals/sicomp/sicomp.htm">SIAM J. Comput.</a> <b>34</b> (6) (2005), 1380-1397. </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1007/978-3-540-30183-7_12">Uncoordinated load balancing and congestion games in P2P systems,</a></b><br> <ul type="circle"> <li>Subhash Suri, Csaba D. T&oacute;th, and Yunhong Zhou, </li> <li>in <i>Proc. <a href="http://iptps04.cs.ucsd.edu/"> 3rd Internat. Workshop on Peer-to-Peer Systems</a> (La Jolla, CA, 2004)</i>, LNCS 3279, Springer, pp. 123-130. </li> </ul> </li> <br><li><a href="http://www.win.tue.nl/~speckman/papers/DegreeBoundsConstrainedPseudo.pdf"><b>Degree bounds for constrained pseudo-triangulations, </b> </a> <ul type="circle"> <li><a href="http://www.cis.tugraz.at/igi/oaich">Oswin Aichholzer</a>, <a href="http://www.inf.ethz.ch/%7Ehoffmann">Michael Hoffmann</a>, <a href="http://www.win.tue.nl/%7Especkman/">Bettina Speckmann</a>, and Csaba D. T&oacute;th, </li> <li>in <i>Proc. <a href="http://www.cs.dal.ca/%7Ecccg/">15th Canadian Conf. Comput. Geom.</a> (Halifax, NS, 2003)</i>, pp. 155-158.</li> </ul> </li> <br> <li><a href="http://www.siam.org/journals/sicomp/38-1/65934.html"><b>Binary space partition for axis-aligned fat rectangles,</b></a> <ul type="circle"> <li>Csaba D. T&oacute;th, </li> <li>in <i>Proc. <a href="http://www.conferences.hu/ALGO2003/">11th European Symposium on Algorithms</a> (Budapest, 2003)</i>, LNCS 2832, Springer, pp. 494-505.</li> <li><a href="http://epubs.siam.org/sicomp">SIAM J. Comput.</a> <b>38</b> (1) (2008), 429-447.</li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1007/s00373-006-0669-9">Alternating paths along axis-parallel segments</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th, </li> <li><i>Abstracts of <a href="http://cg03.cs.uni-bonn.de/">19th European Wrokshop on Comput. Geom.</a> (Bonn, 2003),</i> pp. 133-136.</li> <li>in <i>Proc. <a href="http://www.wads.org">8th Workshop on Algorithms and Data Structures</a> (Ottawa, ON, 2003)</i>, LNCS 2748, Springer, 2003, pp. 389-400.</li> <li><a href="http://www.springerlink.com/openurl.asp?genre=journal&amp;issn=0911-0119">Graphs and Combinatorics</a> <b>22</b> (2006), 527-543. </li> <li>(<a href="axispath.pdf">pdf</a>) </ul> </li> <br> <li><a href="preprint.ps.gz"><b>Allocating vertex <i>&#960;</i>-guards in simple polygons via pseudo-triangulations</b><b>, </b> </a> <ul type="circle"> <li><a href="http://www.win.tue.nl/%7Especkman/">Bettina Speckmann</a> and Csaba D. T&oacute;th, </li> <li>in <i>Proc. <a href="http://www.siam.org/meetings/da03/">14th ACM-SIAM Sympos. on Discrete Algorithms</a> (Baltimore, MD, 2003),</i> ACM Press, 2003, 109-118. </li> <li><a href="http://link.springer-ny.com/link/service/journals/00454/tocs.html">Discrete Comput. Geom.</a> <b>33</b> (2) (2005), 345-364.</li> </ul> <br> </li> <li> <a href="paper.ps.gz"><b>Illuminating disjoint line segments in the plane,</b></a> <ul type="circle"> <li>Csaba D. T&oacute;th, </li> <li><a href="http://link.springer-ny.com/link/service/journals/00454/tocs.html">Discrete Comput. Geom.</a> <b>30</b> (3) (2003), 489-505.</li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1016/S0020-0190%2803%2900349-1">Alternating paths through disjoint line segments</a>,</b> <ul type="circle"> <li><a href="http://www.inf.ethz.ch/%7Ehoffmann">Michael Hoffmann</a> and Csaba D. T&oacute;th,</li> <li><i>Abstracts of the </i><i><a href="http://ewcg2002.mimuw.edu.pl/">18th European Workshop on Comput. Geom.</a> (Warsaw, 2002),</i></li> <li> <a href="http://www.sciencedirect.com/science/journal/00200190">Inform. Proc. Letts.</a> <b>87</b> (6) (2003), 287-294.</li> </ul> </li> <br> <li> <b><a href="diss5.ps.gz">Planar subdivisions,</a></b> <ul type="circle"> <li>Csaba D. T&oacute;th, </li> <li>PhD thesis, <a href="http://e-collection.ethbib.ethz.ch/diss/sg/09x.html">DISS ETH </a>No. 14628, ETH Z&uuml;rich, 2002. </li> </ul> </li> <br> <li><a href="rev-direct.ps.gz"><b>Binary space partition for line segments with a limited number of directions,</b></a> <ul type="circle"> <li>Csaba D. T&oacute;th,</li> <li>in <i><a href="http://portal.acm.org/citation.cfm?id=545381.545443&amp;coll=portal&amp;dl=ACM&amp;type=series&amp;idx=SERIES422&amp;part=series&amp;WantType=Proceedings&amp;title=Symposium%20on%20Discrete%20Algorithms&amp;CFID=4102605&amp;CFTOKEN=1986427">Proc. 13th ACM-SIAM Sympos. on Discrete Algorithms</a> (San Francisco, CA, 2002)</i>, ACM Press, 2002, 465-471. </li> <li><a href="http://www.siam.org/journals/sicomp/sicomp.htm">SIAM J. Comput.</a> <b>32</b> (2) (2003), 307-325.</li> </ul> </li> <br> <li> <b><a href="http://dx.doi.org/10.1007/s00454-002-2896-z">The <i>k</i> most frequent distances in the palne</a>,</b> <ul type="circle"> <li><a href="http://www.math.ubc.ca/~solymosi/">J&oacute;zsef Solymosi</a>, <a href="http://www.renyi.hu/%7Etardos">G&aacute;bor Tardos</a>, and Csaba D. T&oacute;th, </li> <li><a href="http://link.springer-ny.com/link/service/journals/00454/tocs.html">Discrete Comput. Geom.</a> <b>28 </b>(4) (2002), 639-648.</li> </ul> </li> <br> <li><b> <a href="http://dx.doi.org/10.1016/S0925-7721%2801%2900057-8">Illumination in the presence of opaque line segments in the plane</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th, </li> <li><a href="http://www.sciencedirect.com/science/journal/09257721">Comput. Geom. Theory Appl.</a> <b>21</b> (3) (2002), 193-204.</li> </ul> </li> <br> <li><b> <a href="http://dx.doi.org/10.1016/S0925-7721%2801%2900024-4"> Art galleries with guards of uniform range of vision</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th, </li> <li><a href="http://www.sciencedirect.com/science/journal/09257721">Comput. Geom. Theory Appl.</a> <b>21</b> (3) (2002), 185-192.</li> </ul> </li> <br> <li><b> <a href="http://dx.doi.org/10.1016/S0925-7721%2802%2900172-4">Segment endpoint visibility graphs are Hamiltonian</a>,</b> <ul type="circle"> <li><a href="http://www.inf.ethz.ch/%7Ehoffmann">Michael Hoffmann</a> and Csaba D. T&oacute;th, </li> <li>in <i><a href="http://compgeo.math.uwaterloo.ca/%7Ecccg01/proceedings/">Proc. 13th Canadian Conference on Comput. Geom.</a> (Waterloo, ON, 2001)</i>, 109-112.</li> <li><a href="http://www.sciencedirect.com/science/journal/09257721">Comput. Geom. Theory Appl.</a> <b>26</b> (1) (2003), 47-68. </li> </ul> </li> <br> <li><a href="fin-lower.ps.gz"><b>A note on binary plane partitions</b><b>, </b> </a> <ul type="circle"> <li>Csaba D. T&oacute;th, </li> <li>in <i><a href="http://www.acm.org/pubs/contents/proceedings/compgeom/378583/">Proc. 17th Sympos. on Comput. Geom.</a> (Medford, MA, 2001)</i>, ACM Press, 2001, 151-156. </li> <li><a href="http://link.springer-ny.com/link/service/journals/00454/tocs.html">Discrete Comput. Geom.</a> <b>30</b> (1) (2003), 3-16.</li> </ul> </li> <br> <li> <b><a href="http://dx.doi.org/10.1007/s00454-001-0009-z">Distinct distances in the plane</a>,</b> <ul type="circle"> <li><a href="http://www.math.ubc.ca/~solymosi">J&oacute;zsef Solymosi</a> and Csaba D. T&oacute;th, </li> <li>in <i><a href="http://dx.doi.org/10.1007/s00454-001-0009-z">Proc. 17th Sympos. on Comput. Geom.</a> (Medford, MA, 2001)</i>, ACM Press, 2001, 29-31. </li> <li><a href="http://link.springer-ny.com/link/service/journals/00454/tocs.html">Discrete Comput. Geom.</a> <b>25 </b>(4) (2001), 629-634.</li> </ul> </li> <br> <li> <b><a href="http://dx.doi.org/10.1007/3-540-45545-0_89">Illuminating polygons with vertex <i>&#960;</i>-floodlights</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th, </li> <li>in <i>Proc. Int. Conf. on Comput. Sci. (San Francisco, CA, 2001) Part I</i>, LNCS <a href="http://dx.doi.org/10.1007/3-540-45545-0_89">2073</a>, Springer, 2001, 772-781. </li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1002/net.20094">Fault tolerant on-board networks with priorities</a></b>, <ul type="circle"> <li>Jean-Claude Bermond, Fr&eacute;d&eacute;ric Havet, and Csaba D. T&oacute;th,</li> <li>in <i>Proc. <a href="http://algotel.ief.u-psud.fr/">3rd AlgoTel</a> (Saint-Jean-de-Luz, 2001)</i>, pp. 95-98.</li> <li><a href="http://www3.interscience.wiley.com/cgi-bin/jhome/32046">Networks</a> <b>47</b> (1) (2006), 9-25.</li> </ul> </li> <br> <li> <b><a href="http://dx.doi.org/10.1016/S0925-7721%2802%2900130-X">Guarding disjoint triangles and claws in the plane</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th,</li> <li>in <i>Abstracts of the 17th European Workshop on Comput. Geom. (Berlin, 2001),</i></li> <li><a href="http://www.sciencedirect.com/science/journal/09257721">Comput. Geom. Theory Appl.</a> <b>25</b> (1-2) (2003), 51-65.</li> </ul> </li> <br> <li> <b><a href="http://dx.doi.org/10.1007/3-540-47738-1_35">Illuminating both sides of line segments</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th, </li> <li>in: <i>Discrete and Computational Geometry (J. Akiyama, M. Kano, M. Urabe, eds.)</i>, LNCS <a href="http://dx.doi.org/10.1007/3-540-47738-1_35">2098</a>, Springer, 2001, 370-380. </li> </ul> </li> <br> <li> <b><a href="http://dx.doi.org/10.1016/S0166-218X%2803%2900296-8">Illuminating labyrinths</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th, </li> <li>in <i>Abstracts of <a href="http://opt.math.uni-rostock.de/odsa/">Optimal Discrete Structures and Algorithms</a> (Rostock, 2000).</i> </li> <li><a href="http://www.sciencedirect.com/science/journal/0166218X">Discrete Appl. Maths.</a> <b>138</b> (1-2) (2004), 215-228.</li> </ul> </li> <br> <li><b><a href="http://dx.doi.org/10.1016/S0925-7721%2800%2900023-7">Art gallery problem with guards whose range of vision is <i>180&ordm;</i></a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th, </li> <li><a href="http://www.sciencedirect.com/science/journal/09257721">Comput. Geom. Theory Appl.</a> <b>17</b> (3-4) (2000), 121-134. </li> </ul> </li> <br> <li> <b><a href="http://dx.doi.org/10.1016/S0012-365X%2802%2900583-6">Illumination of polygons with 45&ordm;-floodlights</a>,</b> <ul type="circle"> <li>Csaba D. T&oacute;th, </li> <li>Presented at the <i>4th Geometry Festival (Budapest, 1999)</i>. </li> <li><a href="http://www.sciencedirect.com/science/journal/0012365X">Discrete Maths.</a> <b>265</b> (1-3) (2003), 251-260.</li> </ul> </li> <br> <li> <b><a href="http://dx.doi.org/10.1145/305619.305639">All-to-all routing and coloring in weighted trees of rings</a>,</b> <ul type="circle"> <li><a href="http://www-sop.inria.fr/mascotte/Bruno.Beauquier/">Bruno Beauquier</a>, <a href="http://www-sop.inria.fr/mascotte/personnel/Stephane.Perennes/">St&eacute;phane P&eacute;rennes</a>, and David T&oacute;th,</li> <li>in <i>Proc. 11th ACM Sympos. on Parallel Algorithms and Architectures (Saint-Malo, 1999)</i>, ACM Press, 1999, 185-190.</li> </ul> </li> </ul> <br> <br> <b><i> <a href="http://csabatoth.org/manu.html"><font size="+1">Manuscripts</font></a> </i></b><br><br> <br> <br> <br> </body> </html>