-
Chapter and Conference Paper
Bounded Representations of Interval and Proper Interval Graphs
Klavík et al. [ar**v:1207.6960] recently introduced a generalization of recognition called the bounded representation problem which we study for the classes of interval and proper interval graphs. The input gives...
-
Chapter and Conference Paper
Grid Drawings and the Chromatic Number
A grid drawing of a graph maps vertices to the grid ℤ d and edges to line segments that avoid grid points representing other vertices. We show that a graph G is q ...
-
Chapter and Conference Paper
Drawing Graphs Using a Small Number of Obstacles
An obstacle representation of a graph G is a set of points in the plane representing the vertices of G, together with a set of polygonal obstacles such that two vertices of G are connected by an edge in G if and ...
-
Article
Crossing Numbers and Combinatorial Characterization of Monotone Drawings of \(K_n\)
In 1958, Hill conjectured that the minimum number of crossings in a drawing of \(K_n\) ...
-
Article
Open AccessOn the Beer Index of Convexity and Its Variants
Let S be a subset of \(\mathbb {R}^d\) ...
-
Chapter and Conference Paper
Holes in 2-Convex Point Sets
Let S be a set of n points in the plane in general position (no three points from S are collinear). For a positive integer k, a k-hole in S is a convex polygon with k vertices from S and no points of S in its int...
-
Article
Drawing Graphs Using a Small Number of Obstacles
An obstacle representation of a graph G is a set of points in the plane representing the vertices of G, together with a set of polygonal obstacles such that two vertices of G are connected by an edge in G if and ...
-
Chapter and Conference Paper
Minimal Representations of Order Types by Geometric Graphs
In order to have a compact visualization of the order type of a given point set S, we are interested in geometric graphs on S with few edges that unequivocally display the order type of S. We introduce the concep...
-
Chapter and Conference Paper
On Erdős–Szekeres-Type Problems for k-convex Point Sets
We study Erdős–Szekeres-type problems for k-convex point sets, a recently introduced notion that naturally extends the concept of convex position. A finite set S of n points is k-convex if there exists a spanning...
-
Article
Covering Lattice Points by Subspaces and Counting Point–Hyperplane Incidences
Let d and k be integers with \(1 \le k \le d-1\) ...
-
Article
Open AccessAlmost-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 ...
-
Chapter and Conference Paper
On Off-Diagonal Ordered Ramsey Numbers of Nested Matchings
For two ordered graphs \(G^<\) G < ...
-
Chapter and Conference Paper
On Ordered Ramsey Numbers of Tripartite 3-Uniform Hypergraphs
For \(k \ge 2\) k ≥ 2 ...
-
Chapter and Conference Paper
Tight Bounds on the Expected Number of Holes in Random Point Sets
For integers \(d\ge 2\) d ≥ 2 ...
-
Chapter and Conference Paper
Big Ramsey Degrees of the Generic Partial Order
As a result of 33 intercontinental Zoom calls, we characterise big Ramsey degrees of the generic partial order in a similar way as Devlin characterised big Ramsey degrees of the generic linear order (the order...
-
Chapter and Conference Paper
Big Ramsey Degrees and Forbidden Cycles
Using the Carlson–Simpson theorem, we give a new general condition for a structure in a finite binary relational language to have finite big Ramsey degrees.
-
Chapter and Conference Paper
Implementation of Sprouts: A Graph Drawing Game
Sprouts is a two-player pencil-and-paper game invented by John Conway and Michael Paterson in 1967. In the game, the players take turns in joining dots by curves according to simple rules, until one player can...
-
Article
Hypergraph Based Berge Hypergraphs
Fix a hypergraph \({\mathcal {F}}\) F . A hypergraph
-
Article
Big Ramsey Degrees of 3-Uniform Hypergraphs Are Finite
We prove that the universal homogeneous 3-uniform hypergraph has finite big Ramsey degrees. This is the first case where big Ramsey degrees are known to be finite for structures in a non-binary language.
