Logo

Login | Create Account

Non-Planar Core Reduction of Graphs

Gutwenger, Carsten and Chimani, Markus (2006) Non-Planar Core Reduction of Graphs. [Conference Paper]

Full text not available from this repository.

Abstract

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
Classifications:G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.840 Planarization
ID Code:693
Deposited By:GDEA, Administration
Deposited On:22 Feb 2006
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=3843&spage=223

Repository Staff Only: item control page

References

M. Chimani and C. Gutwenger.: On the minimum cut of planarizations. Technical report, University of Dortmund, Germany, 2005.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu.: An experimental comparison of four graph drawing algorithms. Comput. Geom. Theory Appl., 7:303--325, 1997.

G. Di Battista and R.Tamassia.: On-line maintanance of triconnected components with SPQR-trees. Algorithmica, 15:302--318, 1996.

G. Di Battista and R. Tamassia.: On-line planarity testing. SIAM J. Comput., 25(5):956--997, 1996.

M. R. Garey and D. S. Johnson.: Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods, 4(3):312--316, 1983.

C. Gutwenger and P. Mutzel.: A linear time implementation of SPQR trees. J. Marks, editor, Proc. GD 2000, volume 1984 of LNCS, pages 77--90. Springer-Verlag, 2001.

C. Gutwenger and P. Mutzel.: An experimental study of crossing minimization heuristics. G. Liotta, editor, Proc. GD 2003, volume 2912 of LNCS, pages 13--24. Springer, 2004.

C. Gutwenger, P. Mutzel, and R. Weiskircher.: Inserting an edge into a planar graph. Algorithmica, 41(4):289--308, 2005.

J. Hopcroft and R. E. Tarjan.: Efficient planarity testing. J. ACM, 21(4):549--568, 1974.

C. Kuratowski.: Sur le probleme des courbes gauches en topologie. Fundamenta Mathematicae, 15:271--283, 1930.

A. Liebers.: Planarizing graphs --- A survey and annotated bibliography. J. Graph Algorithms and Applications, 5(1):1--74, 2001.

P. C. Liu and R. C. Geldmacher.: On the deletion of nonplanar edges of a graph. Congr. Numerantium, 24:727--738, 1979.

A. Mansfield.: Determining the thickness of graphs is NP-hard. Math. Proc. Camb. Philos. Soc., 93:9--23, 1983.

Petra Mutzel, Thomas Odenthal, and Mark Scharbrodt.: The thickness of graphs: A survey. Graphs and Combinatorics, 14(1):59--73, 1998.

J.Siran: Additivity of the crossing number of graphs with connectivity 2. Periodica Mathematica Hungarica, 15(4):301--305, 1984.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.