IST - Publications

2019

Oswin Aichholzer, Ruy Fabila-Monroy, Ferran Hurtado, Pablo Perez-Lantero, Andres J. Ruiz-Vargas, Jorge Urrutia Galicia and Birgit Vogtenhuber Cross-sections of line configurations in $R^3$ and $(d-2)$-flat configurations in $R^d$ Computational Geometry: Theory and Applications 2019, 51-61, 2019 , DOI Show publication in PURE

Oswin Aichholzer, Irene Maria De Parada, Manfred Scheucher, Birgit Vogtenhuber and Alexandra Weinberger Shooting Stars in Simple Drawings of K<sub>m,n</sub> Show publication in PURE

Oswin Aichholzer, Matias Korman, Yoshio Okamoto, Irene Maria De Parada, Daniel Perz, André van Renssen and Birgit Vogtenhuber Graphs with large total angular resolutionGraphs with large total angular resolution193-199 Show publication in PURE

Alan Arroyo, Fabian Klute, Irene Parada, Raimund Seidel, Birgit Vogtenhuber and Tilo Wiedera Extending simple drawings with one edge is hard arXiv.org e-Print archive 2019, 2019 Show publication in PURE

Oswin Aichholzer, Martin Balko, Michael Hoffmann, Jan Kynčl, Wolfgang Mulzer, Irene Parada, Alexander Pilz, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber and Emo Welzl Minimal Representations of Order Types by Geometric GraphsMinimal Representations of Order Types by Geometric Graphs101-113 Show publication in PURE

Oswin Aichholzer, Ruy Fabila-Monroy, Adrian Fuchs, Carlos Hidalgo-Toscano, Irene Parada, Birgit Vogtenhuber and Francisco Zaragoza On the 2-Colored Crossing NumberOn the 2-Colored Crossing Number87-100 Show publication in PURE

Carolina Medina, Irene Parada, Gelasio Salazar and Birgit Vogtenhuber Bounding the number of crossings for a particular class of drawings of $K_{n,n}$ Show publication in PURE

Oswin Aichholzer, Carlos Alegría, Irene Parada, Alexander Pilz, Javier Tejel, Csaba D. Tóth, Jorge Urrutia Galicia and Birgit Vogtenhuber Hamiltonian meander paths and cycles on bichromatic point sets. Show publication in PURE

Oswin Aichholzer, Fabila-Monroy Ruy, Adrian Fuchs, Carlos Hidalgo-Toscano, Irene Parada, Birgit Vogtenhuber and Francisco Zaragoza On the 2-colored crossing number Show publication in PURE

2018

Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins and Birgit Vogtenhuber Intersection Graphs of Rays and Grounded Segments Journal of Graph Algorithms and Applications 2018, 273-295, 2018 , DOI Show publication in PURE

Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Dan McQuillan, Bojan Mohar, Petra Mutzel, Pedro Ramos, R. Bruce Richter and Birgit Vogtenhuber Bishellable drawings of $K_n$ SIAM Journal on Discrete Mathematics 2018, 2482-2492, 2018 , DOI Show publication in PURE

Oswin Aichholzer, Martin Balko, Thomas Hackl, Alexander Pilz, Pedro Ramos, Pavel Valtr and Birgit Vogtenhuber Holes in 2-convex point sets Computational Geometry: Theory and Applications 2018, 38-49, 2018 , DOI Show publication in PURE

Philipp Kindermann, Stephen Kobourov, Maarten Löffler, Martin Nöllenburg, André Schulz and Birgit Vogtenhuber Lombardi Drawings of Knots and LinksLombardi Drawings of Knots and Links113-126 Show publication in PURE

Oswin Aichholzer, Luis Barba, Thomas Hackl, Alexander Pilz and Birgit Vogtenhuber Linear transformation distance for bichromatic matchings Computational Geometry: Theory and Applications 2018, 77-88, 2018 , DOI Show publication in PURE

Matias Korman, Stefan Langerman, Wolfgang Mulzer, Alexander Pilz, Maria Saumell and Birgit Vogtenhuber The dual diameter of triangulations Computational Geometry: Theory and Applications 2018, 243-252, 2018 , DOI Show publication in PURE

