Source author record

Clemens Huemer

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Geometry Discrete Mathematics math.MG

Catalog footprint

Research overview

11works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Voronoi Diagrams of Arbitrary Order on the Sphere

For a given set of points $U$ on a sphere $S$ , the order $k$ spherical Voronoi diagram $SV_k(U)$ decomposes the surface of $S$ into regions whose points have the same $k$ nearest points of $U$ . Hyeon-Suk Na, Chung-Nim Lee, and Otfried Cheong (Comput. Geom., 2002) applied inversions to construct $SV_1(U)$ . We generalize their construction for spherical Voronoi diagrams from order $1$ to any order $k$ . We use that construction to prove formulas for the numbers of vertices, edges, and faces in $SV_k(U)$ . These formulas were not known before. We obtain several more properties for $SV_k(U)$ , and we also show that $SV_k(U)$ has a small orientable cycle double cover.

preprint2020arXiv

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.

preprint2016arXiv

The intersection graph of the disks with diameters the sides of a convex $n$ -gon

Given a convex polygon of $n$ sides, one can draw $n$ disks (called side disks) where each disk has a different side of the polygon as diameter and the midpoint of the side as its center. The intersection graph of such disks is the undirected graph with vertices the $n$ disks and two disks are adjacent if and only if they have a point in common. We prove that for every convex polygon this graph is planar. Particularly, for $n=5$ , this shows that for any convex pentagon there are two disks among the five side disks that do not intersect, which means that $K_5$ is never the intersection graph of such five disks. For $n=6$ , we then have that for any convex hexagon the intersection graph of the side disks does not contain $K_{3,3}$ as subgraph.

preprint2015arXiv

On Cyclic Kautz Digraphs

A prominent problem in Graph Theory is to find extremal graphs or digraphs with restrictions in their diameter, degree and number of vertices. Here we obtain a new family of digraphs with minimal diameter, that is, given the number of vertices and out-degree there is no other digraph with a smaller diameter. This new family is called modified cyclic digraphs $MCK(d,\ell)$ and it is derived from the Kautz digraphs $K(d,\ell)$ . %It is not common to find non-regular digraphs with minimal diameter given their number of vertices and out-degree. It is well-known that the Kautz digraphs $K(d,\ell)$ have the smallest diameter among all digraphs with their number of vertices and degree. We define the cyclic Kautz digraphs $CK(d,\ell)$ , whose vertices are labeled by all possible sequences $a_1\ldots a_\ell$ of length $\ell$ , such that each character $a_i$ is chosen from an alphabet containing $d+1$ distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and now also requiring that $a_1\neq a_\ell$ . The cyclic Kautz digraphs $CK(d,\ell)$ have arcs between vertices $a_1 a_2\ldots a_\ell$ and $a_2 \ldots a_\ell a_{\ell+1}$ , with $a_1\neq a_\ell$ and $a_2\neq a_{\ell+1}$ . Unlike in Kautz digraphs $K(d,\ell)$ , any label of a vertex of $CK(d,\ell)$ can be cyclically shifted to form again a label of a vertex of $CK(d,\ell)$ . We give the main parameters of $CK(d,\ell)$ : number of vertices, number of arcs, and diameter. Moreover, we construct the modified cyclic Kautz digraphs $MCK(d,\ell)$ to obtain the same diameter as in the Kautz digraphs, and we show that $MCK(d,\ell)$ are $d$ -out-regular. Finally, we compute the number of vertices of the iterated line digraphs of $CK(d,\ell)$ .

preprint2014arXiv

On $k$ -Gons and $k$ -Holes in Point Sets

We consider a variation of the classical Erdős-Szekeres problems on the existence and number of convex $k$ -gons and $k$ -holes (empty $k$ -gons) in a set of $n$ points in the plane. Allowing the $k$ -gons to be non-convex, we show bounds and structural results on maximizing and minimizing their numbers. Most noteworthy, for any $k$ and sufficiently large $n$ , we give a quadratic lower bound for the number of $k$ -holes, and show that this number is maximized by sets in convex position.

preprint2013arXiv

Lower bounds on the maximum number of non-crossing acyclic graphs

This paper is a contribution to the problem of counting geometric graphs on point sets. More concretely, we look at the maximum numbers of non-crossing spanning trees and forests. We show that the so-called double chain point configuration of N points has Omega(12.52^N) non-crossing spanning trees and Omega(13.61^N) non-crossing forests. This improves the previous lower bounds on the maximum number of non-crossing spanning trees and of non-crossing forests among all sets of N points in general position given by Dumitrescu, Schulz, Sheffer and Tóth. Our analysis relies on the tools of analytic combinatorics, which enable us to count certain families of forests on points in convex position, and to estimate their average number of components. A new upper bound of O(22.12^N) for the number of non-crossing spanning trees of the double chain is also obtained.

preprint2013arXiv

On the Fiedler value of large planar graphs

