| Title: |
On the 2-colored crossing number |
| Authors: |
Aichholzer, Oswin; Fabila-Monroy, Ruy; Fuchs, Adrian; Hidalgo-Toscano, Carlos; Parada, Irene; Vogtenhuber, Birgit; Zaragoza, Francisco |
| Publication Year: |
2019 |
| Collection: |
Computer Science; Mathematics |
| Subject Terms: |
Computer Science - Computational Geometry; Mathematics - Combinatorics |
| Description: |
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.; Comment: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019) |
| Document Type: |
Working Paper |
| Access URL: |
http://arxiv.org/abs/1908.06461 |
| Accession Number: |
edsarx.1908.06461 |
| Database: |
arXiv |