Oswin Aichholzer, Martin Balko, Thomas Hackl, Alexander Pilz, Pedro Ramos, Pavel Valtr and Birgit Vogtenhuber Holes in 2-convex point setsHoles in 2-convex point sets169-181 Show publication in PURE

Oswin Aichholzer, Nieves Atienza, José M. Díaz-Báñez, Ruy Fabila-Monroy, David Flores-Peñaloza, Pablo Pérez-Lantero, Birgit Vogtenhuber and Jorge Urrutia Galicia Computing Balanced Islands in Two Colored Point Sets in the Plane Information Processing Letters 2018, 28 - 32, 2018 , DOI Show publication in PURE

Oswin Aichholzer, Ruy Fabila-Monroy, David Flores-Peñaloza, Thomas Hackl, Jorge Urrutia Galicia and Birgit Vogtenhuber Modem Illumination of Monotone Polygons Computational Geometry: Theory and Applications 2018, 101-118, 2018 , DOI Show publication in PURE

Oswin Aichholzer, Martin Balko, Michael Hoffmann, Jan Kyncl, Wolfgang Mulzer, Irene Parada, Alexander Pilz, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber and Emo Welzl Minimal Geometric Graph Representations of Order TypesMinimal Geometric Graph Representations of Order Types21:1-21:6 Show publication in PURE

Oswin Aichholzer, Michael Kerber, István Talata and Birgit Vogtenhuber A Note on Planar Monohedral TilingsA Note on Planar Monohedral Tilings31:1-31:6 Show publication in PURE

Oswin Aichholzer, Wolfgang Mulzer, Partick Schnider and Birgit Vogtenhuber NP-Completeness of Max-Cut for Segment Intersection GraphsNP-Completeness of Max-Cut for Segment Intersection Graphs32:1-32:6 Show publication in PURE

Oswin Aichholzer, Lukas Andritsch, Karin Baur and Birgit Vogtenhuber Perfect $k$-Colored Matchings and $(k+2)$-Gonal Tilings Graphs and combinatorics 2018, 1333-1346, 2018 , DOI Show publication in PURE

John Iacono and Birgit Vogtenhuber In pursuit of a dynamic tree decompositionIn pursuit of a dynamic tree decomposition23-25 Show publication in PURE

2017

Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins and Birgit Vogtenhuber Intersection Graphs of Rays and Grounded SegmentsIntersection Graphs of Rays and Grounded Segments153-166 Show publication in PURE

Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber and Max Willert Routing in Polygonal DomainsRouting in Polygonal Domains88-89 Show publication in PURE

Bahareh Banyassady, Man-Kwun Chiu, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber and Max Willert Routing in Polygonal DomainsRouting in Polygonal Domains10:1-10:13 Show publication in PURE

Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber and Max Willert Routing in Simple PolygonsRouting in Simple Polygons17-20 Show publication in PURE

O. Aichholzer, Martin Balko, T. Hackl, J. Kyncl, I. Parada, M. Scheucher, P. Valtr and B. Vogtenhuber A superlinear lower bound on the number of 5-holesA superlinear lower bound on the number of 5-holes8:1-8:16 Show publication in PURE

O. Aichholzer, Martin Balko, T. Hackl, J. Kyncl, I. Parada, M. Scheucher, P. Valtr and B. Vogtenhuber A superlinear lower bound on the number of 5-holesA superlinear lower bound on the number of 5-holes69-73 Show publication in PURE

O. Aichholzer, L. Andritsch, K. Baur and B. Vogtenhuber Perfect $k$-colored matchings and $k+2$-gonal tilingsPerfect $k$-colored matchings and $k+2$-gonal tilings81-84 Show publication in PURE

B.M. Ábrego, O. Aichholzer, S. Fernández-Merchant, D. McQuillan, B. Mohar, P. Mutzel, P. Ramos, R.B. Richter and B. Vogtenhuber Bishellable drawings of $K_n$Bishellable drawings of $K_n$17-20 Show publication in PURE

