 |
| Home | Issues | About JGAA | Instructions for Authors |
|
Special Issue on Selected Papers from the Nineteenth International Symposium on Graph Drawing, GD 2011
DOI: 10.7155/jgaa.00264
Advances in the Planarization Method: Effective Multiple Edge Insertions
Markus Chimani and
Carsten Gutwenger
Vol. 16, no. 3, pp. 729-757, 2012. Regular paper.
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.
|
Submitted: November 2011.
Reviewed: February 2012.
Revised: February 2012.
Accepted: February 2012.
Final: March 2012.
Published: September 2012.
|
Journal publisher
|
Journal network
|
Journal Supporters
|
