Efficient extraction of multiple Kuratowski subdivisions

Publikationstyp
Conference Paper
Date Issued
2007
Sprache
English
Author(s)
Chimani, Markus  
Mutzel, Petra  
Schmidt, Jens M.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/7596
First published in
Lecture notes in computer science  
Number in series
4875 LNCS
Start Page
159
End Page
170
Citation
International Symposium on Graph Drawing (GD 2007)
Publisher DOI
10.1007/978-3-540-77537-9_17
Scopus ID
2-s2.0-49949119740
Publisher
Springer
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.
DDC Class
004: Informatik