Publication

Drawing cubic graphs with at most five slopes

Publications associées (102)

Graph Chatbot

Chattez avec Graph Search

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.

Connectez-vous pour utiliser Chat avec Graph Search

Induced Matchings In Graphs Of Degree At Most 4

Viet Hang Nguyen

For a graph G, let nu(s)(G) be the strong matching number of G. We prove the sharp bound nu(s)(G) >= n(G)/9 for every graph G of maximum degree at most 4 and without isolated vertices that does not contain a certain blown-up 5-cycle as a component. This re ...

Siam Publications2016

On the Difficulty of Selecting Ising Models with Approximate Recovery

Volkan Cevher, Jonathan Mark Scarlett

In this paper, we consider the problem of estimating the underlying graph associated with an Ising model given a number of independent and identically distributed samples. We adopt an approximate recovery criterion that allows for a number of missed edges ...

Ieee-Inst Electrical Electronics Engineers Inc2016

A Multiscale Pyramid Transform for Graph Signals

Pierre Vandergheynst, David Shuman, Mohammadjavad Faraji

Multiscale transforms designed to process analog and discrete-time signals and images cannot be directly applied to analyze high-dimensional data residing on the vertices of a weighted graph, as they do not capture the intrinsic topology of the graph data ...

Institute of Electrical and Electronics Engineers2016

Song Recommendation with Non-Negative Matrix Factorization and Graph Total Variation

Pierre Vandergheynst, Kirell Maël Benzi, Xavier Bresson, Vasilis Kalofolias

This work formulates a novel song recommender system as a matrix completion problem that benefits from collaborative filtering through Non-negative Matrix Factorization (NMF) and content-based filtering via total variation (TV) on graphs. The graphs encode ...

Ieee2016

Removing and Adding Edges for the Traveling Salesman Problem

Ola Nils Anders Svensson

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a d ...

Assoc Computing Machinery2016

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

A Precise Threshold For Quasi-Ramsey Numbers

János Pach

We consider the variation of Ramsey numbers introduced by Erdos and Pach [J. Graph Theory, 7 (1983), pp. 137-147], where instead of seeking complete or independent sets we only seek a t-homogeneous set, a vertex subset that induces a subgraph of minimum de ...

Siam Publications2015

Free Edge Lengths in Plane Graphs

Radoslav Fulek, Filip Moric

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

Springer2015

Moment Semantics for Reversible Rule-Based Systems

Sandro Stucki

We develop a notion of stochastic rewriting over marked graphs – i.e. directed multigraphs with degree constraints. The approach is based on double-pushout (DPO) graph rewriting. Marked graphs are expressive enough to internalize the ‘no-dangling-edge’ con ...

Springer International Publishing2015

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