Sergio's Homepage

List of Publications and Coauthors

Publications (journal and conference versions are listed together)

• Eliminating crossings in ordered graphs. [draft]
  With A. Agrawal, M. Kaufmann, S. Saurabh, R. Sharma, Y. Uno, A. Wolff.
  Accepted to SWAT 2024.
• Geometric matching and bottleneck problems. [draft]
  With S.-W. Cheng, O. Cheong, C. Knauer.
  Accepted to SoCG 2024.
• A note on the 2-colored rectilinear crossing number of random point sets in the unit square. [draft]
  With É. Czabarka, R. Fabila-Monroy, Y. Higashikawa, R. Seidel, L. Székely, J. Tkadlec, A. Wesolek.
  Acta Mathematica Hungarica, accepted.
• Packing d-dimensional balls into a d+1-dimensional container. [draft]
  With H. Alt, O. Cheong, J. Park, N. Seiferth.
  Submitted to journal.
  [Visuals]
• Connectivity with uncertainty regions given as line segments. [draft]
  With D. Gajser.
  Algorithmica, 2024.
• On k-means for segments and polylines. [draft]
  With P. Giannopoulos.
  Accepted to ESA 2023.
• Maximum matchings in geometric intersection graphs. [draft]
  With É. Bonnet and W. Mulzer.
  Discrete and Computational Geometry, 2023.
  Preliminary version presented at STACS 2020.
• Faster distance-based representative skyline and k-center along Pareto front in the plane. [draft]
  Journal of Global Optimization, 2023.
• Long plane trees. [draft]
  With M. Hoffmann, K. Klost, W. Mulzer and J. Tkadlec.
  Preliminary version presented at SoCG 2022.
• Computing the inverse geodesic length in planar graphs and graphs of bounded treewidth. [draft]
  ACM Transactions on Algorithms, 2022.
• Computing Shapley values in the plane. [draft]
  With T.M. Chan
  Discrete and Computational Geometry, 2022.
  Preliminary version presented at SoCG 2019.
• The inverse Kakeya problem. [draft]
  with O. Cheong and M.G. Dobbins.
  Periodica Mathematica Hungarica, 2022.
• Finding a largest-area triangle in a terrain in near-linear time. [draft]
  With A. K. Das, S. Das, J. Mukherjee.
  Preliminary version presented at WADS 2021.
• The complexity of mixed-connectivity. [draft]
  With É. Bonnet.
  Annals of Operations Research, 2021.
  Note: the problem considered here is also known as network flow interdiction by removing vertices. See for example Network flow interdiction on planar graphs (Zenklusen; DAM 2010).
• Maximizing dominance in the plane and its applications.
  With J. Choi and H.-K. Ahn.
  Algorithmica, 2021.
  Preliminary version presented at WADS 2019.
• On the minimum consistent subset problem. [draft]
  With A. Biniaz, P. Carmi, J.-L. De Carufel, A. Maheshwari, S. Mehrabi, and M. Smid.
  Algorithmica, 2021.
  Preliminary version presented at WADS 2019.
• The reverse Kakeya problem.
  With S.W. Bae, O. Cheong, Y. Choi, F. Stehn, and S.D. Yoon.
  Advances in Geometry, 2021.
  Preliminary version presented at SoCG 2018.
• Minimum cuts in geometric intersection graphs. [draft]
  With W. Mulzer.
  Computational Geometry: Theory and Applications, 2021.
  Note: see the following correction for the journal version.
• The inverse Voronoi problem in graphs II: Trees. [draft merging two papers]
  With É. Bonnet, B. Mohar, and H. Pérez-Rosés.
  Algorithmica, 2021.
• Hardness of minimum barrier shrinkage and minimum installation path. [draft]
  With É. Colin de Verdière.
  Theoretical Computer Science, 2020.
• The inverse Voronoi problem in graphs I: Hardness. [draft merging two papers]
  With É. Bonnet, B. Mohar, and H. Pérez-Rosés.
  Algorithmica, 2020.
• Minimum shared-power edge cut. [draft]
  With K. Jain, A. Lubiw, and D. Mondal.
  Networks, 2020.