The Fiedler value $λ_2$ , also known as algebraic connectivity, is the second smallest Laplacian eigenvalue of a graph. We study the maximum Fiedler value among all planar graphs $G$ with $n$ vertices, denoted by $λ_{2\max}$ , and we show the bounds $2+Θ(\frac{1}{n^2}) \leq λ_{2\max} \leq 2+O(\frac{1}{n})$ . We also provide bounds on the maximum Fiedler value for the following classes of planar graphs: Bipartite planar graphs, bipartite planar graphs with minimum vertex degree~3, and outerplanar graphs. Furthermore, we derive almost tight bounds on $λ_{2\max}$ for two more classes of graphs, those of bounded genus and $K_h$ -minor-free graphs.

preprint2012arXiv

Empty Monochromatic Simplices

Let $S$ be a $k$ -colored (finite) set of $n$ points in $\mathbb{R}^d$ , $d\geq 3$ , in general position, that is, no { $(d + 1)$ } points of $S$ lie in a common $(d - 1)$ }-dimensional hyperplane. We count the number of empty monochromatic $d$ -simplices determined by $S$ , that is, simplices which have only points from one color class of $S$ as vertices and no points of $S$ in their interior. For $3 \leq k \leq d$ we provide a lower bound of $Ω(n^{d-k+1+2^{-d}})$ and strengthen this to $Ω(n^{d-2/3})$ for $k=2$ . On the way we provide various results on triangulations of point sets in $\mathbb{R}^d$ . In particular, for any constant dimension $d\geq3$ , we prove that every set of $n$ points ( $n$ sufficiently large), in general position in $\mathbb{R}^d$ , admits a triangulation with at least $dn+Ω(\log n)$ simplices.

preprint2009arXiv

Maximizing Maximal Angles for Plane Straight-Line Graphs

Let $G=(S, E)$ be a plane straight-line graph on a finite point set $S\subset\R^2$ in general position. The incident angles of a vertex $p \in S$ of $G$ are the angles between any two edges of $G$ that appear consecutively in the circular order of the edges incident to $p$ . A plane straight-line graph is called $ϕ$ -open if each vertex has an incident angle of size at least $ϕ$ . In this paper we study the following type of question: What is the maximum angle $ϕ$ such that for any finite set $S\subset\R^2$ of points in general position we can find a graph from a certain class of graphs on $S$ that is $ϕ$ -open? In particular, we consider the classes of triangulations, spanning trees, and paths on $S$ and give tight bounds in most cases.

preprint2009arXiv

Token Graphs

For a graph $G$ and integer $k\geq1$ , we define the token graph $F_k(G)$ to be the graph with vertex set all $k$ -subsets of $V(G)$ , where two vertices are adjacent in $F_k(G)$ whenever their symmetric difference is a pair of adjacent vertices in $G$ . Thus vertices of $F_k(G)$ correspond to configurations of $k$ indistinguishable tokens placed at distinct vertices of $G$ , where two configurations are adjacent whenever one configuration can be reached from the other by moving one token along an edge from its current position to an unoccupied vertex. This paper introduces token graphs and studies some of their properties including: connectivity, diameter, cliques, chromatic number, Hamiltonian paths, and Cartesian products of token graphs.

preprint2008arXiv

Binary Labelings for Plane Quadrangulations and their Relatives

Motivated by the bijection between Schnyder labelings of a plane triangulation and partitions of its inner edges into three trees, we look for binary labelings for quadrangulations (whose edges can be partitioned into two trees). Our labeling resembles many of the properties of Schnyder's one for triangulations: Apart from being in bijection with tree decompositions, paths in these trees allow to define the regions of a vertex such that counting faces in them yields an algorithm for embedding the quadrangulation, in this case on a~2-book. Furthermore, as Schnyder labelings have been extended to 3-connected plane graphs, we are able to extend our labeling from quadrangulations to a larger class of 2-connected bipartite graphs. Finally, we propose a binary labeling for Laman graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Clemens Huemer

Research overview

Is this your work?

11 publications

Voronoi Diagrams of Arbitrary Order on the Sphere

New production matrices for geometric graphs

The intersection graph of the disks with diameters the sides of a convex $n$ -gon

On Cyclic Kautz Digraphs

On $k$ -Gons and $k$ -Holes in Point Sets

Lower bounds on the maximum number of non-crossing acyclic graphs

On the Fiedler value of large planar graphs

Empty Monochromatic Simplices

Maximizing Maximal Angles for Plane Straight-Line Graphs

Token Graphs

Binary Labelings for Plane Quadrangulations and their Relatives

See the researcher in context

Building this map preview

Clemens Huemer

Research overview

Is this your work?

11 publications

Voronoi Diagrams of Arbitrary Order on the Sphere

New production matrices for geometric graphs

The intersection graph of the disks with diameters the sides of a convex nnn-gon

On Cyclic Kautz Digraphs

On kkk-Gons and kkk-Holes in Point Sets

Lower bounds on the maximum number of non-crossing acyclic graphs

On the Fiedler value of large planar graphs

Empty Monochromatic Simplices

Maximizing Maximal Angles for Plane Straight-Line Graphs

Token Graphs

Binary Labelings for Plane Quadrangulations and their Relatives

See the researcher in context

Building this map preview

The intersection graph of the disks with diameters the sides of a convex $n$ -gon

On $k$ -Gons and $k$ -Holes in Point Sets