An effective crossing minimisation heuristic based on star insertion

DOI10.7155/JGAA.00487MaRDI QIDQ3121515zbMATH OpenOpenAlexFDO

Authors Kieran Clancy, Michael Haythorpe, Alex Newcombe

Publication date 18 March 2019

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

star insertion problem

Mathematics Subject Classification ID

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

Abstract: We present a new heuristic method for minimising crossings in a graph. The method is based upon repeatedly solving the so-called {em star insertion problem} in the setting where the combinatorial embedding is fixed, and has several desirable characteristics for practical use. We introduce the method, discuss some aspects of algorithm design for our implementation, and provide some experimental results. The results indicate that our method compares well to existing methods, and also that it is suitable for dense instances.

Recommendations

• Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
• Graph Drawing
• Crossing Minimisation Heuristics for 2-page Drawings
• A Geometric Heuristic for Rectilinear Crossing Minimization
• Advances in the planarization method: effective multiple edge insertions

Cites work

• A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• Advances in the planarization method: effective multiple edge insertions
• An algorithm for drawing general undirected graphs
• An experimental comparison of four graph drawing algorithms.
• Crossing number and weighted crossing number of near-planar graphs
• Crossing Number is NP-Complete
• Experiments on Exact Crossing Minimization Using Column Generation
• Graph Drawing
• Graph Drawing
• Graph Drawing
• How to draw a planar graph on a grid
• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• scientific article; zbMATH DE number 3668651 (Why is no real title available?)
• scientific article; zbMATH DE number 1791676 (Why is no real title available?)
• Inserting a vertex into a planar graph
• Inserting an edge into a geometric embedding
• Inserting an edge into a planar graph
• On a problem of P. Turan concerning graphs
• On graph crossing number and edge planarization
• On the Crossing Number of Almost Planar Graphs
• The crossing number of K₁₁ is 100
• The crossing numbers of some generalized Petersen graphs.
• Vertex insertion approximates the crossing number of apex graphs

Cited in

(10)

• Star-struck by fixed embeddings: modern crossing number heuristics
• Rotation and crossing numbers for join products
• There are no cubic graphs on 26 vertices with crossing number 10 or 11
• On the crossing number of the Cartesian product of a sunlet graph and a star graph
• On the crossing number of the join of the wheel on five vertices with the discrete graph
• A survey of graphs with known or bounded crossing numbers
• Graph Drawing
• A note on isomorphic generalized Petersen graphs with an application to the crossing number of \(GP[3k-1,k]\) and \(GP[3k+1,k]\)
• Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
• On the crossing numbers of Cartesian products of small graphs with paths, cycles and stars

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3121515)