• The parameterized complexity of finding a 2-sphere in a simplicial complex. [draft]
  With B. Burton, S. Kratsch, W. Pettersson.
  SIAM Journal on Discrete Mathematics, 2019.
  Preliminary version presented at STACS 2017.
• Covering many points with a small-area box. [local copy]
  With M. de Berg, O. Cheong, D. Eppstein and C. Knauer.
  Journal of Computational Geometry, 2019.
• Encoding 3SUM. [draft]
  With J. Cardinal, J. Iacono, S. Langerman, P. Morin, and A. Ooms.
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. [draft]
  ACM Transactions on Algorithms, 2018.
  Preliminary version at the ACM-SIAM Symp on Discrete Algorithms (SODA 2017).
  Best paper award!!
• Two optimization problems for unit disks. [draft]
  With L. Milinković.
  Computational Geometry: Theory and Applications, 2018.
• Parameterized complexity of 1-planarity. [local copy]
  With M. J.Bannister and D. Eppstein.
  Journal of Graph Algorithms and Applications 2018.
  WADS 2013.
• Peeling potatoes near-optimally in near-linear time. [draft]
  With J. Cibulka, J. Kynčl, M. Saumell and P. Valtr.
  SIAM Journal on Computing 2017.
  Preliminary version presented at SoCG 2014.
• Minimum cell connection in line segment arrangements. [draft containing also other things related to separation]
  With H. Alt, P. Giannopoulos, and C. Knauer.
  International J. of Computational Geometry and Applications 2017.
  About half was presented at EuroCG 2011 under the title "On some connection problems in straight-line segment arrangements".
• Interval selection in the streaming model. [draft]
  With P. Pérez-Lantero.
  Theoretical Computer Science 2017.
  WADS 2015.
• Refining the hierarchies of classes of geometric intersection graphs. [draft]
  With M. Jejčič.
  The Electronic Journal of Combinatorics 2017.
  Preliminary version presented at the Discrete Mathematics Days 2016
• Maximum volume subset selection for anchored boxes. [full version]
  With K. Bringmann and M.T.M. Emmerich.
  Preliminary version at SoCG 2017.
• Finding shortest non-trivial cycles in directed graphs on surfaces. [local copy]
  With É. Colin de Verdière and F. Lazarus.
  Journal of Computational Geometry 2016.
  Preliminary version in Proc. ACM Symp. on Computational Geometry (SOCG), 2010, 156--165.
• Finding largest rectangles in convex polygons. [draft]
  With O. Cheong, C. Knauer, and L. Schlipf.
  Computational Geometry: Theory and Applications 2016.
  Preliminary version presented at EuroCG 2014.
• Semi-dynamic connectivity in the plane. [draft]
  With M. Kerber.
  WADS 2015.
• Simple PTAS's for families of graphs excluding a minor. [draft]
  With D. Gajser.
  Discrete Applied Mathematics 2015.
• Finding all maximal subsequences with hereditary properties.
  With D. Bokal and D. Eppstein.
  Preliminary version in SoCG 2015.
• A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon. [draft]
  With M. Saumell.
  Discrete Mathematics & Theoretical Computer Science 2015.
• The complexity of separating points in the plane. [draft]
  With P. Giannopoulos.
  Algorithmica 2016.
  Preliminary version in SoCG 2013.
  Note: Our NP-hardness results, and even APX-hardness, follow from previous works like Calinescu et al.: Separating Points by Axis-parallel Lines. Int. J. Comput. Geometry Appl. 15(6): 575-590 (2005).
• Shortest paths in intersection graphs of unit disks. [draft]
  With M. Jejčič.
  Computational Geometry: Theory and Applications 2015.
  [Visuals]
• Computing the stretch of an embedded graph. [draft]
  With M. Chimani and P. Hliněný.
  SIAM Journal on Discrete Mathematics 2014.
  Preliminary version in the XV Spanish Meeting on Computational Geometry.
• Adding one edge to planar graphs makes crossing number and 1-planarity hard. [draft]
  With B. Mohar.
  SIAM Journal on Computing 2013.   
  Preliminary version under the title Adding one edge to planar graphs makes crossing number hard in SoCG 2010.
  [Visuals]
