Publications related to Planarity testing

Related publications (29)

Non-planarity of Markoff graphs mod p

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

European Mathematical Soc-Ems2024

Frequent asymmetric migrations suppress natural selection in spatially structured populations

Anne-Florence Raphaëlle Bitbol, Alia Abbara

Natural microbial populations often have complex spatial structures. This can impact their evolution, in particular the ability of mutants to take over. While mutant fixation probabilities are known to be unaffected by sufficiently symmetric structures, ev ...

Oxford Univ Press2023

A Solution to Adaptive Mobile Manipulator Throwing

Aude Billard, Aradhana Nayak

Mobile manipulator throwing is a promising method to increase the flexibility and efficiency of dynamic manipulation in factories. Its major challenge is to efficiently plan a feasible throw under a wide set of task specifications. We show that the mobile ...

IEEE2022

Incompleteness of graph neural networks for points clouds in three dimensions

Michele Ceriotti, Sergey Pozdnyakov

Graph neural networks (GNN) are very popular methods in machine learning and have been applied very successfully to the prediction of the properties of molecules and materials. First-order GNNs are well known to be incomplete, i.e. there exist graphs that ...

IOP Publishing Ltd2022

Motif Cut Sparsifiers

Mikhail Kapralov, Jakab Tardos, Mikhail Makarov

A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...

IEEE COMPUTER SOC2022

Sketches, metrics and fast algorithms

Navid Nouri

As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in most applications, even storing datasets as acquired has ...

EPFL2022

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

Akash Kumar

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

IEEE COMPUTER SOC2022

Active Subdivision Surfaces for the Semiautomatic Segmentation of Biomedical Volumes

Michaël Unser, Anaïs Laure Marie-Thérèse Badoual

We present a new family of active surfaces for the semiautomatic segmentation of volumetric objects in 3D biomedical images. We represent our deformable model by a subdivision surface encoded by a small set of control points and generated through a geometr ...

2021

Towards Tight Bounds for Spectral Sparsification of Hypergraphs

Mikhail Kapralov, Jakab Tardos

Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applicati ...

ASSOC COMPUTING MACHINERY2021

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, Jakab Tardos, Navid Nouri, Aidasadat Mousavifar

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O) over tilde (n) space, and with high probability, recover ...

ASSOC COMPUTING MACHINERY2020

Vector-Based 3D Graphic Statics: a framework for the design of spatial structures based on the relation between form and forces

Corentin Jean Dominique Fivet

This article develops a vector-based 3D graphic statics framework that uses synthetic and intuitive graphical means for the analysis and design of spatial structures such as networks of bar elements in static equilibrium. It is intended to support the coll ...

2019

Dual-Band Circularly Polarized Transmitarray Antenna for Satellite Communications at (20 to 30) GHz

Juan Ramon Mosig, Maria Garcia Vigueras, Santiago Capdevila Cascante, Joana Rita Alves dos Santos Silva, Hamed Hasani

A novel dual-band polarization-independent transmitarray is introduced in this paper for communication systems in Ka-band. Thanks to its unit-cell topology, the transmitarray antenna demonstrates almost complete independent performance at two design freque ...

2019

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

Mechanics of a pressure-controlled adhesive membrane for soft robotic gripping on curved surfaces

Jamie Paik, Metin Sitti, Sukho Song

This paper aims at understanding the adhesion mechanics of a pressure-controlled adhesive thin elastomeric membrane for soft robotic gripping on non-planar, curved surfaces. The adhesive elastic membrane is lined with gecko-inspired microfiber arrays and c ...

2019

Photoinitiator-free Laser Fabrication of Ultra-compact, Low-loss Waveguides in Polydimethylsiloxane

Demetri Psaltis, Christophe Moser, Ye Pu, Giulia Panusa, Jieping Wang

Owing to its excellent elasticity, wide spectral range of transparency, and outstanding chemical and thermal stability, polydimethylsiloxane (PDMS) is an elastomer of great technological importance, being widely used in the fabrication of microfluidic and ...

SPIE-INT SOC OPTICAL ENGINEERING2018

Note on k-planar crossing numbers

János Pach

The crossing number CR(G) of a graph G = (V, E) is the smallest number of edge crossings over all drawings of G in the plane. For any k >= 1, the k-planar crossing number of G, CRk(G), is defined as the minimum of CR(G(0)) + CR(G(1)) + ... + CR(G(k-i)) ove ...

Elsevier Science Bv2018

On chirality of toroidal embeddings of polyhedral graphs

Senja Dominique Barthel

We investigate properties of spatial graphs on the standard torus. It is known that nontrivial embeddings of planar graphs in the torus contain a nontrivial knot or a non-split link due to [2, 3]. Building on this and using the chirality of torus knots and ...

World Scientific Publishing2017

Graph learning under sparsity priors

Pascal Frossard, Ntorina Thanou, Hermina Petric Maretic

Graph signals offer a very generic and natural representation for data that lives on networks or irregular structures. The actual data structure is however often unknown a priori but can sometimes be estimated from the knowledge of the application domain. ...

Ieee2017

Heuristic-driven Graph Wavelet Modeling of Complex Terrain

Alexandre Buttler, François Golay, Alexander Ludwig Johannes Peringer

We present a novel method for building a multiresolution representation of large digital surface models. The surface points coincide with the nodes of a planar graph which can be processed using a critically sampled, invertible lifting scheme. To drive the ...

Spie-Int Soc Optical Engineering2015

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