## Abstract

Research about crossings is typically about minimization. In this pa- per, we consider maximizing the number of crossings over all possible ways to draw a given graph in the plane. Alpert et al. [Electron. J. Combin., 2009] conjectured that any graph has a convex straight-line drawing, that is, a drawing with vertices in convex position, that maximizes the number of edge crossings. We disprove this conjecture by constructing a planar graph on twelve vertices that admits a non-convex drawing with more crossings than any convex drawing. Bald et al. [Proc. COCOON, 2016] showed that it is NP-hard to compute the maximum number of crossings of a geometric graph and that the weighted geometric case is NP-hard to approximate. We strengthen these results by showing hardness of approx- imation even for the unweighted geometric case. We also prove that the unweighted topological case is NP-hard.

Original language | English (US) |
---|---|

Pages (from-to) | 67-87 |

Number of pages | 21 |

Journal | Journal of Graph Algorithms and Applications |

Volume | 22 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2018 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science
- Computer Science Applications
- Geometry and Topology
- Computational Theory and Mathematics