Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
The paper in this page has been just accepted in JGAA and is in the queue for being assigned a volume and an issue number. It has been accepted by one of the JGAA editors and its content will no longer be modified. However, the publication format of the paper may still be subject to minor changes.
|
DOI: 10.7155/jgaa.00264 Advances in the Planarization Method: Effective Multiple Edge Insertions Markus Chimani and Carsten Gutwenger To be published in the Special Issue of GD 2011. Abstract The planarization method is the strongest known method to heuristically find good solutions to the general crossing number problem in graphs: Starting from a planar subgraph, one iteratively inserts edges, representing crossings via dummy vertices. In the recent years, several improvements both from the practical and the theoretical point of view have been made. We review these advances and conduct an extensive study of the algorithms' practical implications. Thereby, we also present the first implementation of an approximation algorithm for the crossing number problem of general graphs. We compare the obtained results with known exact crossing number solutions and show that modern techniques allow surprisingly tight results in practice.
|
Posted here: March 2012. |
| Journal of Graph Algorithms and Applications |