Oswin Aichholzer, Florian Ebenführer, Irene Parada, Alexander Pilz and Birgit Vogtenhuber On semi-simple drawings of the complete graphOn semi-simple drawings of the complete graph25-28 Show publication in PURE

Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kyncl, Irene Parada, Manfred Scheucher, Pavel Valtr and Birgit Vogtenhuber A Superlinear Lower Bound on the Number of 5-HolesA Superlinear Lower Bound on the Number of 5-Holes8:1-8:16 Show publication in PURE

2016

Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann and Birgit Vogtenhuber An improved lower bound on the minimum number of triangulationsAn improved lower bound on the minimum number of triangulations7.1-7.16 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Birgit Vogtenhuber, P. Ramos, M. Balko and Pavel Valtr Holes in two convex point setHoles in two convex point set263-266 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Birgit Vogtenhuber, V. Alvarez and B. Speckmann An improved lower bound on the number of triangulationsAn improved lower bound on the number of triangulations7:1-7:16 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Matias Korman, Günter Rote, A. van Renssen, Birgit Vogtenhuber and Marcel Roeloffzen Packing Short Plane Spanning Trees in Complete Geometric GraphsPacking Short Plane Spanning Trees in Complete Geometric Graphs9:1--9:12 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Pavel Valtr and Birgit Vogtenhuber A Note on the Number of General 4-holes in (Perturbed) GridsA Note on the Number of General 4-holes in (Perturbed) Grids1-12 Show publication in PURE

2015

Oswin Aichholzer, Thomas Hackl, Sarah Lutteropp, Tamara Mchedlidze, Alexander Pilz and Birgit Vogtenhuber Monotone Simultaneous Embedding of Upward Planar Digraphs Journal of Graph Algorithms and Applications 2015, 87-110, 2015 , DOI Show publication in PURE

I. Bárány, Ruy Fabila-Monroy and Birgit Vogtenhuber $(n,m)$-Fold Covers of Spheres Proceedings of the Steklov Institute of Mathematics 2015, 203-208, 2015 , DOI Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Birgit Vogtenhuber and G. Salazar Deciding monotonicity of good drawings of the complete graphDeciding monotonicity of good drawings of the complete graph33-36 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Pedro Ramos, Vera Sacristán and Birgit Vogtenhuber Empty triangles in good drawings of the complete graph Graphs and combinatorics 2015, 335-345, 2015 , DOI Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber, R. Fabila-Monroy, Hernan Gonzales-Aguilar, Marco A. Heredia, Clemens Huemer, Jorge Urrutia and Pavel Valtr On k-Gons and k-Holes in Point Sets Computational geometry 2015, 528-537, 2015 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Sarah Lutteropp, Tamara Mchedlidze and Birgit Vogtenhuber Embedding Four-directional Paths on Convex Point Sets Journal of Graph Algorithms and Applications 2015, 743-759, 2015 , DOI Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber and Pavel Valtr A note on the number of general 4-holes in perturbed gridsA note on the number of general 4-holes in perturbed grids68-69 Show publication in PURE

Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Thomas Hackl, Jürgen Pammer, Alexander Pilz, Pedro Ramos, Gelasio Salazar and Birgit Vogtenhuber All Good Drawings of Small Complete GraphsAll Good Drawings of Small Complete Graphs57-60 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber, T. Biedl, M. Held, S. Huber and P. Palfrader Representing Directed Trees as Straight SkeletonsRepresenting Directed Trees as Straight Skeletons335-347 Show publication in PURE

Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, Alexander Pilz, Birgit Vogtenhuber and Clemens Huemer 3-Colorability of Pseudo-Triangulations International Journal of Computational Geometry and Applications 2015, 283-298, 2015 Show publication in PURE

2014

Oswin Aichholzer, Ruy Fabila-Monroy, Ferran Hurtado, Pablo Perez-Lantero, Andres Ruiz-Vargas, Jorge Urrutia and Birgit Vogtenhuber Order types and cross-sections of line arrangements in R3Order types and cross-sections of line arrangements in R3online-only Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Sarah Lutteropp, Tamara Mchedlidze and Birgit Vogtenhuber Monotone Simultaneous Embedding of Directed PathsMonotone Simultaneous Embedding of Directed Paths0-0 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Stefan Huber and Birgit Vogtenhuber Straight Skeletons by Means of Voronoi Diagrams Under Polyhedral Distance FunctionsStraight Skeletons by Means of Voronoi Diagrams Under Polyhedral Distance Functionsonline-only Show publication in PURE

