On chirality of toroidal embeddings of polyhedral graphs

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.

We prove the non-planarity of a family of 3-regular graphs constructed from the solutions to the Markoff equation x2 + y2 + z2 = xyz modulo prime numbers greater than 7. The proof uses Euler characteristic and an enumeration of the short cycles in these gr ...

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Decentralized learning is appealing as it enables the scalable usage of large amounts of distributed data and resources (without resorting to any central entity), while promoting privacy since every user minimizes the direct exposure of their data. Yet, wi ...

We present an algorithmic approach to discover, study, and design multistable elastic knots. Elastic knots are physical realizations of closed curves embedded in 3-space. When endowed with the material thickness and bending resistance of a physical wire, t ...

Knots are the weakest link in surgical sutures, serving as mechanical ligatures between filaments. Exceeding their safe operational limits can cause fatal complications. The empirical nature of present guidelines calls for a predictive understanding of the ...

A graph H is a minor of a second graph G if G can be transformed into H by two operations: 1) deleting nodes and/or edges, or 2) contracting edges. Coarse-grained reconfigurable array (CGRA) application mapping is closely related to the graph minor problem ...

In this thesis, we study the mechanics of tight physical knots. Knots are omnipresent in surgery, climbing, and sailing, with disastrous consequences when the filament or the rope fails to perform its function. Even if the importance of mechanical analysis ...

Graph machine learning offers a powerful framework with natural applications in scientific fields such as chemistry, biology and material sciences. By representing data as a graph, we encode the prior knowledge that the data is composed of a set of entiti ...

We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying ...

Unsupervised graph representation learning aims to learn low-dimensional node embeddings without supervision while preserving graph topological structures and node attributive features. Previous Graph Neural Networks (GNN) require a large number of labeled ...

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

Information retrieval (IR) systems such as search engines are important for people to find what they need among the tremendous amount of data available in their organization or on the Internet. These IR systems enable users to search in a large data collec ...

Graph neural networks take node features and graph structure as input to build representations for nodes and graphs. While there are a lot of focus on GNN models, understanding the impact of node features and graph structure to GNN performance has received ...

We approach the graph generation problem from a spectral perspective by first generating the dominant parts of the graph Laplacian spectrum and then building a graph matching these eigenvalues and eigenvectors. Spectral conditioning allows for direct model ...

We perform a combined experimental and computational investigation of the clove hitch knot. We develop a physical model for the clove hitch by tying an elastic rod onto a rigid cylinder. In the experiments, we characterize the mechanical performance, geome ...

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to t ...

Graph Neural Networks (GNNs) are learning models aimed at processing graphs and signals on graphs. The most popular and successful GNNs are based on message passing schemes. Such schemes inherently have limited expressive power when it comes to distinguish ...

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emer ...

Community structure in graph-modeled data appears in a range of disciplines that comprise network science. Its importance relies on the influence it bears on other properties of graphs such as resilience, or prediction of missing connections. Nevertheless, ...

On chirality of toroidal embeddings of polyhedral graphs

Chat with Graph Search

Non-planarity of Markoff graphs mod p

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

The Privacy Power of Correlated Noise in Decentralized Learning

Computational Exploration of Multistable Elastic Knots

The strength of surgical knots involves a critical interplay between friction and elastoplasticity

GRAMM: Fast CGRA Application Mapping Based on A Heuristic for Finding Graph Minors

Mechanics of Physical Knots: From Filaments in Contact to Surgical Suturing

Equivariant Neural Architectures for Representing and Generating Graphs

ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS

Unsupervised Graph Representation Learning with Cluster-aware Self-training and Refining

Results on Sparse Integer Programming and Geometric Independent Sets

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Graph Embedding for Retrieval

Nature vs. Nurture: Feature vs. Structure for Graph Neural Networks

SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators

Exploring the inner workings of the clove hitch knot

On the robustness of the metric dimension of grid graphs to adding a single edge

A Topological characterisation of Weisfeiler-Leman equivalence classes

Space-Efficient Representations of Graphs

Graph signal processing tailored for subgraph focus and community structure