A planarity test via construction sequences

Publikationstyp
Conference Paper
Date Issued
2013-10-15
Sprache
English
Author(s)
Schmidt, Jens M.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/7654
First published in
Lecture notes in computer science  
Number in series
8087 LNCS
Start Page
765
End Page
776
Citation
International Symposium on Mathematical Foundations of Computer Science (MFCS 2013)
Publisher DOI
10.1007/978-3-642-40313-2_67
Scopus ID
2-s2.0-84885232426
Publisher
Springer
Linear-time algorithms for testing the planarity of a graph are well known for over 35 years. However, these algorithms are quite involved and recent publications still try to give simpler linear-time tests. We give a conceptually simple reduction from planarity testing to the problem of computing a certain construction of a 3-connected graph. This implies a linear-time planarity test. Our approach is radically different from all previous linear-time planarity tests; as key concept, we maintain a planar embedding that is 3-connected at each point in time. The algorithm computes a planar embedding if the input graph is planar and a Kuratowski-subdivision otherwise.
DDC Class
004: Informatik