Efficient Extraction of Multiple Kuratowski Subdivisions

Chimani, Markus and Mutzel, Petra and Schmidt, Jens M. (2008) Efficient Extraction of Multiple Kuratowski Subdivisions. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 159-170 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_17).

Full text not available from this repository.


A graph is planar if and only if it does not contain a Kuratowski subdivision. Hence such a subdivision can be used as a witness for non-planarity. Modern planarity testing algorithms allow to extract a single such witness in linear time. We present the first linear time algorithm which is able to extract multiple Kuratowski subdivisions at once. This is of particular interest for, e.g., Branch-and-Cut algorithms which require multiple such subdivisions to generate cut constraints. The algorithm is not only described theoretically, but we also present an experimental study of its implementation.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_17
Classifications:G Algorithms and Complexity > G.840 Planarization
ID Code:835

Repository Staff Only: item control page


OGDF - Open Graph Drawing Framework. Univeristy of Dortmund, Chair of Algorithm Engineering, 2007. Website under Construction.

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(5-6):303-325, 1997.

J. M. Boyer, P. F. Cortese, M. Patrignani, and G. Di Battista. Stop minding your P's and Q's: Implementing a fast and simple DFS-based planarity testing and embedding algorithm. In G. Liotta, editor, Proc. GD '03, volume 2912 of LNCS, pages 25-36. Springer-Verlag, 2003.

J. M. Boyer and W. J. Myrvold. Stop minding your P's and Q's: A simplified O(n) planar embedding algorithm. In Proc. SODA '99, pages 140-146, Philadelphia, PA, USA, 1999. SIAM.

J. M. Boyer and W. J. Myrvold. On the cutting edge: Simplified O(n) planarity by edge addition. Journal of Graph Algorithms and Applications, 8(3):241-273, 2004.

C. Buchheim, M. Chimani, D. Ebner, C. Gutwenger, M. Jünger, G. W. Klau, P. Mutzel, and R. Weiskircher. A branch-and-cut approach to the crossing number problem. Discrete Optimization, 2007. to appear. A preliminary version appeared in Proc. GD '05, LNCS 3843, pp. 37-48.

M. Chimani, P. Mutzel, and J. M. Schmidt. Efficient extraction of multiple Kuratowski subdivisions (TR). Technical Report TR07-1-002, Chair for Algorithm Engineering, Dep. of CS, University Dortmund, 2007. see http://ls11-www.cs.uni-dortmund.de/people/chimani/.

D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. R. Westbrook, and M. Yung. Maintenance of minimum spanning forest in a dynamic planar graph. J. Algorithms, 13(1):33-54, 1992.

H. de Fraysseix and P. Ossona de Mendez. On cotree-critical and DFS cotree-critical graphs. Journal of Graph Algorithms an Applications, 7(4):411-427, 2003.

H. de Fraysseix and P. Rosenstiehl. A characterization of planar graphs by Trémaux orders. Combinatorica, 5(2):127-135, 1985.

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

M. Jünger and P. Mutzel. Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica, 16(1):33-59, 1996.

K. Kuratowski. Sur le problème de corbes gauches en topologie. Fundamenta Mathematicae, 15:271-283, 1930.

J. M. Schmidt. Effiziente Extraktion von Kuratowski-Teilgraphen. Diploma thesis, Department of Computer Science, University of Dortmund, March 2007.

S. G. Williamson. Depth-first search and Kuratowski subgraphs. J. ACM, 31(4):681-693, 1984.