Star-struck by fixed embeddings: modern crossing number heuristics

DOI10.1007/978-3-030-92931-2_3OpenAlexW3195407697MaRDI QIDQ2151428

Markus Chimani, Max Ilsen, Tilo Wiedera

Publication date: 1 July 2022

Full work available at URL: https://arxiv.org/abs/2108.11443

zbMATH Keywords

crossing numberalgorithm engineeringexperimental evaluation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (1)

Inserting Multiple Edges into a Planar Graph

Uses Software

• OGDF
• Algorithm 447

Cites Work

• Unnamed Item
• Crossing number and weighted crossing number of near-planar graphs
• A branch-and-cut approach to the crossing number problem
• Non-planar core reduction of graphs
• Inserting an edge into a planar graph
• A tighter insertion-based approximation of the crossing number
• An experimental comparison of four graph drawing algorithms.
• Crossing number is hard for cubic graphs
• DRAWING DIRECTED ACYCLIC GRAPHS: AN EXPERIMENTAL STUDY
• Finding Triangles for Maximum Planar Subgraphs
• An effective crossing minimisation heuristic based on star insertion
• Crossing Number is NP-Complete
• A New Approach to Exact Crossing Minimization
• An ILP-based Proof System for the Crossing Number Problem
• Generating Random Regular Graphs Quickly
• Reducibility among Combinatorial Problems
• Experiments on exact crossing minimization using column generation
• Advances in the Planarization Method: Effective Multiple Edge Insertions
• Graph Drawing

This page was built for publication: Star-struck by fixed embeddings: modern crossing number heuristics