An effective crossing minimisation heuristic based on star insertion

DOI10.7155/JGAA.00487zbMath1407.05220arXiv1804.09900OpenAlexW2963557107MaRDI QIDQ3121515

Kieran Clancy, Michael Haythorpe, Alex Newcombe

Publication date: 18 March 2019

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

star insertion problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (9)

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics ⋮ Unnamed Item ⋮ Star-struck by fixed embeddings: modern crossing number heuristics ⋮ There are no cubic graphs on 26 vertices with crossing number 10 or 11 ⋮ ON THE CROSSING NUMBER OF THE JOIN OF THE WHEEL ON FIVE VERTICES WITH THE DISCRETE GRAPH ⋮ Rotation and crossing numbers for join products ⋮ On the crossing numbers of Cartesian products of small graphs with paths, cycles and stars ⋮ A survey of graphs with known or bounded crossing numbers ⋮ ON THE CROSSING NUMBER OF THE CARTESIAN PRODUCT OF A SUNLET GRAPH AND A STAR GRAPH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Crossing number and weighted crossing number of near-planar graphs
• Vertex insertion approximates the crossing number of apex graphs
• How to draw a planar graph on a grid
• Inserting an edge into a planar graph
• An algorithm for drawing general undirected graphs
• A tighter insertion-based approximation of the crossing number
• An experimental comparison of four graph drawing algorithms.
• Crossing Number is NP-Complete
• A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
• On the Crossing Number of Almost Planar Graphs
• The crossing numbers of some generalized Petersen graphs.
• Graph Drawing
• Experiments on Exact Crossing Minimization Using Column Generation
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• The crossing number of K₁₁ is 100
• Graph Drawing
• On a problem of P. Turan concerning graphs
• Advances in the Planarization Method: Effective Multiple Edge Insertions
• Graph Drawing
• Inserting an edge into a geometric embedding

This page was built for publication: An effective crossing minimisation heuristic based on star insertion