Source author record

Pavel Valtr

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 math.PR Computational Complexity Data Structures and Algorithms

Catalog footprint

Research overview

22works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Noncrossing Longest Paths and Cycles

Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, shortest spanning trees, shortest spanning paths, and shortest spanning cycles on a given point set are inherently noncrossing. However, the longest such structures need not be noncrossing. In fact, it is intuitive to expect many edge crossings in various geometric graphs that are longest. Recently, Álvarez-Rebollar, Cravioto-Lagos, Marín, Solé-Pi, and Urrutia (Graphs and Combinatorics, 2024) constructed a set of points for which the longest perfect matching is noncrossing. They raised several challenging questions in this direction. In particular, they asked whether the longest spanning path, on any finite set of points in the plane, must have a pair of crossing edges. They also conjectured that the longest spanning cycle must have a pair of crossing edges. In this paper, we give a negative answer to the question and also refute the conjecture. We present a framework for constructing arbitrarily large point sets for which the longest perfect matchings, the longest spanning paths, and the longest spanning cycles are noncrossing.

preprint2023arXiv

Structure of betweenness uniform graphs with low values of betweenness centrality

This work deals with undirected graphs that have the same betweenness centrality for each vertex, so-called betweenness uniform graphs (or BUGs). The class of these graphs is not trivial and its classification is still an open problem. Recently, Gago, Coroničová-Hurajová and Madaras conjectured that for every rational $α\ge 3/4$ there exists a BUG having betweenness centrality~ $α$ . We disprove this conjecture, and provide an alternative view of the structure of betweenness-uniform graphs from the point of view of their complement. This allows us to characterise all the BUGs with betweennes centrality at most 9/10, and show that their betweenness centrality is equal to $\frac{\ell}{\ell+1}$ for some integer $\ell\le 9$ . We conjecture that this characterization extends to all the BUGs with betweenness centrality smaller than~1.

preprint2022arXiv

Erdős--Szekeres-type problems in the real projective plane

We consider point sets in the real projective plane $\mathbb{R}P^2$ and explore variants of classical extremal problems about planar point sets in this setting, with a main focus on Erdős--Szekeres-type problems. We provide asymptotically tight bounds for a variant of the Erdős--Szekeres theorem about point sets in convex position in $\mathbb{R}P^2$ , which was initiated by Harborth and Möller in 1994. The notion of convex position in $\mathbb{R}P^2$ agrees with the definition of convex sets introduced by Steinitz in 1913. For $k \geq 3$ , an (\affine) $k$ -hole in a finite set $S \subseteq \mathbb{R}^2$ is a set of $k$ points from $S$ in convex position with no point of $S$ in the interior of their convex hull. After introducing a new notion of $k$ -holes for points sets from $\mathbb{R}P^2$ , called projective $k$ -holes, we find arbitrarily large finite sets of points from $\mathbb{R}P^2$ with no \projective 8-holes, providing an analogue of a classical planar construction by Horton from 1983. We also prove that they contain only quadratically many \projective $k$ -holes for $k \leq 7$ . On the other hand, we show that the number of $k$ -holes can be substantially larger in~ $\mathbb{R}P^2$ than in $\mathbb{R}^2$ by constructing, for every $k \in \{3,\dots,6\}$ , sets of $n$ points from $\mathbb{R}^2 \subset \mathbb{R}P^2$ with $Ω(n^{3-3/5k})$ \projective $k$ -holes and only $O(n^2)$ \affine $k$ -holes. Last but not least, we prove several other results, for example about projective holes in random point sets in $\mathbb{R}P^2$ and about some algorithmic aspects. The study of extremal problems about point sets in $\mathbb{R}P^2$ opens a new area of research, which we support by posing several open problems.

preprint2022arXiv

Holes and islands in random point sets

For $d\in\mathbb{N}$ , let $S$ be a set of points in $\mathbb{R}^d$ in general position. A set $I$ of $k$ points from $S$ is a $k$ -island in $S$ if the convex hull $\mathrm{conv}(I)$ of $I$ satisfies $\mathrm{conv}(I) \cap S = I$ . A $k$ -island in $S$ in convex position is a $k$ -hole in $S$ . For $d,k\in\mathbb{N}$ and a convex body $K\subseteq\mathbb{R}^d$ of volume $1$ , let $S$ be a set of $n$ points chosen uniformly and independently at random from $K$ . We show that the expected number of $k$ -holes in $S$ is in $O(n^d)$ . Our estimate improves and generalizes all previous bounds. In particular, we estimate the expected number of empty simplices in $S$ by $2^{d-1}\cdot d!\cdot\binom{n}{d}$ . This is tight in the plane up to a lower-order term. Our method gives an asymptotically tight upper bound $O(n^d)$ even in the much more general setting, where we estimate the expected number of $k$ -islands in $S$ .

