Ferran Hurtado, Marc Noy, Jorge Urrutia Z
Given a triangulation T of a set P of points on the plane, an edge e of T is ippable if it is incident totwo triangles whose union is a convex quadrilateral C. By ipping e we mean the operation of...
Graph classes with given 3-connected components: asymptotic enumeration and random graphs (2009)
Gimenez, Omer, Noy, Marc, Rue, Juanjo
Consider a family $\mathcal{T}$ of 3-connected graphs of moderate growth, and let $\mathcal{G}$ be the class of graphs whose 3-connected components are graphs in $\mathcal{T}$. We present a general...
A Solution to the Tennis Ball Problem (2008)
Séries Formelles, Combinatoire Algébrique, Anna De Mier, Marc Noy
Abstract. We present a complete solution to the so-called tennis ball problem, which is equivalent to counting lattice paths in the plane that use North and East steps and lie between certain...
Bijections for Baxter Families and Related Objects (2008)
Felsner, Stefan, Fusy, Éric, Noy, Marc, Orden, David
The Baxter number can be written as $B_n = \sum_0^n \Theta_{k,n-k-1}$. These numbers have first appeared in the enumeration of so-called Baxter permutations; $B_n$ is the number of Baxter...
Counting polygon dissections in the projective plane (2008)
"Vegeu el resum a l'inici del document del fitxer adjunt."
On the growth rate of minor-closed classes of graphs (2008)
Bernardi, Olivier, Noy, Marc, Welsh, Dominic
"Vegeu el resum a l'inici del document del fitxer adjunt."
Analytic Combinatorics of Non-crossing Configurations (2007)
This paper describes a systematic approach to the enumeration of "non-crossing " geometric configurations built on vertices of a convex n-gon in the plane. It relies on generating...
Esther M. Arkin, Sandor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacristan, ...
We introduce a new measure for planar point sets S. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity (S) of S is given by the smallest number of reflex vertices...
Tutte Polynomials in Square Grids (2007)
Marc Noy, Summary Frederic Chyzak
The Tutte polynomial of a graph G is a two-variable polynomial that records much information on G. In particular, dierent evaluations at integers provide the number of spanning trees, forests...
Hamiltonicity and Colorings of Arrangement Graphs (2007)
Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu
We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (affine or projective) and pseudocircle (spherical)...
Hamiltonicity and Colorings of Geometric Graphs (2007)
Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu
We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (aÆne or projective) and pseudocircle (spherical)...
Triangle-Free Planar Graphs as Segment Intersection Graphs (2007)
Natalia Castro, Francisco Javier, Cobos Juan, Carlos Dana, Alberto Márquez, Marc Noy
We prove that every triangle-free planar graph is the intersection graph of a set of segments in the plane. Moreover, the segments can be chosen in only three directions (horizontal, vertical and...
Ferran Hurtado, Marc Noy, Pedro A. Ramos, Carlos Seara
In this paper we study the separability of two disjoint object sets in the plane by two criteria: we want to know if there is a wedge or a strip separating the object sets. In the affirmative case,...
Point-sets with few k-sets Helmut Alt (2007)
Stefan Felsner, Ferran Hurtado, Marc Noy, Emo Welzl
A k-set of a finite set S of points in the plane is a subset of cardinality k that can be separated from the rest by a straight line. The question of how many k-sets a set of n points can contain is...
Esther M. Arkin, Sandor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacristan, ...
We introduce a new measure for planar point sets S. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity (S) of S is given by the smallest number of reflex vertices...
Oswin Aichholzer, Ferran Hurtado, Marc Noy
We show that the number of straight line triangulations exhibited by any set of n points in general position in the plane is bounded from below by 45 + ") n) for some "> 0. To...
A Lower Bound on the Number of Triangulations of Planar Point Sets (2007)
Oswin Aichholzer, Ferran Hurtado, Marc Noy
We show that the number of straight-edge triangulations exhibited by any set of n points in general position in the plane is bounded from below by 4 :33 ).
Ferran Hurtado, Marc Noy, Aplicada Ii, Jorge Urrutia
this paper is to show that this is indeed the case
On the growth rate of minor-closed classes of graphs (2007)
Bernardi, Olivier, Noy, Marc, Welsh, Dominic
A minor-closed class of graphs is a set of labelled graphs which is closed under isomorphism and under taking minors. For a minor-closed class $C$, we let $c_n$ be the number of graphs in $C$ which...
On the growth rate of minor-closed classes of graphs (2007)
Bernardi, Olivier, Noy, Marc, Welsh, Dominic
A minor-closed class of graphs is a set of labelled graphs which is closed under isomorphism and under taking minors. For a minor-closed class $C$, we let $c_n$ be the number of graphs in $C$ which...
On the growth rate of minor-closed classes of graphs (2007)
Bernardi, Olivier, Noy, Marc, Welsh, Dominic
A minor-closed class of graphs is a set of labelled graphs which is closed under isomorphism and under taking minors. For a minor-closed class $C$, we let $c_n$ be the number of graphs in $C$ which...
On the number of K3,3-minor-free and maximal K3,3-minor-free graphs (2006)
Gerke, Stefanie, Giménez, Omer, Noy, Marc, Weissl, Andreass
"Vegeu el resum a l'inici del document del fitxer adjunt."
Enumeration and limit laws of series-parallel graphs (2005)
Bodirsky, Manuel, Gimenez, Omer, Kang, Mihyun, Noy, Marc
We show that the number $g_n$ of labelled series-parallel graphs on $n$ vertices is asymptotically $g_n \sim g\cdot n^{-5/2} \gamma^n n!$, where $\gamma$ and $g$ are explicit computable constants. We...
Asymptotic enumeration and limit laws of planar graphs (2005)
We show an asymptotic estimate for the number of labelled planar graphs on $n$ vertices. We also find limit laws for the number of edges, the number of connected components, and other parameters in...
On the number of series parallel and outerplanar graphs (2005)
Manuel Bodirsky, Omer Giménez, Mihyun Kang, Marc Noy
We show that the number gn of labelled series-parallel graphs on n vertices is asymptotically gn ∼ g · n −5/2 γ n n!, where γ and g are explicit computable constants. We show that the number...
On the number of series parallel and outerplanar graphs (2005)
Manuel Bodirsky, Omer Giménez, Mihyun Kang, Marc Noy
Abstract. We show that the number gn of labelled series-parallel graphs on n vertices is asymptotically gn ∼ g · n −5/2 γ n n!, where γ and g are explicit computable constants. We show that...
Computing the Tutte polynomial on graphs of bounded clique-width (2005)
Abstract. The Tutte polynomial is a notoriously hard graph invariant, and efficient algorithms for it are known only for a few special graph classes, like for those of bounded tree-width. The notion...
Computing the Tutte polynomial on graphs of bounded clique-width (2005)
Abstract. The Tutte polynomial is a notoriously hard graph invariant, and efficient algorithms for it are known only for a few special graph classes, like for those of bounded tree-width. The notion...
A solution to the tennis ball problem (2003)
We present a complete solution to the so-called tennis ball problem, which is equivalent to counting lattice paths in the plane that use North and East steps and lie between certain boundaries. The...
On the reflexivity of point sets (2003)
Esther M. Arkin, Sándor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacristán, ...
We introduce a new measure for planar point sets S that captures a combinatorial distance that S is from being a convex set: The reflexivity ρ(S) ofS is given by the smallest number of reflex...
On the reflexivity of point sets (2003)
S Andor, P. Fekete, Esther M. Arkin, Esther M. Arkin, Sandor P. Fekete, Ferran Hurtado, ...
x We introduce a new measure for planar point sets S. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity (S) of S is given by the smallest number of reflex...
Lattice path matroids: enumerative aspects and Tutte polynomials (2003)
Joseph E. Bonin, Anna De Mier, Marc Noy
Abstract. Fix two lattice paths P and Q from (0, 0) to (m, r) that use East and North steps with P never going above Q. We show that the lattice paths that go from (0, 0) to (m, r) and that remain in...
On the reflexivity of point sets (2003)
Esther M. Arkin, Sándor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacristán, ...
Abstract. We introduce a new measure for planar point sets S. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity ρ(S) ofS is given by the smallest number of...
Lattice path matroids: enumerative aspects and Tutte polynomials (2002)
Bonin, Joseph E., De Mier, Anna, Noy, Marc
Fix two lattice paths P and Q from (0,0) to (m,r) that use East and North steps with P never going above Q. We show that the lattice paths that go from (0,0) to (m,r) and that remain in the region...
On the Reflexivity of Point Sets (2002)
Arkin, Esther M., Fekete, Sandor P., Hurtado, Ferran, Mitchell, Joseph S. B., Noy, Marc, Sacristan, Vera, ...
We introduce a new measure for planar point sets S that captures a combinatorial distance that S is from being a convex set: The reflexivity rho(S) of S is given by the smallest number of reflex...
Triangle-Free Planar Graphs as Segment Intersection Graphs (2002)
Natalia De Castro, Francisco Javier Cobos, Francisco Javier, Cobos Juan, Juan Carlos Dana, Alberto Marquez, ...
We prove that every triangle-free planar graph is the intersection graph of a set of segments in the plane. Moreover, the segments can be chosen in only three directions (horizontal, vertical and...
Graphs of non-crossing perfect matchings (2001)
Hernando Martín, M. Carmen, Hurtado Díaz, Fernando A. (Fernando Alfredo), Noy, Marc
Let Pn be a set of n = 2m points that are the vertices of a convex polygon, and let Mm be the graph having as vertices all the perfect matchings in the point set Pn whose edges are straight line...
Graphs of non-crossing perfect matchings (2001)
Hernando Martín, M. Carmen, Hurtado Díaz, Fernando A. (Fernando Alfredo), Noy, Marc
Let Pn be a set of n = 2m points that are the vertices of a convex polygon, and let Mm be the graph having as vertices all the perfect matchings in the point set Pn whose edges are straight line...
Graphs of non-crossing perfect matchings (2001)
Hernando Martín, M. Carmen, Hurtado Díaz, Fernando A. (Fernando Alfredo), Noy, Marc
Let Pn be a set of n = 2m points that are the vertices of a convex polygon, and let Mmbe the graph having as vertices all the perfect matchings in the point set Pn whose edgesare straight line...
Graphs of non-crossing perfect matchings (2001)
Hernando Martín, M. Carmen, Hurtado Díaz, Fernando A. (Fernando Alfredo), Noy, Marc
Let Pn be a set of n = 2m points that are the vertices of a convex polygon, and let Mm be the graph having as vertices all the perfect matchings in the point set Pn whose edges are straight line...
Analytic Combinatorics of Chord Diagrams (2000)
In this paper we study the enumeration of diagrams of n chords joining 2n points on a circle in disjoint pairs. We establish limit laws for the following three parameters: number of components, size...
Analytic Combinatorics of Chord Diagrams (2000)
In this paper we study the enumeration of diagrams of n chords joining 2n points on a circle in disjoint pairs. We establish limit laws for the following three parameters: number of components, size...
Analytic Combinatorics of Chord Diagrams (2000)
In this paper we study the enumeration of diagrams of n chords joining 2n points on a circle in disjoint pairs. We establish limit laws for the following three parameters: number of components, size...
Hamiltonicity and colorings of arrangement graphs (2000)
Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu
We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (ane or projective) and pseudocircle (spherical)...
Analytic combinatorics of chord diagrams (2000)
Projet Algo, Inria Rocquencourt, Marc Noy, Marc Noy, Marc Noy
de recherche
Analytic Combinatorics of Chord Diagrams (2000)
Philippe Flajolet, Inria Rocquencourt, Marc Noy, Marc Noy, Marc Noy
In this paper we study the enumeration of diagrams of n chords joining 2n points on a circle in disjoint pairs. We establish limit laws for the following three parameters: number of components, size...
Hamiltonicity and Colorings of (2000)
Arrangement Graphs Stefan, Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu
We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (ane or projective) and pseudocircle (spherical)...
Properties of random triangulations and trees (1999)
Luc Devroye, Inria Rocquencourt, Ferran Hurtado, Marc Noy, William Steiger
Let Tn denote the set of triangulations of a convex polygon K with n sides. We study functions that measure very natural "geometric " features of a triangulation # Tn, for example...
Enumeration of Geometric Configurations on a Convex Polygon (1999)
We survey recent work on the enumeration of non-crossing configurations on the set of vertices of a convex polygon, such as triangulations, trees, and forests. Exact formulae and limit laws are...
Random Triangulations and Trees (1999)
Luc Devroye, Philippe Flajolet, Ferran Hurtado, Marc Noy, William Steiger, Politecnica Catalunya, ...
gulation ø of K, let d i denote the degree of vertex v i , the number of (the n \Gamma 3 internal) diagonals of ø that are incident with v i . We study \Delta n (ø) = max(d i ; i = 0; : : : ; n...
Properties of random triangulations and trees (1999)
Luc Devroye, Marc Noy, Ferran Hurtado, William Steiger
Let Tn denote the set of triangulations of a convex polygon K with n sides. We study functions that measure very natural “geometric ” features of a triangulation τ ∈ Tn, for example ∆n(τ)...
Separating objects in the plane by wedges and strips (1998)
Ferran Hurtado, Marc Noy, Pedro A. Ramos, Carlos Seara
In this paper we study the separability of two disjoint sets of objects in the plane according to two criteria: wedge separability and strip separability. We give algorithms for computing all the...
Illuminating Objects with Mirrors (1998)
Ferran Hurtado, Marc Noy, Jean-Marc Robert, Vera Sacristán, Steven Skiena
Advanced computer graphics techniques such as ray tracing... In this paper, we provide algorithms and geometries providing optimal mirror placements for two natural classes of problems;...
Point-Sets With Few K-Sets (1998)
Helmut Alt, Stefan Felsner, Ferran Hurtado, Marc Noy
A k-set of a finite set S of points in the plane is a subset of cardinality k that can be separated from the rest by a straight line. The question of how many k-sets a set of n points can contain is...
Analytic Combinatorics of Non-crossing Configurations (1997)
This paper describes a systematic approach to the enumeration of «non-crossing» geometric configurations built on vertices of a convex $n$-gon in the plane. It relies on generating functions,...
Analytic Combinatorics of Non-crossing Configurations (1997)
This paper describes a systematic approach to the enumeration of «non-crossing» geometric configurations built on vertices of a convex $n$-gon in the plane. It relies on generating functions,...
Analytic Combinatorics of Non-crossing Configurations (1997)
This paper describes a systematic approach to the enumeration of «non-crossing» geometric configurations built on vertices of a convex $n$-gon in the plane. It relies on generating functions,...
Geometric tree graphs of points in convex position (1997)
Hernando Martín, M. Carmen, Hurtado Díaz, Fernando A. (Fernando Alfredo), Márquez Pérez, Alberto, Mora, Mercè, Noy, Marc
Given a set $P$ of points in the plane, the geometric tree graph of $P$ is defined as the graph $T(P)$ whose vertices are non-crossing rectilinear spanning trees of $P$, and where two trees $T_1$ and...
Geometric tree graphs of points in convex position (1997)
Hernando Martín, M. Carmen, Hurtado Díaz, Fernando A. (Fernando Alfredo), Márquez Pérez, Alberto, Mora, Mercè, Noy, Marc
Given a set $P$ of points in the plane, the geometric tree graph of$P$ is defined as the graph $T(P)$ whose vertices are non-crossingrectilinear spanning trees of $P$, and where two trees $T_1$ and...
Analytic Combinatorics of Non-crossing Configurations (1997)
Philippe Flajolet, Marc Noy, Marc Noy, Marc Noy
: This paper describes a systematic approach to the enumeration of "noncrossing " geometric configurations built on vertices of a convex n-gon in the plane. It relies on generating...
Geometric tree graphs of points in convex position (1997)
Hernando Martín, M. Carmen, Hurtado Díaz, Fernando A. (Fernando Alfredo), Márquez Pérez, Alberto, Mora, Mercè, Noy, Marc
Given a set $P$ of points in the plane, the geometric tree graph of $P$ is defined as the graph $T(P)$ whose vertices are non-crossing rectilinear spanning trees of $P$, and where two trees $T_1$ and...
Random Triangulations (Extended Abstract) (1996)
Luc Devroye, Philippe Flajolet, Inria Rocquencourt, Ferran Hurtado, Marc Noy, William Steiger
) 3 Luc Devroye McGill University luc@kriek.cs.mcgill.ca Philippe Flajolet INRIA - Rocquencourt Philippe.Flajolet@inria.fr Ferran Hurtado Universitat Politecnica de Catalunya hurtado@ma2.upc.es Marc...
Illuminating Objects with Mirrors (1996)
Ferran Hurtado, Marc Noy, Jean-Marc Robert, Vera Sacristán, Steven Skiena
Advanced computer graphics techniques such as ray tracing are being used to visualize complicated...
Stage-Graph Representations (1995)
Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Marc Noy, Jörg-Rüdiger Sack, Jorge Urrutia
We consider graph applications of the well-known paradigm "killing two birds with one stone". In the plane, this gives rise to a stage graph as follows: vertices are the points, and fu; vg...
Bijections for Baxter Families and Related Objects
Stefan Felsner, Marc Noy, Departament Matemàtica, Aplicada Ii, Éric Fusy, ...
The Baxter number Bn can be written as Bn = � n 0 Θk,n−k−1 with Θk,ℓ = 2 (k + 1) 2 (k + 2)