• Multiple-source shortest paths in embedded graphs. [draft]
  With E. W. Chambers and J. Erickson.
  SIAM Journal on Computing 2013
  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.
• Stackelberg shortest path tree game, revisited. [draft]
  Only arxiv.
• Hardness of approximation for crossing number. [draft]
  Discrete and Computational Geometry 2013.
• The clique problem in ray intersection graphs. [draft]
  With J. Cardinal and S. Langermann.
  Discrete and Computational Geometry 2013.
  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.
• 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 2013.
• 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 2012.
  Preliminary version presented at EuroCG 2010.
• A point calculus for interlevel set homology. [draft]
  With P. Bendich and H. Edelsbrunner.
  Pattern Recognition Letters 2012.
• Finding cycles with topological properties in embedded graphs. [draft]
  With É. Colin de Verdière and F. Lazarus.
  SIAM Journal on Discrete Mathematics 2011.
• On the b-chromatic number of regular graphs. [draft]
  With M. Jakovac.
  Discrete Applied Mathematics 2011.
• The complexity of obtaining a distance-balanced graph.
  With P. Lukšič.
  The Electronic Journal of Combinatorics 2011.
• Algorithms for the edge-width of an embedded graph. [draft]
  With É. Colin de Verdière and F. Lazarus.
  Computational Geometry: Theory and Applications 2012.
  Preliminary version in Proc. ACM Symp. on Computational Geometry (SOCG), 2010, 147--155.
• 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 2011.
  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 2011.
  [Visuals]
• Crossing and weighted crossing number of near-planar graphs. [draft]
  With B. Mohar.
  Algorithmica 2011.
  Preliminary version presented at Graph Drawing 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 2011.
  Preliminary version (without D. Marx and less results) in SODA 2008, 836--843.
  [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 2010.
  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 2010. 
  Preliminary version in SODA 2009.
  
• 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 2010.
  Preliminary version presented at EuroCG 2008.
• Algorithms for graphs of bounded treewidth via orthogonal range searching. [draft]
  With C. Knauer.
  Computational Geometry: Theory and Applications 2009. (See the following correction.)
  Preliminary version will be presented at EuroCG 2008.
• Finding one tight cycle.
  With M. DeVos, J. Erickson, and B. Mohar.
  ACM Transactions on Algorithms 2010.
  Preliminary version in SODA 2008.
• Obnoxious centers in graphs. [draft]
  With G. Rote.
  SIAM Journal on Discrete Mathematics 2010.
  Preliminary version in SODA 2007
• Computing a center-transversal line. [draft]
  With P. K. Agarwal, J. A. Sellarès, and M. Sharir.
  Full version stalled.
  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 2009.
• Covering many or few points with unit disks. [draft]
  With M. de Berg and S. Har-Peled.
  Theory of Computing Systems 2009.
  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 2006.
  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 2007.
  Preliminary version in ESA 2005.
  [visuals]
• Algorithmic aspects of proportional symbol maps. [draft]
  With M. van Kreveld, H. Haverkort, and B. Speckmann.
  Algorithmica 2010.
  Preliminary version in ESA 2006
  
• On the parameterized complexity of d-dimensional point set pattern matching. [draft]
  With P. Giannopoulos, and C. Knauer.
  Information Processing Letters 2008.
  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 2008.
  
• Many distances in planar graphs. [draft]
  Algorithmica 2012.
  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 2008.
  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 2010.
  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 2007.
  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, O. Cheong, J. Gudmundsson, M. van Kreveld, and B. Speckmann. 
  Journal of Discrete Algorithms 2006.
  A preliminary version was presented at the Japan Conference on Discrete and Computational Geometry, 2004.
• Approximation algorithms for spreading points.  [draft]
  Journal of Algorithms 2007.
  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.
  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 2005.
  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 2004.
  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 2009.
  A preliminary version appeared at SWAT 2004 and EuroCG 2004.
• Approximation algorithms for aligning points. [ draft ]
  With M. van Kreveld.
  Algorithmica 2003.
  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 2002.
  A preliminary version appeared at FCT  1999.

Coauthors