Publication

Virtual Round Table on ten leading questions for network research

Related publications (34)

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.

THE NUMBER OF EDGES IN k-QUASI-PLANAR GRAPHS

János Pach

A graph drawn in the plane is called k-quasi-planar if it does not contain k pair-wise crossing edges. It has been conjectured for a long time that for every fixed k, the maximum number of edges of a k-quasi-planar graph with n vertices is O(n). The best k ...

Siam Publications2013

A Bayesian Method for Matching Two Similar Graphs without Seeds

Matthias Grossglauser, Pedram Pedarsani

Approximate graph matching (AGM) refers to the problem of mapping the vertices of two structurally similar graphs, which has applications in social networks, computer vision, chemistry, and biology. Given its computational cost, AGM has mostly been limited ...

2013

Lower bounds on the obstacle number of graphs

János Pach, Doemoetoer Palvoelgyi, Padmini Mukkamala

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 ...

2012

Graphs That Admit Polyline Drawings with Few Crossing Angles

Radoslav Fulek

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 ...

2012

Wavelet Frames On Graphs Defined By Fmri Functional Connectivity

Dimitri Nestor Alice Van De Ville, Nora Leonardi

Multiscale representations such as the wavelet transform are useful for many signal processing tasks. Graphs are flexible models to represent complex networks and a spectral graph wavelet transform (SGWT) has recently been developed as a generalization of ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2011

Beyond Graphs: A New Synthesis

Dario Floreano, Claudio Mattiussi, Daniel Marbach, Peter Dürr

Artiﬁcial neural networks, electronic circuits, and gene networks are some examples of systems that can be modeled as networks, that is, as collections of interconnected nodes. In this paper we introduce the concept of terminal graph (t-graph for short), w ...

2011

Algebraic Algorithms for Vector Network Coding

Christina Fragouli, Javad Ebrahimi Boroojeni

We develop new algebraic algorithms for scalar and vector network coding. In vector network coding, the source multicasts information by transmitting vectors of length L, while intermediate nodes process and combine their incoming packets by multiplying th ...

Institute of Electrical and Electronics Engineers2011

Graphs that Admit Right Angle Crossing Drawings

Radoslav Fulek, Balázs Keszegh, Filip Moric

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 ...

2010

Algebraic techniques for deterministic networks

Christina Fragouli, Javad Ebrahimi Boroojeni

We here summarize some recent advances in the study of linear deterministic networks, recently proposed as approximations for wireless channels. This work started by extending the algebraic framework developed for multicasting over graphs in [1] to include ...

2010

Blockers and transversals

Dominique de Werra, Bernard Ries, Rico Zenklusen

Given an undirected graph G = (V, E) with matching number v(G), we define d-blockers as subsets of edges B such that nu((V, E \ B)) = d. ...

2009