Publications related to Planar Point Sets Determine Many Pairwise Crossing Segments

Related publications (21)

Approximating the rectilinear crossing number

A straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph G, (cr) over bar (G), is the mi ...

2019

A Note on Lenses in Arrangements of Pairwise Intersecting Circles in the Plane

Rom Pinchasi

Let F be a family of n pairwise intersecting circles in the plane. We show that the number of lenses, that is convex digons, in the arrangement induced by F is at most 2n - 2. This bound is tight. Furthermore, if no two circles in F touch, then the geometr ...

Electronic Journal Of Combinatorics2024

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

An Information-Theoretic Framework for Multiplex Graphs

Anda Skeja

This thesis presents a comprehensive theory of information-theoretic measures for characterizing the complexity and higher-order dependence structures of graphs. We introduce multivariate complexity and dependence measures for graphs within the framework o ...

EPFL2024

Graph-based structures in data science : fundamental limits and applications to machine learning

Nathanaël Perraudin

State-of-the-art data analysis tools have to deal with high-dimensional data. Fortunately, the inherent dimensionality of data is often much smaller, as it has an internal structure limiting its degrees of freedom. In most cases, this structure can be appr ...

EPFL2017

On the Zarankiewicz problem for intersection hypergraphs

János Pach

Let d and t be fixed positive integers, and let denote the complete d-partite hypergraph with t vertices in each of its parts, whose hyperedges are the d-tuples of the vertex set with precisely one element from each part. According to a fundamental theorem ...

Academic Press Inc Elsevier Science2016

Maximum Independent Set: Self-Training through Dynamic Programming

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly construc ...

2023

Better Trees for Santa Claus

Etienne Michel François Bamas, Lars Rohwedder

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...

Assoc Computing Machinery2023

Coloring Relatives of Interval Overlap Graphs via On-line Games

Bartosz Maria Walczak

The main goal of this paper is to formalize and explore a connection between chromatic properties of graphs defined by geometric representations and competitivity analysis of on-line algorithms. This connection became apparent after the recent construction ...

Springer-Verlag Berlin2014

Quantization for Decentralized Learning Under Subspace Constraints

Ali H. Sayed, Stefan Vlaski, Roula Nassif

In this article, we consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints that require the minimizers across the network to lie in low-dimensional subspaces. This constrained fo ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2023

Intersection Patterns of Edges in Topological Graphs

Radoslav Fulek

This thesis is devoted to crossing patterns of edges in topological graphs. We consider the following four problems: A thrackle is a graph drawn in the plane such that every pair of edges meet exactly once: either at a common endpoint or in a proper crossi ...

EPFL2012

Distributed Graph Learning With Smooth Data Priors

Pascal Frossard, Mireille El Gheche, Isabela Cunha Maia Nobre

Graph learning is often a necessary step in processing or representing structured data, when the underlying graph is not given explicitly. Graph learning is generally performed centrally with a full knowledge of the graph signals, namely the data that live ...

IEEE2022

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

Locally Private Graph Neural Networks

Daniel Gatica-Perez

Graph Neural Networks (GNNs) have demonstrated superior performance in learning node representations for various graph inference tasks. However, learning over graph data can raise privacy concerns when nodes represent people or human-related variables that ...

ASSOC COMPUTING MACHINERY2021

Networks of Ethereum Non-Fungible Tokens: A graph-based analysis of the ERC-721 ecosystem

Marco Mattavelli, Simone Casale Brunet

Non-fungible tokens (NFTs) as a decentralized proof of ownership represent one of the main reasons why Ethereum is a disruptive technology. This paper presents the first systematic study of the interactions occurring in a number of NFT ecosystems. We illus ...

IEEE2021

Representation Learning for Multi-relational Data

Eda Bayram

Recent years have witnessed a rise in real-world data captured with rich structural information that can be better depicted by multi-relational or heterogeneous graphs. However, research on relational representation learning has so far mostly focused on th ...

EPFL2021

Routing of Electric Vehicles With Intermediary Charging Stations: A Reinforcement Learning Approach

Christophe Ballif, Nicolas Würsch, Marina Dorokhova

In the past few years, the importance of electric mobility has increased in response to growing concerns about climate change. However, limited cruising range and sparse charging infrastructure could restrain a massive deployment of electric vehicles (EVs) ...

2021

A Crossing Lemma for Multigraphs

János Pach

Let G be a drawing of a graph with n vertices and e > 4n edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvatal, Newborn, Szemeredi and Leighton, the nu ...

SPRINGER2020

Limits on amplifiers of natural selection under death-Birth updating

Andreas Pavlogiannis

The fixation probability of a single mutant invading a population of residents is among the most widely-studied quantities in evolutionary dynamics. Amplifiers of natural selection are population structures that increase the fixation probability of advanta ...

2020

Fast and Accurate Efficient Streaming Subgraph Isomorphism

Karl Aberer, Quoc Viet Hung Nguyen, Chi Thang Duong

Queries to detect isomorphic subgraphs are important in graph-based data management. While the problem of subgraph isomorphism search has received considerable attention for the static setting of a single query, or a batch thereof, existing approaches do n ...

2020