Oswin Aichholzer, Ruy Fabila-Monroy, Hernán González-Aguilar, Thomas Hackl, Marco A. Heredia, Clemens Huemer, Jorge Urrutia and Birgit Vogtenhuber 4-Holes in Point Sets Computational geometry 2014, 644-650, 2014 , DOI Show publication in PURE

Oswin Aichholzer, Jean Cardinal, Thomas Hackl, Ferran Hurtado, Matias Korman, Alexander Pilz, Rodrigo Silveira, Ryuhei Uehara, Pavel Valtr, Birgit Vogtenhuber and Emo Welzl Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane Discrete Mathematics & Theoretical Computer Science 2014, 317-332, 2014 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, David Orden, Alexander Pilz, Maria Saumell and Birgit Vogtenhuber Flips in combinatorial pointed pseudo-triangulations with face degree at most four International Journal of Computational Geometry and Applications 2014, 197-224, 2014 , DOI Show publication in PURE

Oswin Aichholzer, Luis Barba, Thomas Hackl, Alexander Pilz and Birgit Vogtenhuber Linear Transformation Distance for Bichromatic MatchingsLinear Transformation Distance for Bichromatic Matchings154-162 Show publication in PURE

Matias Korman, Langerman Stefan, Wolfgang Mulzer, Alexander Pilz and Birgit Vogtenhuber Minimum Dual Diameter TriangulationsMinimum Dual Diameter Triangulations0-0 Show publication in PURE

Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, Ferran Hurtado, Alexander Pilz, Pedro Ramos, Jorge Urrutia, Pavel Valtr and Birgit Vogtenhuber On k-Convex Point Sets Computational geometry 2014, 809-832, 2014 , DOI Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz and Birgit Vogtenhuber Geodesic-preserving polygon simplification International Journal of Computational Geometry and Applications 2014, 307-323, 2014 , DOI Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Sarah Lutteropp, Tamara Mchedlidze and Birgit Vogtenhuber Embedding Four-directional Paths on Convex Point SetsEmbedding Four-directional Paths on Convex Point Sets355-366 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Alexander Pilz, Günter Rote, Bettina Speckmann and Birgit Vogtenhuber Plane graphs with parity constraints Graphs and combinatorics 2014, 47-69, 2014 , DOI Show publication in PURE

Oswin Aichholzer, Ruy Fabila-Monroy, Thomas Hackl, Clemens Huemer, Alexander Pilz and Birgit Vogtenhuber Lower bounds for the number of small convex k-holes Computational geometry 2014, 605-613, 2014 , DOI Show publication in PURE

Oswin Aichholzer, Matias Korman, Alexander Pilz and Birgit Vogtenhuber Geodesic Order Types Algorithmica 2014, 112-128, 2014 , DOI Show publication in PURE

Bernardo Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Pedro Ramos and Birgit Vogtenhuber Non-Shellable Drawings of Kn with Few CrossingsNon-Shellable Drawings of Kn with Few Crossingsonline-only Show publication in PURE

2013

Oswin Aichholzer, J. Urrutia and Birgit Vogtenhuber Balanced 6-holes in bichromatic point sets.Balanced 6-holes in bichromatic point sets.5-6 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Clemens Huemer, Francisco Santos, Bettina Speckmann and Birgit Vogtenhuber Maximizing maximal angles for plane straight line graphs Computational geometry 2013, 17-28, 2013 , DOI Show publication in PURE

Oswin Aichholzer, J. Urrutia and Birgit Vogtenhuber Balanced 6-holes in linearly separable bichromatic point sets. Electronic Notes in Discrete Mathematics 2013, 181-186, 2013 , DOI Show publication in PURE

Oswin Aichholzer, Thomas Hackl, David Orden, Alexander Pilz, Maria Saumell and Birgit Vogtenhuber Flips in combinatorial pointed pseudo-triangulations with face degree at most four (extended abstract)Flips in combinatorial pointed pseudo-triangulations with face degree at most four (extended abstract)131-134 Show publication in PURE

