Source author record

Clément Requilé

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

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Enumeration of chordal planar graphs and maps

We determine the number of labelled chordal planar graphs with $n$ vertices, which is asymptotically $c_1\cdot n^{-5/2} γ^n n!$ for a constant $c_1>0$ and $γ\approx 11.89235$ . We also determine the number of rooted simple chordal planar maps with $n$ edges, which is asymptotically $c_2 n^{-3/2} δ^n$ , where $δ= 1/σ\approx 6.40375$ , and $σ$ is an algebraic number of degree 12. The proofs are based on combinatorial decompositions and singularity analysis. Chordal planar graphs (or maps) are a natural example of a subcritical class of graphs in which the class of 3-connected graphs is relatively rich. The 3-connected members are precisely chordal triangulations, those obtained starting from $K_4$ by repeatedly adding vertices adjacent to an existing triangular face.

preprint2016arXiv

Strong Ramsey Games: Drawing on an infinite board

We consider the strong Ramsey-type game $\mathcal{R}^{(k)}(\mathcal{H}, \aleph_0)$ , played on the edge set of the infinite complete $k$ -uniform hypergraph $K^k_{\mathbb{N}}$ . Two players, called FP (the first player) and SP (the second player), take turns claiming edges of $K^k_{\mathbb{N}}$ with the goal of building a copy of some finite predetermined $k$ -uniform hypergraph $\mathcal{H}$ . The first player to build a copy of $\mathcal{H}$ wins. If no player has a strategy to ensure his win in finitely many moves, then the game is declared a draw. In this paper, we construct a $5$ -uniform hypergraph $\mathcal{H}$ such that $\mathcal{R}^{(5)}(\mathcal{H}, \aleph_0)$ is a draw. This is in stark contrast to the corresponding finite game $\mathcal{R}^{(5)}(\mathcal{H}, n)$ , played on the edge set of $K^5_n$ . Indeed, using a classical game-theoretic argument known as \emph{strategy stealing} and a Ramsey-type argument, one can show that for every $k$ -uniform hypergraph $\mathcal{G}$ , there exists an integer $n_0$ such that FP has a winning strategy for $\mathcal{R}^{(k)}(\mathcal{G}, n)$ for every $n \geq n_0$ .

preprint2015arXiv

Variants of Plane Diameter Completion

The {\sc Plane Diameter Completion} problem asks, given a plane graph $G$ and a positive integer $d$ , if it is a spanning subgraph of a plane graph $H$ that has diameter at most $d$ . We examine two variants of this problem where the input comes with another parameter $k$ . In the first variant, called BPDC, $k$ upper bounds the total number of edges to be added and in the second, called BFPDC, $k$ upper bounds the number of additional edges per face. We prove that both problems are {\sf NP}-complete, the first even for 3-connected graphs of face-degree at most 4 and the second even when $k=1$ on 3-connected graphs of face-degree at most 5. In this paper we give parameterized algorithms for both problems that run in $O(n^{3})+2^{2^{O((kd)^2\log d)}}\cdot n$ steps.

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.