Sergio - Publications

Pankaj K. Agarwal, Oswin Aichholzer, Mark de Berg, Prosenjit K. Bose, Kevin Buchin, Erin W. Chamber, Otfried Cheong, Éric Colin de Verdière, Erik D. Demaine , José Miguel Díaz-Báñez, Matt deVos, Steven van Dijk, David Eppstein, Jeff Erickson, Ruy Fabila-Monroy, David Flores-Peñaloza, Marta Fort, Panos Giannopoulos, Joachim Gudmundsson, Thomas Hackl, Sariel Har-Peled, Clemens Huemer, Ferran Hurtado, Sandi Klavžar, Christian Knauer, Marc van Kreveld, Herman Haverkort, Stefan Langerman, Francis Lazarus, Giuseppe Liotta, Yuanxin (Leo) Liu, Maarten Löffler, Jun Luo, Andrea Mantler, Dániel Marx, Henk Meijer, Bojan Mohar, René van Oostrum, Carles Padró, Günter Rote, Germán Sáez, Carlos Seara, J. Antoni Sellarès, Micha Sharir, Rodrigo I. Silveira, Jack Snoeyink, Bettina Speckmann, Tycho Strijk, Remco C. Veltkamp, Jorge Urrutia, Inma Ventura, Kevin Verbeek, Thomas Wolle, David R. Wood, and Arjana Žitnik.

Publications (journal and conference versions are together)

Finding shortest non-trivial cycles in directed graphs on surfaces.
With É. Colin de Verdière and F. Lazarus.
Submitted.

Output-sensitive algorithm for the edge-width of an embedded graph.
With É. Colin de Verdière and F. Lazarus.
Submitted.

Adding one edge to planar graphs makes crossing number hard.
With B. Mohar.
Submitted.

Geometric simultaneous embeddings of a graph and a matching. [draft]
With M. van Kreveld, G. Liotta, H. Meijer, B. Speckmann, and K. Verbeek.
Invited and submitted to the special issue of JGAA devoted to selected papers from GD09.
Presented at 17th International Symposium on Graph Drawing (GD 09).

The Fibonacci dimension of a graph. [draft]
With D. Eppstein and S. Klavžar.
Submitted to journal.
[Visuals]

Finding the most relevant fragments in networks. [draft]
With K. Buchin, J. Gudmundsson, M. Löffler, J. Luo, G. Rote, R. I. Silveira, B. Speckmann, and T. Wolle.
Full version submitted to journal.
Preliminary version with title Detecting Hotspots in Geographic Networks was presented at AGILE 2009; best paper award.

Finding shortest contractible and shortest separating cycles in embedded graphs. [draft]
Accepted to ACM Transactions on Algorithms, special issue devoted to SODA 09.
Preliminary version in SODA 2009.

Crossing and weighted crossing number of near-planar graphs. [draft]
With B. Mohar.
Accepted to Algorithmica.
Preliminary version presented at Graph Drawing 2008.

Edge-removal and non-crossing configurations in geometric graphs. [draft]
With O. Aichholzer, R. Fabila-Monroy, D. Flores-Peñaloza, T. Hackl, C. Huemer, F. Hurtado, and D. R. Wood.
Full version submitted to journal.
Preliminary version presented at EuroCG 2008.

Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension. [draft]
With P. Giannopoulos, C. Knauer, D. Marx, and G. Rote.
Accepted to ACM Transactions on Algorithms.
Preliminary version (without D. Marx and missing results) in SODA 2008, 836--843.
[visuals]

Algorithms for graphs of bounded treewidth via orthogonal range searching. [draft]
With C. Knauer.
Computational Geometry: Theory and Applications 42 (2009) 815--824.
Preliminary version will be presented at EuroCG 2008.

Finding one tight cycle. [draft]
With M. DeVos, J. Erickson, and B. Mohar.
Accepted to ACM Transactions on Algorithms, special issue devoted to SODA 08.
Preliminary version in SODA 2008, pp 527--531.

Multiple source shortest paths in a genus g graph.
With E. W. Chambers and J. Erickson.
Full version in preparation.
Preliminary version (without J. Erickson and worse time bounds) in SODA'07, pp 89--97.

Obnoxious centers in graphs. [draft]
With G. Rote.
Full version submitted to journal.
Preliminary version in SODA 2007, pp 98--107.

Computing a center-transversal line. [draft]
With P. K. Agarwal, J. A. Sellarès, and M. Sharir.
Full version submitted to journal.
Preliminary version in FSTTCS 2006, LNCS 4337, 93--104.

Higher-order Voronoi diagrams on triangulated surfaces. [draft]
With M. Fort and J.A. Sellarès.
Information Processing Letters 109 (2009) 440--445.

Covering many or few points with unit disks. [draft]
With M. de Berg and S. Har-Peled.
Theory of Computing Systems, to appear (special issue on WAOA 2006).
Preliminary version in WAOA 2006, LNCS 4368, pp 55--68, 2007.
[visuals]

Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. [draft]
Journal of Graph Algorithms and Applications 10 (2006) 353--363.
A short version appeared at EWCG'04.

Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. [draft]
With B. Mohar.
Discrete and Computational Geometry 37 (2007) 213--235 .
Preliminary version in ESA 2005,LNCS 3669, pp 131--142, 2005.
[visuals]

