CHClemens Huemer

Clemens Huemer

*This is an algorithmically generated author record based on publicly available information.

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


Clemens Huemer has a total of 103 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    On the Number of Drawings of a Combinatorial Triangulation

    by Belén Cruces, Clemens Huemer, Dolores Lara

    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)$$ Ω ( 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.


  • On the Number of Crossings in a Random Labeled Tree

    by Octavio Arizmendi, Pilar Cano, Clemens Huemer

  • Open Access

    On the number of drawings of a combinatorial triangulation

    by Belén Cruces, Clemens Huemer, Dolores Lara

    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

    On polynomials associated to Voronoi diagrams of point sets and crossing numbers

    by Mercè Claverol, Andrea de Las Heras-Parrilla, David Flores-Peñaloza, Clemens Huemer, David Orden

    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.

  • The edge labeling of higher order Voronoi diagrams

    by Mercè Claverol, Andrea de Las Heras Parrilla, Clemens Huemer, Alejandra Martínez-Moraian


  • Matching random colored points with rectangles

    by Josué Corujo, David Flores-Peñaloza, Clemens Huemer, Pablo Pérez-Lantero, Carlos Seara

  • Open Access

    On maximum-sum matchings of points

    by Sergey Bereg, Oscar P. Chacón-Rivera, David Flores-Peñaloza, Clemens Huemer, Pablo Pérez-Lantero, Carlos Seara

    Huemer et al. (Discrete Mathematics, 2019) proved that for any two point sets R and B with $$|R|=|B|$$ | 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$$ p ∈ R and $$q\in B$$ q ∈ 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

    On Weighted Sums of Numbers of Convex Polygons in Point Sets

    by Clemens Huemer, Deborah Oliveros, Pablo Pérez-Lantero, Ferran Torra, Birgit Vogtenhuber

    Let S be a set of n points in general position in the plane, and let $$X_{k,\ell }(S)$$ X k , ℓ ( 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)$$ X k , ℓ ( 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

    by C. Dalfó, F. Duque, R. Fabila-Monroy, M. A. Fiol, C. Huemer, A. L. Trujillo-Negrete, F. J. Zaragoza Martínez

    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

    by Guillermo Esteban, Clemens Huemer, Rodrigo I. Silveira

    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.