Infoscience

Report

Space crossing numbers

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.

    Reference

    • EPFL-REPORT-175650

    Record created on 2012-03-13, modified on 2016-08-09

Related material