preprint2022arXiv

Tight bounds on the expected number of holes in random point sets

For integers $d \geq 2$ and $k \geq d+1$ , a $k$ -hole in a set $S$ of points in general position in $\mathbb{R}^d$ is a $k$ -tuple of points from $S$ in convex position such that the interior of their convex hull does not contain any point from $S$ . For a convex body $K \subseteq \mathbb{R}^d$ of unit $d$ -dimensional volume, we study the expected number $EH^K_{d,k}(n)$ of $k$ -holes in a set of $n$ points drawn uniformly and independently at random from $K$ . We prove an asymptotically tight lower bound on $EH^K_{d,k}(n)$ by showing that, for all fixed integers $d \geq 2$ and $k\geq d+1$ , the number $EH_{d,k}^K(n)$ is at least $Ω(n^d)$ . For some small holes, we even determine the leading constant $\lim_{n \to \infty}n^{-d}EH^K_{d,k}(n)$ exactly. We improve the currently best known lower bound on $\lim_{n \to \infty}n^{-d}EH^K_{d,d+1}(n)$ by Reitzner and Temesvari (2019). In the plane, we show that the constant $\lim_{n \to \infty}n^{-2}EH^K_{2,k}(n)$ is independent of $K$ for every fixed $k \geq 3$ and we compute it exactly for $k=4$ , improving earlier estimates by Fabila-Monroy, Huemer, and Mitsche (2015) and by the authors (2020).

preprint2021arXiv

Graph Drawing and Network Visualization GD2020

Proceedings of GD2020: This volume contains the papers presented at GD~2020, the 28th International Symposium on Graph Drawing and Network Visualization, held on September 18-20, 2020 online. Graph drawing is concerned with the geometric representation of graphs and constitutes the algorithmic core of network visualization. Graph drawing and network visualization are motivated by applications where it is crucial to visually analyse and interact with relational datasets. Information about the conference series and past symposia is maintained at http://www.graphdrawing.org. The 2020 edition of the conference was hosted by University Of British Columbia, with Will Evans as chair of the Organizing Committee. A total of 251 participants attended the conference.

preprint2020arXiv

A superlinear lower bound on the number of 5-holes

Let $P$ be a finite set of points in the plane in general position, that is, no three points of $P$ are on a common line. We say that a set $H$ of five points from $P$ is a $5$ -hole in $P$ if $H$ is the vertex set of a convex $5$ -gon containing no other points of $P$ . For a positive integer $n$ , let $h_5(n)$ be the minimum number of 5-holes among all sets of $n$ points in the plane in general position. Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for $h_5(n)$ have been of order $Ω(n)$ and $O(n^2)$ , respectively. We show that $h_5(n) = Ω(n\log^{4/5}{n})$ , obtaining the first superlinear lower bound on $h_5(n)$ . The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set $P$ of points in the plane in general position is partitioned by a line $\ell$ into two subsets, each of size at least 5 and not in convex position, then $\ell$ intersects the convex hull of some 5-hole in $P$ . The proof of this result is computer-assisted.

preprint2020arXiv

Almost-equidistant sets

For a positive integer $d$ , a set of points in $d$ -dimensional Euclidean space is called almost-equidistant if for any three points from the set, some two are at unit distance. Let $f(d)$ denote the largest size of an almost-equidistant set in $d$ -space. It is known that $f(2)=7$ , $f(3)=10$ , and that the extremal almost-equidistant sets are unique. We give independent, computer-assisted proofs of these statements. It is also known that $f(5) \ge 16$ . We further show that $12\leq f(4)\leq 13$ , $f(5)\leq 20$ , $18\leq f(6)\leq 26$ , $20\leq f(7)\leq 34$ , and $f(9)\geq f(8)\geq 24$ . Up to dimension $7$ , our work is based on various computer searches, and in dimensions $6$ to $9$ , we give constructions based on the known construction for $d=5$ . For every dimension $d \ge 3$ , we give an example of an almost-equidistant set of $2d+4$ points in the $d$ -space and we prove the asymptotic upper bound $f(d) \le O(d^{3/2})$ .

preprint2020arXiv

Long Alternating Paths Exist