Algorithmic aspects of proportional symbol maps. [draft]
With M. van Kreveld, H. Haverkort, and B. Speckmann.
Accepted to Algorithmica.
Preliminary version in ESA 2006, LNCS 4168, pp 720--731, 2006.

On the parameterized complexity of d-dimensional point set pattern matching. [draft]
With P. Giannopoulos, and C. Knauer.
Information Processing Letters 105 (2008) 73--77.
Preliminary version in IWPEC 2006, pp. 175--183, LNCS 4169, 2006.

Covering point sets with two disjoint disks or dquares. [draft]
With J. M. Díaz-Báñez, C. Seara, J. A. Sellarès, J. Urrutia, and I. Ventura.
Computational Geometry: Theory and Applications 40 (2008) 195--206.

Many distances in planar graphs. [draft]
Appeared at SODA'06.
Full version submitted to journal.
[visuals]

Matching point sets with respect to the Earth Mover's Distance. [draft]
With P. Giannopoulos, C. Knauer, and G. Rote.
Computational Geometry: Theory and Applications 39 (2008) 118--133.
A preliminary version appeared at ESA'05 and EWCG'05.

Facility location problems in the plane based on reverse nearest neighbor queries. [full version]
With J. M. Díaz-Báñez, S. Langerman, C. Seara, I. Ventura.
Full version submitted to journal.
A preliminary version appeared at CCCG'05.

Planar embeddings of graphs with specified edge lengths. [draft]
With E. D. Demaine, and G. Rote.
Journal of Graph Algorithms and Applications 11 (2007), pp. 259--276.
A preliminary version appeared at Graph Drawing 2003, LNCS 2912.
Visuals: [Perugia , 2.49MB]

Homotopic Spanners.
With B. Mohar and A. Žitnik.
A short version appeared at EWCG'05. [draft] [visuals]
An expanded version with C. Knauer, A. Por, and G. Rote is in preparation.

Area-Preserving approximations of polygonal paths. [draft]
With P. Bose, S. Cabello, O. Cheong, J. Gudmundsson, M. van Kreveld, and B. Speckmann.
Journal of Discrete Algorithms 4 (2006) 554--566.
A preliminary version was presented at the Japan Conference on Discrete and Computational Geometry, 2004.

Approximation algorithms for spreading points. [draft]
Journal of Algorithms 62 (2007) 49--73.
A preliminary version appeared at WAOA 2004, LNCS 3351.
Visuals: [WAOA, 4.5MB] [Seminar , 7.3MB]

Expected case for projecting points. [draft]
With M. DeVos, and B. Mohar.
Informatica 30 (2006) 289--293 (special issue on TCS'04).
A preliminary version was presented at TCS'04. [visuals]

Schematization of networks. [ draft ]
With M. de Berg, and M. van Kreveld.
Computational Geometry: Theory and Applications 30 (2005) 223--238.
Based on the following two conference publications:

Schematization of road networks.
With M. de Berg, S. van Dijk, M. van Kreveld, and T. Strijk.
Proc. 17th ACM Symp. on Computational Geometry , pages 33--39, 2001. Boston. [ draft ]
Visuals: [SoCG'01 , 1.74MB] [Dagstuhl , 100KB].

Schematic Networks: an Algorithm and its Implementation. [ draft ]
With M. van Kreveld.
Advances in Spatial Data Handling, D.E. Richardson and P. van Oosterom (ed.), pages 475--486. Springer, 2002.
10th International Symposium on Spatial Data Handling (SDH), 2002. Ottawa.
You can have a look here .

Geometric Problems in Cartographic Networks.
PhD Thesis at Utrecht University.
[full version, 3.5MB] [introduction, 250KB]

Testing homotopy for paths in the plane. [ draft ]
With Y. Liu, A. Mantler and J. Snoeyink.
Discrete and Computational Geometry 31 (2004) 61--81 (special issue on 18th SoCG).
A preliminary version appeared at Proc. 18th ACM Symp. on Computational Geometry, 2002. Barcelona.
Visuals: [Seminar , 580KB]

Maximizing the area of overlap of two unions of disks under rigid motion. [full version]
With M. de Berg, P. Giannopoulos, C. Knauer, R. van Oostrum, and R. C. Veltkamp.
Accepted to International J. of Computational Geometry and Applications.
Proc. 9th Scandinavian Workshop on Algorithm Theory, LNCS 3111. (2004)
A short version appeared at EWCG'04.

Approximation algorithms for aligning points. [ draft ]
With M. van Kreveld.
Algorithmica 37 (2003) 211--232.
A preliminary version appeared at Proc. 19th ACM Symp. on Computational Geometry, 2002. Barcelona.
A preliminary version appeared at Fall Workshop on Computational Geometry, 2001.
Visuals: [Fall Workshop]

Secret sharing schemes with detection of cheaters for a general access structure.
With C. Padró, and G. Sáez.
Designs, Codes and Cryptography 25 (2002) 175--188.
A preliminary version appeared at Proc. of the 12th Int. Symp. on Fundamentals of Computation Theory, FCT '99, LNCS 1684. Iasi, Romania.

Sergio's Homepage

List of Publications and Coauthors

Coauthors

Publications (journal and conference versions are together)