Non-Planar Core Reduction of Graphs

Gutwenger, Carsten and Chimani, Markus (2006) Non-Planar Core Reduction of Graphs. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 223-234(Official URL:

Full text not available from this repository.


We present a reduction method that reduces a graph to a smaller core graph which behaves invariant with respect to planarity measures like crossing number, skewness, 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 planarity measures mentioned above. Experimental results show that this strategy yields a reduction to 2/3 in average for a widely used benchmark set of graphs.

Item Type: Conference Paper
Additional Information: 10.1007/11618058_21
Classifications: G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.840 Planarization

Actions (login required)

View Item View Item