Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649423 | Discrete Mathematics | 2009 | 18 Pages |
Abstract
We present a reduction method that reduces a graph to a smaller core graph which behaves invariant with respect to non-planarity measures like crossing number, skewness, coarseness, and thickness. The core reduction is based on the decomposition of a graph into its triconnected components and can be computed in linear time. It has applications in heuristic and exact optimization algorithms for the non-planarity measures mentioned above. Experimental results show that this strategy reduces the number of edges by 45% in average for a widely used benchmark set of graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Markus Chimani, Carsten Gutwenger,