Publication

Lower bounds on the obstacle number of graphs

Related publications (116)

Graph Chatbot

Chat with Graph Search

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.

Scaling a Reliable Distributed System

Alexandre David Olivier Maurer

We consider the problem of reliably connecting an arbitrarily large set of computers (nodes) with communication channels. Reliability means here the ability, for any two nodes, to remain connected (i.e., their ability to communicate) with probability at le ...

LPD EPFL2016

Principal Patterns on Graphs: Discovering Coherent Structures in Datasets

Pierre Vandergheynst, Kirell Maël Benzi, Benjamin Ricaud

Graphs are now ubiquitous in almost every field of research. Recently, new research areas devoted to the analysis of graphs and data associated to their vertices have emerged. Focusing on dynamical processes, we propose a fast, robust and scalable framewor ...

Ieee-Inst Electrical Electronics Engineers Inc2016

Decomposition of Multiple Packings with Subquadratic Union Complexity

János Pach, Bartosz Maria Walczak

Suppose k is a positive integer and X is a k-fold packing of the plane by infinitely many arc-connected compact sets, which means that every point of the plane belongs to at most k sets. Suppose there is a function f(n) = o(n(2)) with the property that any ...

Cambridge Univ Press2016

Modeling and Controlling epidemics : a graph perspective

Philippe Sakari Rossinelli

The social and economical impact a virus has in a population is not negligible. For this reason, gaining a theoretical understanding of the behavior of a virus is of prime importance. This project is going to be divided in several parts. First, we will dis ...

2015

Curve Graphs On Surfaces Of Infinite Type

Hugo Parlier, Ariadna Fossas Tenas

We define and study analogs of curve graphs for infinite type surfaces. Our definitions use the geometry of a fixed surface and vertices of our graphs are infinite multicurves which are bounded in both a geometric and a topological sense. We show that the ...

Suomalainen Tiedeakatemia2015

Spectrum-Adapted Tight Graph Wavelet and Vertex-Frequency Frames

Pierre Vandergheynst, David Shuman

We consider the problem of designing spectral graph filters for the construction of dictionaries of atoms that can be used to efficiently represent signals residing on weighted graphs. While the filters used in previous spectral graph wavelet constructions ...

Institute of Electrical and Electronics Engineers2015

Reconstruction of Images from Gabor Graphs with Applications in Facial Image Processing

Graphs labeled with complex-valued Gabor jets are one of the important data formats for face recognition and the classification of facial images into medically relevant classes like genetic syndromes. We here present an interpolation rule and an iterative ...

2015

Double-Normal Pairs In Space

János Pach

A double-normal pair of a finite set S of points that spans R-d is a pair of points {p, q} from S such that S lies in the closed strip bounded by the hyperplanes through p and q perpendicular to pq. A double-normal pair {p, q} is strict if S \ {p,q} lies i ...

London Mathematical Society, Cambridge2015

Approximations for Stochastic Graph Rewriting

Sandro Stucki

In this note we present a method to compute approximate descriptions of a class of stochastic systems. For the method to apply, the system must be presented as a Markov chain on a state space consisting in graphs or graph-like objects, and jumps must be de ...

Springer International Publishing2014

Diameter Graphs in R-4

Andrei Kupavskii

A diameter graph in is a graph whose set of vertices is a finite subset of and whose set of edges is formed by pairs of vertices that are at diameter apart. This paper is devoted to the study of different extremal properties of diameter graphs in and on a ...

Springer2014