Clemens Huemer
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
Research Interests
Clemens Huemer has a total of 103 co-authors. Here are the top co-authors by number of shared publications:
Oswin Aichholzer
Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b/II, Graz, Austria
11 shared publicationsThomas Hackl
Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b/II, Graz, Austria
10 shared publicationsBirgit Vogtenhuber
Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b/II, Graz, Austria
9 shared publications- Pablo Pérez-Lantero
Facultad de Ciencia, Departamento de Matemática y Ciencia de la Computación, Universidad de Santiago de Chile (USACH), Santiago, Chile
9 shared publications - Ruy Fabila-Monroy
Departamento de Matemáticas, CINVESTAV, Ciudad de México, Mexico
9 shared publications - Carlos Seara
Departament de Matemàtiques, Universitat Politècnica de Catalunya, Barcelona, Spain
8 shared publications
Latest Publications
- Open Access
- 21 January 2026
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 42 (1) , 16
On the Number of Drawings of a Combinatorial Triangulation
In 1962, Tutte provided a formula for the number of combinatorial triangulations, that is, maximal planar graphs with a fixed triangular face and n additional vertices. In this note, we study in how many ways a combinatorial triangulation can be drawn as geometric triangulation, that is, with straight-line segments, on a given point set in the plane. Our central contribution is that there exist a combinatorial triangulation T and a point set S such that T can be drawn on S in at least $$\varOmega (1,31^n)$$ ways as different geometric triangulations. We also show an upper bound on the number of drawings of a combinatorial triangulation on the so-called double chain point set.- 21 January 2026
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 42 (1) , 16
Open AccessOn the Number of Drawings of a Combinatorial Triangulation
In 1962, Tutte provided a formula for the number of combinatorial triangulations, that is, maximal planar graphs with a fixed triangular face and n additional vertices. In this note, we study in how many ways a combinatorial triangulation can be drawn as geometric triangulation, that is, with straight-line segments, on a given point set in the plane. Our central contribution is that there exist a combinatorial triangulation T and a point set S such that T can be drawn on S in at least $$\varOmega (1,31^n)$$ ways as different geometric triangulations. We also show an upper bound on the number of drawings of a combinatorial triangulation on the so-called double chain point set. - 29 October 2025
- Published by Springer Nature
- p. 85-101
On the Number of Crossings in a Random Labeled Tree
- 29 October 2025
- Published by Springer Nature
- p. 85-101
On the Number of Crossings in a Random Labeled Tree
- Open Access
On the number of drawings of a combinatorial triangulation
In 1962, Tutte provided a formula for the number of combinatorial triangulations, that is, maximal planar graphs with a fixed triangular face and $n$ additional vertices. In this note, we study how many ways a combinatorial triangulation can be drawn as geometric triangulation, that is, with straight-line segments, on a given point set in the plane. Our central contribution is that there exists a combinatorial triangulation with n vertices that can be drawn in at least $Ω(1,31^n)$ ways on a set of n points as different geometric triangulations. We also show an upper bound on the number of drawings of a combinatorial triangulation on the so-called double chain point set.Open AccessOn the number of drawings of a combinatorial triangulation
In 1962, Tutte provided a formula for the number of combinatorial triangulations, that is, maximal planar graphs with a fixed triangular face and $n$ additional vertices. In this note, we study how many ways a combinatorial triangulation can be drawn as geometric triangulation, that is, with straight-line segments, on a given point set in the plane. Our central contribution is that there exists a combinatorial triangulation with n vertices that can be drawn in at least $Ω(1,31^n)$ ways on a set of n points as different geometric triangulations. We also show an upper bound on the number of drawings of a combinatorial triangulation on the so-called double chain point set. - Open Access
- 4 November 2024
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Discrete Mathematics & Theoretical Computer Science
- Vol. 26:2 (Combinator)
On polynomials associated to Voronoi diagrams of point sets and crossing numbers
Three polynomials are defined for given sets $S$ of $n$ points in general position in the plane: The Voronoi polynomial with coefficients the numbers of vertices of the order-$k$ Voronoi diagrams of $S$, the circle polynomial with coefficients the numbers of circles through three points of $S$ enclosing $k$ points of $S$, and the $E_{\leq k}$ polynomial with coefficients the numbers of (at most $k$)-edges of $S$. We present several formulas for the rectilinear crossing number of $S$ in terms of these polynomials and their roots. We also prove that the roots of the Voronoi polynomial lie on the unit circle if, and only if, $S$ is in convex position. Further, we present bounds on the location of the roots of these polynomials.- 4 November 2024
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Discrete Mathematics & Theoretical Computer Science
- Vol. 26:2 (Combinator)
Open AccessOn polynomials associated to Voronoi diagrams of point sets and crossing numbers
Three polynomials are defined for given sets $S$ of $n$ points in general position in the plane: The Voronoi polynomial with coefficients the numbers of vertices of the order-$k$ Voronoi diagrams of $S$, the circle polynomial with coefficients the numbers of circles through three points of $S$ enclosing $k$ points of $S$, and the $E_{\leq k}$ polynomial with coefficients the numbers of (at most $k$)-edges of $S$. We present several formulas for the rectilinear crossing number of $S$ in terms of these polynomials and their roots. We also prove that the roots of the Voronoi polynomial lie on the unit circle if, and only if, $S$ is in convex position. Further, we present bounds on the location of the roots of these polynomials. - 21 May 2024
- Published by Springer Nature in Journal of Global Optimization
- Vol. 90 (2) , 515-549
The edge labeling of higher order Voronoi diagrams
- 21 May 2024
- Published by Springer Nature in Journal of Global Optimization
- Vol. 90 (2) , 515-549
The edge labeling of higher order Voronoi diagrams
- 14 March 2023
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 45 (2) , 1-18
Matching random colored points with rectangles
- 14 March 2023
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 45 (2) , 1-18
Matching random colored points with rectangles
- Open Access
- 21 June 2022
- Published by Springer Nature in Journal of Global Optimization
- Vol. 85 (1) , 111-128
On maximum-sum matchings of points
Huemer et al. (Discrete Mathematics, 2019) proved that for any two point sets R and B with $$|R|=|B|$$ , the perfect matching that matches points of R with points of B, and maximizes the total squared Euclidean distance of the matched pairs, has the property that all the disks induced by the matching have a common point. Each pair of matched points $$p\in R$$ and $$q\in B$$ induces the disk of smallest diameter that covers p and q. Following this research line, in this paper we consider the perfect matching that maximizes the total Euclidean distance. First, we prove that this new matching for R and B does not always ensure the common intersection property of the disks. Second, we extend the study of this new matching for sets of 2n uncolored points in the plane, where a matching is just a partition of the points into n pairs. As the main result, we prove that in this case all disks of the matching do have a common point.- 21 June 2022
- Published by Springer Nature in Journal of Global Optimization
- Vol. 85 (1) , 111-128
Open AccessOn maximum-sum matchings of points
Huemer et al. (Discrete Mathematics, 2019) proved that for any two point sets R and B with $$|R|=|B|$$ , the perfect matching that matches points of R with points of B, and maximizes the total squared Euclidean distance of the matched pairs, has the property that all the disks induced by the matching have a common point. Each pair of matched points $$p\in R$$ and $$q\in B$$ induces the disk of smallest diameter that covers p and q. Following this research line, in this paper we consider the perfect matching that maximizes the total Euclidean distance. First, we prove that this new matching for R and B does not always ensure the common intersection property of the disks. Second, we extend the study of this new matching for sets of 2n uncolored points in the plane, where a matching is just a partition of the points into n pairs. As the main result, we prove that in this case all disks of the matching do have a common point. - Open Access
- 7 June 2022
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 68 (2) , 448-476
On Weighted Sums of Numbers of Convex Polygons in Point Sets
Let S be a set of n points in general position in the plane, and let $$X_{k,\ell }(S)$$ be the number of convex k-gons with vertices in S that have exactly $$\ell $$ points of S in their interior. We prove several equalities for the numbers $$X_{k,\ell }(S)$$ . This problem is related to the Erdős–Szekeres theorem. Some of the obtained equations also extend known equations for the numbers of empty convex polygons to polygons with interior points. Analogous results for higher dimension are shown as well.- 7 June 2022
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 68 (2) , 448-476
Open AccessOn Weighted Sums of Numbers of Convex Polygons in Point Sets
Let S be a set of n points in general position in the plane, and let $$X_{k,\ell }(S)$$ be the number of convex k-gons with vertices in S that have exactly $$\ell $$ points of S in their interior. We prove several equalities for the numbers $$X_{k,\ell }(S)$$ . This problem is related to the Erdős–Szekeres theorem. Some of the obtained equations also extend known equations for the numbers of empty convex polygons to polygons with interior points. Analogous results for higher dimension are shown as well. - Open Access
On the Laplacian spectra of token graphs
We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers $h$ and $k$ such that $1\le h\le k\le \frac{n}{2}$, the Laplacian spectrum of $F_h(G)$ is contained in the Laplacian spectrum of $F_k(G)$. We also show that the double odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph $K_n$ and the star $S_{n}=K_{1,n-1}$, respectively. Besides, we obtain a relationship between the spectra of the $k$-token graph of $G$ and the $k$-token graph of its complement $\overline{G}$. This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs. Finally, the double odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph $G$ and its token graph.Open AccessOn the Laplacian spectra of token graphs
We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers $h$ and $k$ such that $1\le h\le k\le \frac{n}{2}$, the Laplacian spectrum of $F_h(G)$ is contained in the Laplacian spectrum of $F_k(G)$. We also show that the double odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph $K_n$ and the star $S_{n}=K_{1,n-1}$, respectively. Besides, we obtain a relationship between the spectra of the $k$-token graph of $G$ and the $k$-token graph of its complement $\overline{G}$. This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs. Finally, the double odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph $G$ and its token graph. - Open Access
New production matrices for geometric graphs
We use production matrices to count several classes of geometric graphs. We present novel production matrices for non-crossing partitions, connected geometric graphs, and k-angulations, which provide another way of counting the number of such objects. Counting geometric graphs is then equivalent to calculating the powers of a production matrix. Applying the technique of Riordan Arrays to these production matrices, we establish new formulas for the numbers of geometric graphs as well as combinatorial identities derived from the production matrices. Further, we obtain the characteristic polynomial and the eigenvectors of such production matrices.
Open AccessNew production matrices for geometric graphs
We use production matrices to count several classes of geometric graphs. We present novel production matrices for non-crossing partitions, connected geometric graphs, and k-angulations, which provide another way of counting the number of such objects. Counting geometric graphs is then equivalent to calculating the powers of a production matrix. Applying the technique of Riordan Arrays to these production matrices, we establish new formulas for the numbers of geometric graphs as well as combinatorial identities derived from the production matrices. Further, we obtain the characteristic polynomial and the eigenvectors of such production matrices.