On the 2-colored crossing number
Authors:
Preprint
Abstract
Let $D$ be a straight-line drawing of a graph. The rectilinear 2-colored crossing number of $D$ is the minimum number of crossings between edges of the same color, taken over all possible 2-colorings of the edges of $D$. First, we show lower and upper bounds on the rectilinear 2-colored crossing number for the complete graph $K_n$. To obtain this result, we prove that asymptotic bounds can be derived from optimal and near-optimal instances with few vertices. We obtain such instances using a combination of heuristics and integer programming. Second, for any fixed drawing of $K_n$, we improve the bound on the ratio between its rectilinear 2-colored crossing number and its rectilinear crossing number.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- On topological graphs with at most four crossings per edgeComputational Geometry, 2019
- Note on k-planar crossing numbersComputational Geometry, 2018
- The 2-Page Crossing Number of $K_{n}$ K nDiscrete & Computational Geometry, 2013
- Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic methodRandom Structures & Algorithms, 2008
- A central approach to bound the number of crossings in a generalized configurationElectronic Notes in Discrete Mathematics, 2008
- On k-planar crossing numbersDiscrete Applied Mathematics, 2007
- Abstract order type extension and new results on the rectilinear crossing numberComputational Geometry, 2007
- Biplanar Crossing Numbers I: A Survey of Results and Problems2006
- Lectures on Discrete Geometry2002
- A Positive Fraction Erdos - Szekeres TheoremDiscrete & Computational Geometry, 1998