Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.
DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.
By a polygonization of a finite point set S in the plane we understand a simple polygon having S as the set of its vertices. Let B and R be sets of blue and red points, respectively, in the plane such that is in general position, and the convex hull of B c ...
We consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with n vertices admits a RAC drawing with at most 1 bend or 2 bends pe ...
We study the impact of metric constraints on the realizability of planar graphs. Let G be a subgraph of a planar graph H (where H is the "host" of G). The graph G is free in H if for every choice of positive lengths for the edges of G, the host H has a pla ...
Let P be a set of n > d points in for d >= 2. It was conjectured by Zvi Schur that the maximum number of (d-1)-dimensional regular simplices of edge length diam(P), whose every vertex belongs to P, is n. We prove this statement under the condition that any ...
We show that the maximum total perimeter of k plane convex bodies with disjoint interiors lying inside a given convex body C is equal to , in the case when C is a square or an arbitrary triangle. A weaker bound is obtained for general plane convex bodies. ...
Let d(1) < d(2) < ... denote the set of all distances between two vertices of a convex n-gon. We show that the number of pairs of vertices at distance d(2) from one another is at most n + O(1). (C) 2013 Elsevier B.V. All rights reserved. ...
The inverse degree of a graph is the sum of the reciprocals of the degrees of its vertices. We prove that in any connected planar graph, the diameter is at most 5/2 times the inverse degree, and that this ratio is tight. To develop a crucial surgery method ...
In a seminal paper published in 1946, Erd ̋os initiated the investigation of the distribution of distances generated by point sets in metric spaces. In spite of some spectacular par- tial successes and persistent attacks by generations of mathe- maticians, ...
Given a set P of n points in ℝd, let d1 > d2 >...denote all distinct inter-point distances generated by point pairs in P. It was shown by Schur, Martini, Perles, and Kupitz that there is at most oned-dimensional regular simplex of edge length d1 whos ...
