Csaba D. Toth
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Csaba D. Toth has a total of 39 co-authors. Here are the top co-authors by number of shared publications:
- Adrian Dumitrescu
Department of Computer Science University of Wisconsin-Milwaukee USA
6 shared publications - Diane L. Souvaine
Tufts University
5 shared publications - Adrian Dumitrescu
Algoresearch L.L.C.
4 shared publications - Adam Sheffer
School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel
3 shared publications - Micha Sharir
School of Computer Science, Tel Aviv University, Tel Aviv, Israel
3 shared publications - André Schulz
Institut für Mathematische Logik und Grundlagenforschung Universität Münster Germany
2 shared publications
Latest Publications
- 1 November 2013
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 44, 345-350
Diffuse Reflections in Simple Polygons
- 1 November 2013
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 44, 345-350
Diffuse Reflections in Simple Polygons
- 1 October 2013
- Published by Elsevier in Computational Geometry
- Vol. 46 (8) , 945-958
A tight bound for point guards in piecewise convex art galleries
- 1 October 2013
- Published by Elsevier in Computational Geometry
- Vol. 46 (8) , 945-958
A tight bound for point guards in piecewise convex art galleries
- Open Access
Covering Paths for Planar Point Sets
Given $n$ points in the plane, a \emph{covering path} is a polygonal path that visits all the points. If no three points are collinear, every covering path requires at least $n/2$ segments, and $n-1$ straight line segments obviously suffice even if the covering path is required to be noncrossing. We show that every set of $n$ points in the plane admits a (possibly self-crossi ng) covering path consisting of $n/2 +O(n/\log{n})$ straight line segments. If the path is required to be noncrossing, we prove that $(1-\eps)n$ straight line segments suffice for a small constant $\eps>0$, and we exhibit $n$-element point sets that require at least $5n/9 -O(1)$ segments in every such path. Further, the analogous question for noncrossing \emph{covering trees} is considered and similar bounds are obtained. Finally, it is shown that computing a noncrossing covering path for $n$ points in the plane requires $\Omega(n \log{n})$ time in the worst case.Open AccessCovering Paths for Planar Point Sets
Given $n$ points in the plane, a \emph{covering path} is a polygonal path that visits all the points. If no three points are collinear, every covering path requires at least $n/2$ segments, and $n-1$ straight line segments obviously suffice even if the covering path is required to be noncrossing. We show that every set of $n$ points in the plane admits a (possibly self-crossi ng) covering path consisting of $n/2 +O(n/\log{n})$ straight line segments. If the path is required to be noncrossing, we prove that $(1-\eps)n$ straight line segments suffice for a small constant $\eps>0$, and we exhibit $n$-element point sets that require at least $5n/9 -O(1)$ segments in every such path. Further, the analogous question for noncrossing \emph{covering trees} is considered and similar bounds are obtained. Finally, it is shown that computing a noncrossing covering path for $n$ points in the plane requires $\Omega(n \log{n})$ time in the worst case. - 29 October 2012
- Published by Springer Nature
- p. 327-354
Plane Geometric Graph Augmentation: A Generic Perspective
- 29 October 2012
- Published by Springer Nature
- p. 327-354
Plane Geometric Graph Augmentation: A Generic Perspective
- 29 October 2012
- Published by Springer Nature
- p. 303-325
Counting Plane Graphs: Flippability and Its Applications
- 29 October 2012
- Published by Springer Nature
- p. 303-325
Counting Plane Graphs: Flippability and Its Applications
- 11 August 2012
- Published by Springer Nature in Algorithmica
- Vol. 68 (2) , 448-482
Relative Convex Hulls in Semi-Dynamic Arrangements
- 11 August 2012
- Published by Springer Nature in Algorithmica
- Vol. 68 (2) , 448-482
Relative Convex Hulls in Semi-Dynamic Arrangements
- Open Access
Packing anchored rectangles
Let $S$ be a set of $n$ points in the unit square $[0,1]^2$, one of which is the origin. We construct $n$ pairwise interior-disjoint axis-aligned empty rectangles such that the lower left corner of each rectangle is a point in $S$, and the rectangles jointly cover at least a positive constant area (about 0.09). 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.Open AccessPacking anchored rectangles
Let $S$ be a set of $n$ points in the unit square $[0,1]^2$, one of which is the origin. We construct $n$ pairwise interior-disjoint axis-aligned empty rectangles such that the lower left corner of each rectangle is a point in $S$, and the rectangles jointly cover at least a positive constant area (about 0.09). 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. - 31 May 2012
- Published by Elsevier in Computational Geometry
- Vol. 45 (4) , 169-177
Graphs that admit right angle crossing drawings
- 31 May 2012
- Published by Elsevier in Computational Geometry
- Vol. 45 (4) , 169-177
Graphs that admit right angle crossing drawings
- Open Access
Conflict-free graph orientations with parity constraints
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 two types of constraints for a multigraph G=(V,E): (1) an exact conflict constraint is an edge set C in E and a vertex v in V such that C should not equal the set of incoming edges at v; (2) a subset conflict constraint is an edge set C in E and a vertex v in V such that C should not be a subset of incoming edges at v. 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 disjoint exact or subset conflict pairs.
Open AccessConflict-free graph orientations with parity constraints
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 two types of constraints for a multigraph G=(V,E): (1) an exact conflict constraint is an edge set C in E and a vertex v in V such that C should not equal the set of incoming edges at v; (2) a subset conflict constraint is an edge set C in E and a vertex v in V such that C should not be a subset of incoming edges at v. 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 disjoint exact or subset conflict pairs.
- Open Access
Counting Plane Graphs: Flippability and its Applications
We generalize the notions of flippable and simultaneously flippable edges in a triangulation of a set S of points in the plane to so-called \emph{pseudo-simultaneously flippable edges}. Such edges are related to the notion of convex decompositions spanned by S. We prove a worst-case tight lower bound for the number of pseudo-simultaneously flippable edges in a triangulation in terms of the number of vertices. We use this bound for deriving new upper bounds for the maximal number of crossing-free straight-edge graphs that can be embedded on any fixed set of N points in the plane. We obtain new upper bounds for the number of spanning trees and forests as well. Specifically, let tr(N) denote the maximum number of triangulations on a set of N points in the plane. Then we show (using the known bound tr(N) < 30^N) that any N-element point set admits at most 6.9283^N * tr(N) < 207.85^N crossing-free straight-edge graphs, O(4.7022^N) * tr(N) = O(141.07^N) spanning trees, and O(5.3514^N) * tr(N) = O(160.55^N) forests. We also obtain upper bounds for the number of crossing-free straight-edge graphs that have cN, fewer than cN, or more than cN edges, for any constant parameter c, in terms of c and N.
Open AccessCounting Plane Graphs: Flippability and its Applications
We generalize the notions of flippable and simultaneously flippable edges in a triangulation of a set S of points in the plane to so-called \emph{pseudo-simultaneously flippable edges}. Such edges are related to the notion of convex decompositions spanned by S. We prove a worst-case tight lower bound for the number of pseudo-simultaneously flippable edges in a triangulation in terms of the number of vertices. We use this bound for deriving new upper bounds for the maximal number of crossing-free straight-edge graphs that can be embedded on any fixed set of N points in the plane. We obtain new upper bounds for the number of spanning trees and forests as well. Specifically, let tr(N) denote the maximum number of triangulations on a set of N points in the plane. Then we show (using the known bound tr(N) < 30^N) that any N-element point set admits at most 6.9283^N * tr(N) < 207.85^N crossing-free straight-edge graphs, O(4.7022^N) * tr(N) = O(141.07^N) spanning trees, and O(5.3514^N) * tr(N) = O(160.55^N) forests. We also obtain upper bounds for the number of crossing-free straight-edge graphs that have cN, fewer than cN, or more than cN edges, for any constant parameter c, in terms of c and N.