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

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, 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