Planarity Certificates

Lars Noschinski

11 November 2015

Abstract

This development provides a formalization of planarity based on combinatorial maps and proves that Kuratowski's theorem implies combinatorial planarity. Moreover, it contains verified implementations of programs checking certificates for planarity (i.e., a combinatorial map) or non-planarity (i.e., a Kuratowski subgraph).
BSD License

Depends On

Topics

Related Entries

Theories

Cite

×
@article{Planarity_Certificates-AFP,
  author  = {Lars Noschinski},
  title   = {Planarity Certificates},
  journal = {Archive of Formal Proofs},
  month   = November,
  year    = 2015,
  note    = {\url{http://isa-afp.org/entries/Planarity_Certificates.html},
            Formal proof development},
  ISSN    = {2150-914x},
}
Download