Let $P$ be a set of $2n$ points in convex position, such that $n$ points are colored red and $n$ points are colored blue. A non-crossing alternating path on $P$ of length $\ell$ is a sequence $p_1, \dots, p_\ell$ of $\ell$ points from $P$ so that (i) all points are pairwise distinct; (ii) any two consecutive points $p_i$ , $p_{i+1}$ have different colors; and (iii) any two segments $p_i p_{i+1}$ and $p_j p_{j+1}$ have disjoint relative interiors, for $i \neq j$ . We show that there is an absolute constant $\varepsilon > 0$ , independent of $n$ and of the coloring, such that $P$ always admits a non-crossing alternating path of length at least $(1 + \varepsilon)n$ . The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least $(1 + \varepsilon)n$ points of $P$ . This is a properly colored matching whose segments are pairwise disjoint and intersected by common line. For both versions, this is the first improvement of the easily obtained lower bound of $n$ by an additive term linear in $n$ . The best known published upper bounds are asymptotically of order $4n/3+o(n)$ .

preprint2020arXiv

On the Average Complexity of the $k$ -Level

Let ${\cal L}$ be an arrangement of $n$ lines in the Euclidean plane. The \emph{ $k$ -level} of ${\cal L}$ consists of all vertices $v$ of the arrangement which have exactly $k$ lines of ${\cal L}$ passing below $v$ . The complexity (the maximum size) of the $k$ -level in a line arrangement has been widely studied. In 1998 Dey proved an upper bound of $O(n\cdot (k+1)^{1/3})$ . Due to the correspondence between lines in the plane and great-circles on the sphere, the asymptotic bounds carry over to arrangements of great-circles on the sphere, where the $k$ -level denotes the vertices at distance at most $k$ to a marked cell, the \emph{south pole}. We prove an upper bound of $O((k+1)^2)$ on the expected complexity of the $k$ -level in great-circle arrangements if the south pole is chosen uniformly at random among all cells. We also consider arrangements of great $(d-1)$ -spheres on the sphere $\mathbb{S}^d$ which are orthogonal to a set of random points on $\mathbb{S}^d$ . In this model, we prove that the expected complexity of the $k$ -level is of order $Θ((k+1)^{d-1})$ .

preprint2016arXiv

Low Ply Drawings of Trees

We consider the recently introduced model of \emph{low ply graph drawing}, in which the ply-disks of the vertices do not have many common overlaps, which results in a good distribution of the vertices in the plane. The \emph{ply-disk} of a vertex in a straight-line drawing is the disk centered at it whose radius is half the length of its longest incident edge. The largest number of ply-disks having a common overlap is called the \emph{ply-number} of the drawing. We focus on trees. We first consider drawings of trees with constant ply-number, proving that they may require exponential area, even for stars, and that they may not even exist for bounded-degree trees. Then, we turn our attention to drawings with logarithmic ply-number and show that trees with maximum degree $6$ always admit such drawings in polynomial area.

preprint2016arXiv

On the Beer index of convexity and its variants

Let $S$ be a subset of $\mathbb{R}^d$ with finite positive Lebesgue measure. The Beer index of convexity $\operatorname{b}(S)$ of $S$ is the probability that two points of $S$ chosen uniformly independently at random see each other in $S$ . The convexity ratio $\operatorname{c}(S)$ of $S$ is the Lebesgue measure of the largest convex subset of $S$ divided by the Lebesgue measure of $S$ . We investigate the relationship between these two natural measures of convexity. We show that every set $S\subseteq\mathbb{R}^2$ with simply connected components satisfies $\operatorname{b}(S)\leqα\operatorname{c}(S)$ for an absolute constant $α$ , provided $\operatorname{b}(S)$ is defined. This implies an affirmative answer to the conjecture of Cabello et al. that this estimate holds for simple polygons. We also consider higher-order generalizations of $\operatorname{b}(S)$ . For $1\leq k\leq d$ , the $k$ -index of convexity $\operatorname{b}_k(S)$ of a set $S\subseteq\mathbb{R}^d$ is the probability that the convex hull of a $(k+1)$ -tuple of points chosen uniformly independently at random from $S$ is contained in $S$ . We show that for every $d\geq 2$ there is a constant $β(d)>0$ such that every set $S\subseteq\mathbb{R}^d$ satisfies $\operatorname{b}_d(S)\leqβ\operatorname{c}(S)$ , provided $\operatorname{b}_d(S)$ exists. We provide an almost matching lower bound by showing that there is a constant $γ(d)>0$ such that for every $\varepsilon\in(0,1)$ there is a set $S\subseteq\mathbb{R}^d$ of Lebesgue measure $1$ satisfying $\operatorname{c}(S)\leq\varepsilon$ and $\operatorname{b}_d(S)\geqγ\frac{\varepsilon}{\log_2{1/\varepsilon}}\geqγ\frac{\operatorname{c}(S)}{\log_2{1/\operatorname{c}(S)}}$ .

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

