Publications related to Approximating the rectilinear crossing number

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.

Stability results for vertex Turatn problems in Kneser graphs

Abhishek Methuku

The vertex set of the Kneser graph K(n, k) is V = (([n])(k)) and two vertices are adjacent if the corresponding sets are disjoint. For any graph F, the largest size of a vertex set U subset of V such that K(n, k)[U] is F-free, was recently determined by Al ...

ELECTRONIC JOURNAL OF COMBINATORICS2019

Distributed Coloring of Graphs with an Optimal Number of Colors

Etienne Michel François Bamas

This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on ...

SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS2019

Thrackles: An improved upper bound

János Pach, Radoslav Fulek

A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, ex ...

ELSEVIER SCIENCE BV2019

Local Approximation of the Maximum Cut in Regular Graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

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

Ramsey-Turan numbers for semi-algebraic graphs

János Pach

A semi-algebraic graph G = (V, E) is a graph where the vertices are points in R-d, and the edge set E is defined by a semi-algebraic relation of constant complexity on V. In this note, we establish the following Ramsey-Turan theorem: for every integer p >= ...

ELECTRONIC JOURNAL OF COMBINATORICS2018

Global and Local Uncertainty Principles for Signals on Graphs

Pierre Vandergheynst, Nathanaël Perraudin, Benjamin Ricaud, David Shuman

Uncertainty principles such as Heisenberg's provide limits on the time-frequency concentration of a signal, and constitute an important theoretical tool for designing and evaluating linear signal transforms. Generalizations of such principles to the graph ...

2018

Rate Distortion Optimized Graph Partitioning for Omnidirectional Image Coding

Pascal Frossard, Francesca De Simone, Thomas Maugey, Mira Rizkallah

Omnidirectional images are spherical signals captured by cameras with 360-degree field of view. In order to be compressed using existing encoders, these signals are mapped to planar domain. A commonly used planar representation is the equirectangular one, ...

IEEE COMPUTER SOC2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Slobodan Mitrovic, Mohsen Ghaffari

We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum ve ...

ASSOC COMPUTING MACHINERY2018

Approximating the rectilinear crossing number

Graph Chatbot

Chat with Graph Search

Stability results for vertex Turatn problems in Kneser graphs

Distributed Coloring of Graphs with an Optimal Number of Colors

Unique decomposition of homogeneous languages and application to isothetic regions

Thrackles: An improved upper bound

Local Approximation of the Maximum Cut in Regular Graphs

Planar Point Sets Determine Many Pairwise Crossing Segments

Ramsey-Turan numbers for semi-algebraic graphs

Global and Local Uncertainty Principles for Signals on Graphs

Rate Distortion Optimized Graph Partitioning for Omnidirectional Image Coding

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Thrackles: An improved upper bound

Rate Distortion Optimized Graph Partitioning for Omnidirectional Image Coding

Stability results for vertex Turatn problems in Kneser graphs

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Planar Point Sets Determine Many Pairwise Crossing Segments

Local Approximation of the Maximum Cut in Regular Graphs

Unique decomposition of homogeneous languages and application to isothetic regions

Ramsey-Turan numbers for semi-algebraic graphs

Distributed Coloring of Graphs with an Optimal Number of Colors

Global and Local Uncertainty Principles for Signals on Graphs