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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/835

Actions (login required)

View Item View Item