Space crossing numbers

2011
Rapport ou document de travail

Résumé

We define the crossing number for an embedding of a graph G into R^3, and prove a lower bound on it which almost implies the classical crossing lemma. We also give sharp bounds on the space crossing numbers of pseudo-random graphs.

Source officielle

https://infoscience.epfl.ch/record/175650?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Space crossing numbers

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

In Medio Stat Virtus: Combining Boolean and Pattern Matching

A full characterization of invariant embeddability of unimodular planar graphs

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

A full characterization of invariant embeddability of unimodular planar graphs

In Medio Stat Virtus: Combining Boolean and Pattern Matching