On the Geometric Ramsey Number of Outerplanar Graphs

We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on $2n$ vertices are bounded by $O(n^{3})$ and $O(n^{10})$ , in the convex and general case, respectively. We then apply similar methods to prove an $n^{O(\log(n))}$ upper bound on the Ramsey number of a path with $n$ ordered vertices.

preprint2013arXiv

Splittings and Ramsey Properties of Permutation Classes

We say that a permutation p is 'merged' from permutations q and r, if we can color the elements of p red and blue so that the red elements are order-isomorphic to q and the blue ones to r. A 'permutation class' is a set of permutations closed under taking subpermutations. A permutation class C is 'splittable' if it has two proper subclasses A and B such that every element of C can be obtained by merging an element of A with an element of B. Several recent papers use splittability as a tool in deriving enumerative results for specific permutation classes. The goal of this paper is to study splittability systematically. As our main results, we show that if q is a sum-decomposable permutation of order at least four, then the class Av(q) of all q-avoiding permutations is splittable, while if q is a simple permutation, then Av(q) is unsplittable. We also show that there is a close connection between splittings of certain permutation classes and colorings of circle graphs of bounded clique size. Indeed, our splittability results can be interpreted as a generalization of a theorem of Gyárfás stating that circle graphs of bounded clique size have bounded chromatic number.

preprint2012arXiv

Empty pentagons in point sets with collinearities

An empty pentagon in a point set P in the plane is a set of five points in P in strictly convex position with no other point of P in their convex hull. We prove that every finite set of at least 328k^2 points in the plane contains an empty pentagon or k collinear points. This is optimal up to a constant factor since the (k-1)x(k-1) grid contains no empty pentagon and no k collinear points. The previous best known bound was doubly exponential.

preprint2012arXiv

Graph sharing games: complexity and connectivity

We study the following combinatorial game played by two players, Alice and Bob, which generalizes the Pizza game considered by Brown, Winkler and others. Given a connected graph G with nonnegative weights assigned to its vertices, the players alternately take one vertex of G in each turn. The first turn is Alice's. The vertices are to be taken according to one (or both) of the following two rules: (T) the subgraph of G induced by the taken vertices is connected during the whole game, (R) the subgraph of G induced by the remaining vertices is connected during the whole game. We show that if rules (T) and/or (R) are required then for every epsilon > 0 and for every positive integer k there is a k-connected graph G for which Bob has a strategy to obtain (1-epsilon) of the total weight of the vertices. This contrasts with the original Pizza game played on a cycle, where Alice is known to have a strategy to obtain 4/9 of the total weight. We show that the problem of deciding whether Alice has a winning strategy (i.e., a strategy to obtain more than half of the total weight) is PSPACE-complete if condition (R) or both conditions (T) and (R) are required. We also consider a game played on connected graphs (without weights) where the first player who violates condition (T) or (R) loses the game. We show that deciding who has the winning strategy is PSPACE-complete.

preprint2011arXiv

On empty pentagons and hexagons in planar point sets

We give improved lower bounds on the minimum number of $k$ -holes (empty convex $k$ -gons) in a set of $n$ points in general position in the plane, for $k=5,6$ .

preprint2011arXiv

On the connectivity of visibility graphs

