Sergio's Homepage

List of Publications and Coauthors

Coauthors

Publications (journal and conference versions are listed together)

• Multiple-source shortest paths in embedded graphs. [draft]
  With E. W. Chambers and J. Erickson.
  Accepted to SIAM J. on Computing.
  Preliminary version, under the title of Multiple source shortest paths in a genus g graph, without J. Erickson and with worse time bounds, appeared in SODA 2007, pp 89--97.
• Parameterized complexity of 1-planarity. [draft]
  With M. J.Bannister and D. Eppstein.
  Accepted to WADS 2013.
• The complexity of separating points in the plane. [draft]
  With P. Giannopoulos.
  Accepted to SoCG 2013.
• Stackelberg shortest path tree game, revisited. [draft]
  Submitted.
• Hardness of approximation for crossing number. [draft]
  Discrete and Computational Geometry 49 (2013) 348-358.
• The clique problem in ray intersection graphs. [draft]
  With J. Cardinal and S. Langermann.
  Submitted to journal.
  Preliminary version in ESA 2012.
• Annotating simplices with a homology basis and its applications. [draft]
  With O. Busaryev, C. Chen, T. K. Dey, and Y. Wang.
  Published in SWAT 2012.
• Minimum cell connection in line segment arrangements. [draft containing also other things related to separation]
  With H. Alt, P. Giannopoulos, and C. Knauer.
  Submitted to journal.
  About half was presented at EuroCG 2011 under the title "On some connection problems in straight-line segment arrangements".
• Covering a bichromatic point set with two disjoint monochromatic disks. [draft]
  With J. M. Díaz-Báñez and P. Pérez-Lantero.
  Computational Geometry: Theory and Applications 46 (2013) 203-212.
• A point calculus for interlevel set homology. [draft]
  With P. Bendich and H. Edelsbrunner.
  Pattern Recognition Letters 33 (2012) 1436-1444.
• Finding cycles with topological properties in embedded graphs. [draft]
  With É. Colin de Verdière and F. Lazarus.
  SIAM Journal on Discrete Mathematics 25 (2011), 1600--1614.
• On the b-chromatic number of regular graphs. [draft]
  With M. Jakovac.
  Discrete Applied Mathematics 159 (2011) 1303-1310.
• The complexity of obtaining a distance-balanced graph.
  With P. Lukšič.
  The Electronic Journal of Combinatorics 18 (2011) p #49 (10 pages).
• The class cover problem with boxes. [draft]
  With S. Bereg, J. M. Díaz-Báñez, P. Pérez-Lantero, C. Seara, and I. Ventura.
  Computational Geometry: Theory and Applications 45 (2012) 294-304.
  Preliminary version presented at EuroCG 2010.
• Finding shortest non-trivial cycles in directed graphs on surfaces.
  With É. Colin de Verdière and F. Lazarus.
  Full version in preparation.
  Preliminary version in Proc. ACM Symp. on Computational Geometry (SOCG), 2010, 156--165.
• Algorithms for the edge-width of an embedded graph. [draft]
  With É. Colin de Verdière and F. Lazarus.
  Computational Geometry: Theory and Applications 45 (2012): 215-224 (special issue of selected papers from SoCG'10).
  Preliminary version in Proc. ACM Symp. on Computational Geometry (SOCG), 2010, 147--155.
• Adding one edge to planar graphs makes crossing number and 1-planarity hard. [draft]
  With B. Mohar.
  Submitted to journal.  
  Preliminary version under the title Adding one edge to planar graphs makes crossing number hard in Proc. ACM Symp. on Computational Geometry (SOCG), 2010, 68--76.
  [Visuals]
• Geometric simultaneous embeddings of a graph and a matching.
  With M. van Kreveld, G. Liotta, H. Meijer, B. Speckmann, and K. Verbeek.
  Journal of Graph Algorithms and Applications 15 (2011) 79--96 (special issue of selected papers from GD09).
  Presented at 17th International Symposium on Graph Drawing (GD 09).
• The Fibonacci dimension of a graph. 
  With D. Eppstein and S. Klavžar.
  The Electronic Journal of Combinatorics 18 (2011) p #55 (23 pages).
  [Visuals]
  
• Finding the most relevant fragments in networks.
  With K. Buchin, J. Gudmundsson, M. Löffler, J. Luo, G. Rote, R. I. Silveira, B. Speckmann, and T. Wolle.
  Journal of Graph Algorithms and Applications 14 (2010) 307--336.
  Preliminary version with the title Detecting Hotspots in Geographic Networks was presented at AGILE 2009; best paper award.
• Finding shortest contractible and shortest separating cycles in embedded graphs.
  ACM Transactions on Algorithms 6 (2010) Article No. 24 (special issue of selected papers from SODA 09). 
  Preliminary version in SODA 2009.
• Crossing and weighted crossing number of near-planar graphs. [draft]
  With B. Mohar.
  Algorithmica 60 (2011) 484--504.
  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.
  Discrete Mathematics & Theoretical Computer Science 12 (2010) 75--86.
  Preliminary version presented at EuroCG 2008.
• Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension.
  With P. Giannopoulos, C. Knauer, D. Marx, and G. Rote.
  ACM Transactions on Algorithms 7 (2011), Article No. 43.
  Preliminary version (without D. Marx and less 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.
  With M. DeVos, J. Erickson, and B. Mohar.
  ACM Transactions on Algorithms 6 (2010) Article No. 61 (special issue of selected papers from SODA 08).
  Preliminary version in SODA 2008, pp 527--531.
• Obnoxious centers in graphs. [draft]
  With G. Rote.
  SIAM Journal on Discrete Mathematics 24 (2010) 1713--1730.
  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 45 (2009) 446-469 (special issue of selected papers from 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 EuroCG 2004.
• 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.
  Algorithmica 58  (2010) 543--565.
  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, LNCS 4169, pp. 175--183, 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]
  Algorithmica 62 (2012) 361--381.
  Preliminary version in SODA 2006.
  [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 2005 and EuroCG 2005.
• 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.
  European Journal of Operational Research 202 (2010) 99--106.
  A preliminary version appeared at CCCG 2005.
• Planar embeddings of graphs with specified edge lengths.
  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 2004. [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.
  Visuals: [SoCG'01 , 1.74MB]  [Dagstuhl , 100KB].
• Schematic Networks: an Algorithm and its Implementation.
  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 SoCG 2002.
  Visuals: [Seminar , 580KB]
• Maximizing the area of overlap of two unions of disks under rigid motion. [draft]
  With M. de Berg, P. Giannopoulos, C. Knauer,  R. van Oostrum, and R. C. Veltkamp.
  International J. of Computational Geometry and Applications 19 (2009) 533--556.
  A preliminary version appeared at SWAT 2004 and EuroCG 2004.
• Approximation algorithms for aligning points. [ draft ]
  With M. van Kreveld.
  Algorithmica 37 (2003) 211--232.
  A preliminary version appeared at SoCG 2002 and 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 FCT  1999.