Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.
AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.
We consider straight-line outerplanar drawings of outerplanar graphs in which a small number of distinct edge slopes are used, that is, the segments representing edges are parallel to a small number of directions. We prove that Delta - 1 edge slopes suffic ...
A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. An old conjecture states that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). Fox and Pach showed that every k-quasi-pla ...
We study some variants of Conway’s thrackle conjecture. A tangle is a graph drawn in the plane such that its edges are represented by continuous arcs, and any two edges share precisely one point, which is either a common endpoint or an interior point at wh ...
Polygonal objects are prevalent in man-made scenes. Early approaches to detecting them relied mainly on geometry while subsequent ones also incorporated appearance-based cues. It has recently been shown that this could be done fast by searching for cycles ...
We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different sl ...
We analyze the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin de ...
We consider graphs that admit polyline drawings where all crossings occur at the same angle alpha is an element of (0, pi/2]. We prove that every graph on n vertices that admits such a polyline drawing with at most two bends per edge has O(n) edges. This r ...
Given a graph G, an obstacle representation of G is a set of points in the plane representing the vertices of G, together with a set of connected obstacles such that two vertices of G are joined by an edge if and only if the corresponding points can be con ...
We propose a method for learning dictionaries towards sparse approximation of signals defined on vertices of arbitrary graphs. Dictionaries are expected to describe effectively the main spatial and spectral components of the signals of interest, so that th ...
This thesis is devoted to crossing patterns of edges in topological graphs. We consider the following four problems: A thrackle is a graph drawn in the plane such that every pair of edges meet exactly once: either at a common endpoint or in a proper crossi ...