Oswin Aichholzer, Jean Cardinal, Thomas Hackl, Ferran Hurtado, Matias Korman, Alexander Pilz, Rodrigo Silveira, Ryuhei Uehara, Birgit Vogtenhuber and Emo Welzl Cell-paths in mono- and bichromatic line arrangements in the planeCell-paths in mono- and bichromatic line arrangements in the plane169-174 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Pedro Ramos, Vera Sacristán and Birgit Vogtenhuber Empty triangles in good drawings of the complete graphEmpty triangles in good drawings of the complete graph21-29 Show publication in PURE

Oswin Aichholzer, Ruy Fabila-Monroy, Thomas Hackl, Marc van Kreveld, Alexander Pilz, Pedro Ramos and Birgit Vogtenhuber Blocking delaunay triangulations Computational geometry 2013, 154-159, 2013 , DOI Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz and Birgit Vogtenhuber Geodesic-preserving polygon simplificationGeodesic-preserving polygon simplification11-21 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Vera Sacristán, Birgit Vogtenhuber and Reinhard Wallner Simulating distributed algorithms for lattice agentsSimulating distributed algorithms for lattice agents81-84 Show publication in PURE

2012

Oswin Aichholzer, Ferran Hurtado and Birgit Vogtenhuber Compatible matchings for bichromatic plane straight-line graphsCompatible matchings for bichromatic plane straight-line graphs257-260 Show publication in PURE

Oswin Aichholzer, Günter Rote, André Schulz and Birgit Vogtenhuber Pointed drawings of planar graphs Computational geometry 2012, 482-494, 2012 , DOI Show publication in PURE

Oswin Aichholzer, Ruy Fabila-Monroy, Thomas Hackl, Clemens Huemer, Alexander Pilz and Birgit Vogtenhuber Lower bounds for the number of small convex k-holesLower bounds for the number of small convex k-holes261-266 Show publication in PURE

Oswin Aichholzer, Matias Korman, Alexander Pilz and Birgit Vogtenhuber Geodesic order typesGeodesic order types216-227 Show publication in PURE

Oswin Aichholzer, Thomas Hackl and Birgit Vogtenhuber On 5-gons and 5-holes Lecture notes in computer science 2012, 1-13, 2012 Show publication in PURE

2011

Birgit Vogtenhuber Combinatorial Aspects of [Colored] Point Sets in the Plane Show publication in PURE

Oswin Aichholzer, Ruy Fabila-Monroy, Hernán González-Aguilar, Thomas Hackl, Marco A. Heredia, Clemens Huemer, Jorge Urrutia, Pavel Valtr and Birgit Vogtenhuber On k-Gons and k-Holes in Point SetsOn k-Gons and k-Holes in Point Sets21-26 Show publication in PURE

Oswin Aichholzer, Ruy Fabila-Monroy, Hernán González-Aguilar, Thomas Hackl, Marco A. Heredia, Clemens Huemer, Jorge Urrutia and Birgit Vogtenhuber 4-Holes in Point Sets4-Holes in Point Sets115-118 Show publication in PURE

Oswin Aichholzer, Thomas Hackl and Birgit Vogtenhuber On 5-gons and 5-holesOn 5-gons and 5-holes7-10 Show publication in PURE

2010

Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, Clemens Huemer, Alexander Pilz and Birgit Vogtenhuber 3-Colorability of pseudo-triangulations3-Colorability of pseudo-triangulations21-24 Show publication in PURE

Oswin Aichholzer, Ruy Fabila-Monroy, Thomas Hackl, Marc van Kreveld, Alexander Pilz, Pedro Ramos and Birgit Vogtenhuber Blocking delaunay triangulationsBlocking delaunay triangulations21-24 Show publication in PURE

Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado and Birgit Vogtenhuber Large bichromatic point sets admit empty monochromatic 4-gons SIAM Journal on Discrete Mathematics 2010, 2147-2155, 2010 , DOI Show publication in PURE

Oswin Aichholzer, Thomas Hackl and Birgit Vogtenhuber Compatible pointed pseudo-triangulationsCompatible pointed pseudo-triangulations91-94 Show publication in PURE