 Research group
 DCCG  Research group on discrete, combinatorial and computational geometry
 Department
 Department of Applied Mathematics IV
 School
 Castelldefels School of Telecommunications and Aerospace Engineering (EETAC)
 clemens.huemerupc.edu
 Contact details
 UPC directory
Scientific and technological production


Empty monochromatic simplices
Aichholzer, Oswin; Fabila Monroy, Ruy; Hackl, Thomas; Huemer, Clemens; Urrutia Galicia, Jorge
Discrete and computational geometry
Date of publication: 20140301
Journal article
Read the abstract View Share Reference managersLet S be a kcolored (finite) set of n points in , da parts per thousand yen3, in general position, that is, no (d+1) points of S lie in a common (d1)dimensional hyperplane. We count the number of empty monochromatic dsimplices 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 3a parts per thousand currency signka parts per thousand currency signd we provide a lower bound of and strengthen this to Omega(n (d2/3)) for k=2.; On the way we provide various results on triangulations of point sets in . In particular, for any constant dimension da parts per thousand yen3, we prove that every set of n points (n sufficiently large), in general position in , admits a triangulation with at least dn+Omega(logn) simplices. 
On 4connected geometric graphs
Garcia Olaverri, Alfredo Martin; Huemer, Clemens; Tejel Altarriba, Francisco Javier; Valtr, Pavel
Spanish Meeting on Computational Geometry
Presentation's date: 201306
Presentation of work at congresses
Read the abstract View Share Reference managersGiven a set S of n points in the plane, in this paper we give a necessary and sometimes sucient condition to build a 4connected noncrossing geometric graph on S 
On the number of edges in geometric graphs without empty triangles
Bautista Santiago, Crevel; Heredia, Marco A.; Huemer, Clemens; Ramírez Vigueras, Adriana; Seara Ojea, Carlos; Urrutia Galicia, Jorge
Graphs and combinatorics
Date of publication: 20131101
Journal article
Read the abstract View Share Reference managersIn this paper we study the extremal type problem arising from the question: What is the maximum number ET(S) of edges that a geometric graph G on a planar point set S can have such that it does not contain empty triangles? We prove:(Formula Presented). © 2012 Springer. 
The edge rotation graph
Cano, Javier; Díaz Báñez, JoséMiguel; Huemer, Clemens; Urrutia Galicia, Jorge
Graphs and combinatorics
Date of publication: 2013
Journal article
View Share Reference managers 
On the Fiedler value of large planar graphs
Barriere Figueroa, Eulalia; Huemer, Clemens; Mitsche, Dieter Wilhelm; Orden, David
Linear algebra and its applications
Date of publication: 2013
Journal article
View Share Reference managers 
Maximizing maximal angles for plane straightline graphs
Aichholzer, Oswin; Hackl, Thomas; Hoffmann, Michael; Huemer, Clemens; Pór, Attila; Santos, Francisco; Speckmann, Bettina; Vogtenhuber, Birgit
Computational geometry: theory and applications
Date of publication: 201301
Journal article
Read the abstract View Share Reference managersLet G=(S,E) be a plane straightline graph on a finite point set S⊂R2 in general position. The incident angles of a point p∈S in 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 straightline 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⊂R2 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 spanning paths on S and give tight bounds in most cases. 
Covering islands in plane point sets
FabilaMonroy, Ruy; Huemer, Clemens
Lecture notes in computer science
Date of publication: 2012
Journal article
Read the abstract View Share Reference managersLet S be a set of n points in general position in the plane. A kisland I of S is a subset of k points of S such that Conv(I)¿n¿S¿=¿I. We show that, for an arbitrary but fixed number k¿=¿2, the minimum number of kislands among all sets S of n points is T(n 2). The following related counting problem is also studied: For l¿<¿k, an lisland covers a kisland if it is contained in the kisland. Let C k,l (S) be the minimum number of lislands needed to cover all the kislands of S and let C k,l (n) be the minimum of C k,l (S) among all sets S of n points. We show asymptotic bounds for C k,l (n). 
Token Graphs
Fabila Monroy, Ruy; Flores Peñaloza, David; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Urrutia, Jorge; Wood, David R.
Graphs and combinatorics
Date of publication: 201205
Journal article
View Share Reference managers 
4labelings and grid embeddings of plane quadrangulations
Barriere Figueroa, Eulalia; Huemer, Clemens
Discrete mathematics
Date of publication: 20120528
Journal article
View Share Reference managers 
On the Fiedler value of large planar graphs
Barriere Figueroa, Eulalia; Huemer, Clemens; Mitsche, Dieter Wilhelm; Orden, David
Electronic notes in discrete mathematics
Date of publication: 20111201
Journal article
View Share Reference managers 
Puntos y grafos: puentes geométricos (IP04 en CRP Comb. of points sets, ComPoSe,EuroGIGA ESF)
Claverol Aguas, Merce; Dall, Aaron Matthew; Silveira, Rodrigo Ignacio; Huemer, Clemens; Mora Gine, Mercè; Sacristán Adinolfi, Vera; Hernando Martin, Maria Del Carmen; Seara Ojea, Carlos; Montes Lozano, Antonio; Hurtado Diaz, Fernando Alfredo
Participation in a competitive project
Share 
A combinatorial property on angular orders of plane point sets
FabilaMonroy, Ruy; Huemer, Clemens; Lara, Dolores
Information processing letters
Date of publication: 2011
Journal article
View Share Reference managers 
Edgeremoval and noncrossing configurations in geometric graphs
Aichholzer, Oswin; Cabello, Sergio; Fabila Monroy, Ruy; Flores Peñazola, David; Hackl, Thomas; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Wood, D. R.
Discrete mathematics and theoretical computer science
Date of publication: 2010
Journal article
Read the abstract Access to the full text Share Reference managersA geometric graph is a graph G = (V;E) drawn in the plane, such that V is a point set in general position and E is a set of straightline segments whose endpoints belong to V . We study the following extremal problem for geometric graphs: How many arbitrary edges can be removed from a complete geometric graph with n vertices such that the remaining graph still contains a certain noncrossing subgraph. The noncrossing subgraphs that we consider are perfect matchings, subtrees of a given size, and triangulations. In each case, we obtain tight bounds on the maximum number of removable edges. 
Binary labelings for plane quadrangulations and their relatives
Felsner, Stefan; Huemer, Clemens; Kappes, Sarah; Orden, David
Discrete mathematics and theoretical computer science
Date of publication: 2010
Journal article
Read the abstract Access to the full text Share Reference managersMotivated 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 2book. Furthermore, as Schnyder labelings have been extended to 3connected plane graphs, we are able to extend our labeling from quadrangulations to a larger class of 2connected bipartite graphs. 
Large bichromatic point sets admit empty monochromatic 4Gons
Aichholzer, Oswin; Hackl, Thomas; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Vogtenhuber, Birgit
SIAM journal on discrete mathematics
Date of publication: 2010
Journal article
View Share Reference managers 
PROBLEMAS DE COMBINATORIA Y DE COMPUTACION
Claverol Aguas, Merce; Hernando Martin, Maria Del Carmen; Montes Lozano, Antonio; Mora Gine, Mercè; Sacristán Adinolfi, Vera; Seara Ojea, Carlos; Trias Pairo, Juan; Huemer, Clemens; Pfeifle, Julian Thoralf; Saumell Mendiola, Maria; Garcia Olaverri, Alfredo Martin; Tejel Altarriba, Francisco Javier; Dall, Aaron Matthew; Hurtado Diaz, Fernando Alfredo
Participation in a competitive project
Share 
On the Chromatic Number of some Flip Graphs
Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; FabilaMonroy, R; FloresPenaloza, D; Urrutia, J; Wood, Dr
Discrete mathematics and theoretical computer science
Date of publication: 200901
Journal article
View Share Reference managers 
On triconnected and cubic plane graphs on given point sets
Garcia, A; Hurtado Diaz, Fernando Alfredo; Huemer, Clemens; Tejel, J; Valtr, P
Computational geometry: theory and applications
Date of publication: 200911
Journal article
View Share Reference managers 
Compatible geometric matchings
Aichholzer, O; Bereg, S; Dumitrescu, A; Garcia, A; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Kano, M; Marquez, A; Rappaport, D; Smorodinsky, S; Souvaine, D; Urrutia, J; Wood, Dr
Computational geometry: theory and applications
Date of publication: 200908
Journal article
Share Reference managers 
Gray codes for noncrossing partitions and dissections of a convex polygon
Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Noy Serrano, Marcos
Discrete applied mathematics
Date of publication: 200904
Journal article
View Share Reference managers 
Recoloring directed graphs
Felsner, Stefan; Huemer, Clemens; Saumell Mendiola, Maria
Encuentros de Geometría Computacional
Presentation's date: 20090629
Presentation of work at congresses
Read the abstract Access to the full text Share Reference managersLet G be a directed graph and k a positive integer. We define the kcolor graph of G (Dk(G) for short) as the directed graph having all kcolorings of G as node set, and where two kcolorings and ' are joined by a directed edge ! ' if ' is obtained from by choosing a vertex v and recoloring v so that its color is different from the colors of all its outneighbors. We investigate reachability questions in Dk(G). In particular we want to know whether a fixed legal k′coloring of G with k′ k is reachable in Dk(G) from every possible initial kcoloring . Interesting instances of this problem arise when G is planar and the orientation is an arbitrary orientation for fixed . Our main result is that reachability can be guaranteed if the orientation has maximal outdegree k − 1 and an accessible pseudosink. 
36 twocolored points with no empty monochromatic convex fourgons
Huemer, Clemens; Seara Ojea, Carlos
Geombinatorics
Date of publication: 200907
Journal article
View Share Reference managers 
On some partitioning problems for twocolored point sets
Grima, Clara; Hernando Martin, Maria Del Carmen; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo
Encuentros de Geometría Computacional
Presentation's date: 2009
Presentation of work at congresses
Read the abstract Access to the full text Share Reference managersLet S be a twocolored set of n points in general position in the plane. We show that S admits at least 2 n 17 pairwise disjoint monochromatic triangles with vertices in S and empty of points of S. We further show that S can be partitioned into 3 n 11 subsets with pairwise disjoint convex hull such that within each subset all but at most one point have the same color. A lower bound on the number of subsets needed in any such partition is also given. 
Empty monochromatic triangles
Aichholzer, O; FabilaMonroy, R; FloresPenaloza, D; Hackl, Thomas; Huemer, Clemens; Urrutia, J
Computational geometry: theory and applications
Date of publication: 200911
Journal article
View Share Reference managers 
Matching edges and faces in polygonal partitions
Aichholzer, O; Aurenhammer, F; GonzalezNava, P; Hackl, Thomas; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Krasser, H; Ray, S; Vogtenhuber, Birgit
Computational geometry: theory and applications
Date of publication: 200802
Journal article
View Share Reference managers 
Compatible Geometric Matchings
Aichholzer, Oswin; Sergey, Bereg; Dumitrescu, Adrian; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Mikio, Kano; Alberto, Márquez; Rappaport, David; Smorodinsky, Shakhar; Souvaine, Diane; URRUTIA GALICIA, JORGE
Electronic notes in discrete mathematics
Date of publication: 200808
Journal article
Share Reference managers 
Lower bounds for the colored mixed chromatic number of some classes of graphs
FabilaMonroy, Ruy; FloresPeñaloza, David; Huemer, Clemens; Montejano Cantoral, Amanda
Commentationes Mathematicae Universitatis Carolinae
Date of publication: 2008
Journal article
View Share Reference managers 
Compatible Geometric Matchings
Aichholzer, O; Bereg, S; Dumitrescu, A; GARCÍA, A; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Kano, M; Márquez, A; Souvaine, D
TGGT 2008 international conference : Topological and Geometric Graph Theory
Presentation of work at congresses
Share Reference managers 
The rotation graph of kary trees is Hamiltonian
Huemer, Clemens; Hurtado, Ferran; Pfeifle, Julian Thoralf
Information processing letters
Date of publication: 200812
Journal article
Share Reference managers 
Triangulations without pointed spanning trees
Aichholzer, Oswin; Huemer, Clemens; Krasser, Hannes
Computational geometry: theory and applications
Date of publication: 200805
Journal article
View Share Reference managers 
On the number of plane geometric graphs
Aichholzer, O; Hackl, Thomas; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Krasser, H; Vogtenhuber, Birgit
Graphs and combinatorics
Date of publication: 200702
Journal article
Share Reference managers 
On embedding triconnected cubic graphs on point sets
Hurtado Diaz, Fernando Alfredo; Huemer, Clemens; Javier, Tejel; Pavel, Valtr
ELECTRONIC Notes IN DISCRETE MATHEMATICS
Date of publication: 200708
Journal article
Share Reference managers 
Binary labelings for bipartite graphs
Felsner, S; Huemer, Clemens; Kappes, Sarah; Orden, D
Encuentros de Geometría Computacional
Presentation of work at congresses
Share Reference managers 
On the Chromatic Numbers of Some Flip Graphs
FabilaMonroy, R; FloresPeñaloza, D; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Urrutia, J; Wood, D
Encuentros de Geometría Computacional
Presentation of work at congresses
Share Reference managers 
Binary labelings for bipartite graphs
Huemer, Clemens
Encuentros de Geometría Computacional
Presentation's date: 20070626
Presentation of work at congresses
Share Reference managers 
On the Chromatic Numbers of Some Flip Graphs
FabilaMonroy, R; FloresPeñaloza, D; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Urrutia, J; Wood, D
European Conference on Computational Geometry
Presentation of work at congresses
Share Reference managers 
Structural and Enumerative Problems for Plane Geometric Graphs
Huemer, Clemens
Defense's date: 20071127
School of Mathematics and Statistics (FME), Universitat Politècnica de Catalunya
Theses
Share Reference managers 
Compatible geometric trees
Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Javier, Tejel
Encuentros de Geometría Computacional
Presentation of work at congresses
Share Reference managers 
Connecting colored point sets
Aichholzer, O; Aurenhammer, F; Hackl, Thomas; Huemer, Clemens
Discrete applied mathematics
Date of publication: 200702
Journal article
Share Reference managers 
Gray Code Enumeration of Plane Straight Line Graphs
Aichholzer, O; Aurenhammer, F; Huemer, Clemens; Vogtenhuber, Birgit
Graphs and combinatorics
Date of publication: 200710
Journal article
Share Reference managers 
Decompositions, partitions, and coverings with convex polygons and pseudotriangles
Aichholzer, O; Huemer, Clemens; Kappes, Sarah; Speckmann, B; Toth, C D
Graphs and combinatorics
Date of publication: 200710
Journal article
Share Reference managers 
The rotation graph of kary trees is Hamiltonian
Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Pfeifle, Julian Thoralf
European Workshop on Computational Geometry
Presentation's date: 20060327
Presentation of work at congresses
Read the abstract View Share Reference managersIn this paper we show that the graph of kary trees, connected by rotations, contains a Hamilton cycle. Our proof is constructive and thus provides a cyclic Gray code for kary trees. Furthermore, we identify a basic building block of this graph as the 1skeleton of the polytopal complex dual to the lower faces of a certain cyclic polytope. 
A binary labelling for plane Laman graphs and quadrangulations
Huemer, Clemens; Kappes, Sarah
22nd European Workshop on Computational Geometry
Presentation of work at congresses
Share Reference managers 
On the number of plane graphs
Aichholzer, O; Hackl, Thomas; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Krasser, H; Vogtenhuber, Birgit
17th Annual ACMSIAM Symposium on Discrete Algorithms (SODA)
Presentation of work at congresses
Share Reference managers 
Gray Code Enumeration of Plane StraightLine Graphs
Aichholzer, O; Aurenhammer, F; Huemer, Clemens; Vogtenhuber, Birgit; Hurtado Diaz, Fernando Alfredo; Pfeifle, Julian Thoralf
22nd European Workshop on Computational Geometry
Presentation of work at congresses
Share Reference managers 
The rotation graph of kary trees is Hamiltonian
Huemer, Clemens; HURTADO, F; Pfeifle, J
22nd European Workshop on Computational Geometry
Presentation of work at congresses
Share Reference managers 
Decompositions, partitions, and coverings with convex polygons and pseudotriangles
Aichholzer, O; Huemer, Clemens; Kappes, Sarah; Speckmann, B; Tóth, C D
International Symposium on Mathematical Foundations of Computer Science
Presentation of work at congresses
Share Reference managers 
Embedding quadrangulations on a 2book
Huemer, Clemens; Kappes, Sarah; Orden, D
Jornadas de Matemática Discreta y Algorítmica
Presentation of work at congresses
Share Reference managers 
Transforming spanning trees and pseudotriangulations
Aichholzer, O; Aurenhammer, F; Huemer, Clemens; Krasser, H
Information processing letters
Date of publication: 200601
Journal article
Share Reference managers 
Decompositions, partitions, and coverings with convex polygons and pseudotriangles
Aichholzer, O; Huemer, Clemens; Kappes, Sarah; Speckmann, B; Tóth, And C D
Lecture notes in computer science
Date of publication: 200608
Journal article
Share Reference managers
Filter results
Reference managers
Continue