The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesník (1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesník by showing that for any two vertices v and w in a graph of diameter 2, if deg(v) <= deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. Furthermore, we find that in visibility graphs every minimum edge cut is the set of edges incident to a vertex of minimum degree. For vertex-connectivity, we prove that every visibility graph with n vertices and at most l collinear vertices has connectivity at least (n-1)/(l-1), which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, in the case that l=4 we improve this bound to two thirds of the minimum degree.

preprint2011arXiv

Universal Sets for Straight-Line Embeddings of Bicolored Graphs

A set S of n points is 2-color universal for a graph G on n vertices if for every proper 2-coloring of G and for every 2-coloring of S with the same sizes of color classes as G has, G is straight-line embeddable on S. We show that the so-called double chain is 2-color universal for paths if each of the two chains contains at least one fifth of all the points, but not if one of the chains is more than approximately 28 times longer than the other. A 2-coloring of G is equitable if the sizes of the color classes differ by at most 1. A bipartite graph is equitable if it admits an equitable proper coloring. We study the case when S is the double-chain with chain sizes differing by at most 1 and G is an equitable bipartite graph. We prove that this S is not 2-color universal if G is not a forest of caterpillars and that it is 2-color universal for equitable caterpillars with at most one half non-leaf vertices. We also show that if this S is equitably 2-colored, then equitably properly 2-colored forests of stars can be embedded on it.

preprint2010arXiv

Large convexly independent subsets of Minkowski sums

Let $E_d(n)$ be the maximum number of pairs that can be selected from a set of $n$ points in $R^d$ such that the midpoints of these pairs are convexly independent. We show that $E_2(n)\geq Ω(n\sqrt{\log n})$ , which answers a question of Eisenbrand, Pach, Rothvoß, and Sopher (2008) on large convexly independent subsets in Minkowski sums of finite planar sets, as well as a question of Halman, Onn, and Rothblum (2007). We also show that $\lfloor\frac{1}{3}n^2\rfloor\leq E_3(n)\leq \frac{3}{8}n^2+O(n^{3/2})$ . Let $W_d(n)$ be the maximum number of pairwise nonparallel unit distance pairs in a set of $n$ points in some $d$ -dimensional strictly convex normed space. We show that $W_2(n)=Θ(E_2(n))$ and for $d\geq 3$ that $W_d(n)\sim\frac12\left(1-\frac{1}{a(d)}\right)n^2$ , where $a(d)\in N$ is related to strictly antipodal families. In fact we show that the same asymptotics hold without the requirement that the unit distance pairs form pairwise nonparallel segments, and also if diameter pairs are considered instead of unit distance pairs.

preprint2008arXiv

Solution of Peter Winkler's Pizza Problem

Bob cuts a pizza into slices of not necessarily equal size and shares it with Alice by alternately taking turns. One slice is taken in each turn. The first turn is Alice's. She may choose any of the slices. In all other turns only those slices can be chosen that have a neighbor slice already eaten. We prove a conjecture of Peter Winkler by showing that Alice has a strategy for obtaining 4/9 of the pizza. This is best possible, that is, there is a cutting and a strategy for Bob to get 5/9 of the pizza. We also give a characterization of Alice's best possible gain depending on the number of slices. For a given cutting of the pizza, we describe a linear time algorithm that computes Alice's strategy gaining at least 4/9 of the pizza and another algorithm that computes the optimal strategy for both players in any possible position of the game in quadratic time. We distinguish two types of turns, shifts and jumps. We prove that Alice can gain 4/9, 7/16 and 1/3 of the pizza if she is allowed to make at most two jumps, at most one jump and no jump, respectively, and the three constants are the best possible.

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.

Pavel Valtr

Research overview

Is this your work?

22 publications

Noncrossing Longest Paths and Cycles

Structure of betweenness uniform graphs with low values of betweenness centrality

Erdős--Szekeres-type problems in the real projective plane

Holes and islands in random point sets

Tight bounds on the expected number of holes in random point sets

Graph Drawing and Network Visualization GD2020

A superlinear lower bound on the number of 5-holes

Almost-equidistant sets

Long Alternating Paths Exist

On the Average Complexity of the $k$ -Level

Low Ply Drawings of Trees

On the Beer index of convexity and its variants

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

On the Geometric Ramsey Number of Outerplanar Graphs

Splittings and Ramsey Properties of Permutation Classes

Empty pentagons in point sets with collinearities

Graph sharing games: complexity and connectivity

On empty pentagons and hexagons in planar point sets

On the connectivity of visibility graphs

Universal Sets for Straight-Line Embeddings of Bicolored Graphs

Large convexly independent subsets of Minkowski sums

Solution of Peter Winkler's Pizza Problem

See the researcher in context

Building this map preview

Pavel Valtr

Research overview

Is this your work?

22 publications

Noncrossing Longest Paths and Cycles

Structure of betweenness uniform graphs with low values of betweenness centrality

Erdős--Szekeres-type problems in the real projective plane

Holes and islands in random point sets

Tight bounds on the expected number of holes in random point sets

Graph Drawing and Network Visualization GD2020

A superlinear lower bound on the number of 5-holes

Almost-equidistant sets

Long Alternating Paths Exist

On the Average Complexity of the kkk-Level

Low Ply Drawings of Trees

On the Beer index of convexity and its variants

On kkk-Gons and kkk-Holes in Point Sets

On the Geometric Ramsey Number of Outerplanar Graphs

Splittings and Ramsey Properties of Permutation Classes

Empty pentagons in point sets with collinearities

Graph sharing games: complexity and connectivity

On empty pentagons and hexagons in planar point sets

On the connectivity of visibility graphs

Universal Sets for Straight-Line Embeddings of Bicolored Graphs

Large convexly independent subsets of Minkowski sums

Solution of Peter Winkler's Pizza Problem

See the researcher in context

Building this map preview

On the Average Complexity of the $k$ -Level

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