Publications related to Planar separator theorem

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

Pre-annealing for improved LPCVD deposited boron-doped poly-Si hole-selective contacts

Franz-Josef Haug, Luca Massimiliano Antognini, Josua Andreas Stückelberger, Xinyu Zhang, Zhao Wang, Jie Yang

We demonstrate the beneficial effect of a pre-annealing step prior to the boron diffusion on passivation and contact resistivity of industrially LPCVD deposited poly-Si/SiOX hole-selective contacts. We investigate the influence of the pre-annealing tempera ...

ELSEVIER2023

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

Yichen Xu, Qiang Liu, Feng Yu

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

Assoc Computing Machinery2023

A Solution to Adaptive Mobile Manipulator Throwing

Aude Billard, Yang Liu, 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

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

From kirigami to hydrogels: a tutorial on designing conformally transformable surfaces

Tian Chen, Yingying Ren, Yue Wang

Elastic surfaces that morph between multiple geometrical configurations are of significant engineering value, with applications ranging from the deployment of space-based PV arrays, the erection of temporary shelters, and the realization of flexible displa ...

2023

Space-Efficient Representations of Graphs

Jakab Tardos

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

EPFL2022

Atomic subgraphs and the statistical mechanics of networks

Sofia Charlotta Olhede

We develop random graph models where graphs are generated by connecting not only pairs of vertices by edges, but also larger subsets of vertices by copies of small atomic subgraphs of arbitrary topology. This allows for the generation of graphs with extens ...

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

Minimal graphs for 2-factor extension

Dominique de Werra

Let G = (V, E) be a simple loopless finite undirected graph. We say that G is (2-factor) expandable if for any non-edge uv, G + uv has a 2-factor F that contains uv. We are interested in the following: Given a positive integer n = vertical bar V vertical b ...

ELSEVIER2020

Realizability of planar point embeddings from angle measurements

Majed El Helou, Adam James Scholefield, Frederike Dümbgen

Localization of a set of nodes is an important and a thoroughly researched problem in robotics and sensor networks. This paper is concerned with the theory of localization from inner-angle measurements. We focus on the challenging case where no anchor loca ...

IEEE2020

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

Planar Point Sets Determine Many Pairwise Crossing Segments

János Pach, Gábor Tardos

We show that any set of n points in general position in the plane determines n(1-o(1)) pairwise crossing segments. The best previously known lower bound, Omega(root n), was proved more than 25 years ago by Aronov, Erdos, Goddard, Kreitman, Krugerman, Pach, ...

ASSOC COMPUTING MACHINERY2019

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, Pierluigi D'Acunto

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, Joana Rita Alves dos Santos Silva, Santiago Capdevila Cascante, 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

New Notions and Constructions of Sparsification for Graphs and Hypergraphs

Ola Nils Anders Svensson

A sparsifier of a graph G (Bencztir and Karger; Spielman and Teng) is a sparse weighted subgraph (G) over tilde that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs ...

IEEE COMPUTER SOC2019

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

High-performance normally-off tri-gate GaN power MOSFETs

Elison de Nazareth Matioli, Jun Ma, Luca Nela, Minghua Zhu

In this work, we present the investigation of the combination of gate recess and tri-gate structures to achieve high performance normally-off GaN-on-Si MOSFETs with high positive threshold voltage ( VTH ), low specific on resistance ( RON,SP ) and high out ...

IEEE2019

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

Jamie Paik, Sukho Song, Metin Sitti

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