Modem Illumination of Monotone Polygons (2009)
Oswin Aichholzer, Ruy Fabila-monroy, David Flores-peñaloza, Thomas Hackl, Clemens Huemer, Jorge Urrutia, ...
We study a generalization of the classical problem of illumination of polygons. Instead of modeling a light source we model a wireless device whose radio signal can penetrate a given number k of...
Fabila-Monroy, Ruy, Flores-Peñaloza, David, Huemer, Clemens, Hurtado, Ferran, Urrutia, Jorge, Wood, David R.
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...
4-labelings and grid embeddings of plane quadrangulations (2009)
Barrière, Lali, Huemer, Clemens
We show that each quadrangulation on $n$ vertices has a closed rectangle of influence drawing on the $(n-2) \times (n-2)$ grid. Further, we present a simple algorithm to obtain a straight-line...
4-labelings and grid embeddings of plane quadrangulations (2009)
Barrière, Lali, Huemer, Clemens
We show that each quadrangulation on $n$ vertices has a closed rectangle of influence drawing on the $(n-2) \times (n-2)$ grid. Further, we present a simple algorithm to obtain a straight-line...
Maximizing Maximal Angles for Plane Straight-Line Graphs ⋆ (2009)
Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Clemens Huemer, Attila Pór, Francisco Santos, ...
Abstract. Let G =(S, E) be a plane straight-line graph on a finite point set S ⊂ R 2 in general position. The incident angles of a point p ∈ S in G are the angles between any two edges of G that...
On the Chromatic Numbers of some Flip Graphs (2008)
Ruy Fabila-monroy, David Flores-peñaloza, Clemens Huemer, Ferran Hurtado, Jorge Urrutia, David R. Wood
This paper studies the chromatic number of the following four flip graphs (under suitable definitions of a flip): • the flip graph of perfect matchings of a complete graph of even order, • the...
The Rotation Graph of k-ary Trees is Hamiltonian ∗ (2008)
Clemens Huemer, Ferran Hurtado, Julian Pfeifle
In this paper we show that the graph of k-ary trees, connected by rotations, contains a Hamilton cycle. Our proof is constructive and thus provides a cyclic Gray code for k-ary trees. Furthermore, we...
Binary labelings for bipartite graphs ∗ (2008)
Stefan Felsner, Clemens Huemer, David Orden
Part of the authors introduced in [C. Huemer, S. Kappes, A binary labelling for plane Laman graphs and quadrangulations, in Proceedings of the 22nd European Workshop on Computational Geometry...
Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber, Clemens Huemer, Ferran Hurtado, Hannes Krasser
We investigate the number of plane geometric, i.e., straight-line, graphs, a set S of n points in the plane admits. We show that the number of plane graphs and connected plane graphs as well as the...
Maximizing Maximal Angles for Plane Straight Line Graphs (2008)
Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Clemens Huemer, Francisco Santos
Let G =(S, E) be a plane straight line graph on a finite point set S ⊂ R 2 in general position. For a point p ∈ S let the maximum incident angle of p in G be the maximum angle between any two...
ported by the Austrian FWF Joint Research Project ’Industrial Geometry ’ S9205-N12. (2008)
Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, ...
Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non-crossing. Our first...
Compatible Geometric Matchings (2007)
Aichholzer, Oswin, Bereg, Sergey, Dumitrescu, Adrian, García, Alfredo, Huemer, Clemens, Hurtado, Ferran, ...
This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are \emph{compatible} if they have the same vertex set and their union is also non-crossing. Our first result...
Maximizing Maximal Angles for Plane Straight-Line Graphs (2007)
Aichholzer, Oswin, Hackl, Thomas, Hoffmann, Michael, Huemer, Clemens, Por, Attila, Santos, Francisco, ...
Let $G=(S, E)$ be a plane straight-line graph on a finite point set $S\subset\R^2$ in general position. The \emph{incident angles} of a point $p \in S$ in $G$ are the angles between any two edges of...
Compatible Geometric Matchings (2007)
Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, ...
Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non-crossing. Our first...
Binary Labelings for Plane Quadrangulations and their Relatives (2006)
Felsner, Stefan, Huemer, Clemens, Kappes, Sarah, Orden, David
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...
On the number of plane graphs (2006)
Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser, Birgit Vogtenhuber
We investigate the number of plane geometric, i.e., straight-line, graphs, a set S of n points in the plane admits. We show that the number of plane graphs is minimized when S is in convex position,...
O. Aichholzer, T. Hackl, C. Huemer, F. Hurtado, H. Krasser, B. Vogtenhuber, ...
We investigate the number of plane geometric, i.e., straight-line, graphs, a set S of n points in the plane admits. We show that the number of plane geometric graphs and connected plane geometric...
O. Aichholzer, F. Aurenhammer, C. Huemer, H. Krasser, Oswin Aichholzer, Franz Aurenhammer, ...
Let TS be the set of all crossing-free straight line spanning trees of a planar n-point set S. Consider the graph TS where two members T and T ′ of TS are adjacent if T intersects T ′ only in...
Transforming spanning trees and pseudo-triangulations (2006)
Oswin Aichholzer, Franz Aurenhammer, Clemens Huemer, Hannes Krasser
Let TS be the set of all crossing-free straight line spanning trees of a planar n-point set S. Consider the graph TS where two members T and T ′ of TS are adjacent if T intersects T ′ only in...
O. Aichholzer, F. Aurenhammer, T. Hackl, C. Huemer, Oswin Aichholzer, Franz Aurenhammer, ...
We study the following Ramsey-type problem. Let S = B ∪ R be a two-colored set of n points in the plane. We show how to construct, in O(n log n) time, a crossing-free spanning tree T(B) for B, and...