### 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).

### License

BSD License

### Topics

- Mathematics/Graph theory

### Session Planarity_Certificates

- Lib
- OptionMonad
- NonDetMonad
- NonDetMonadLemmas
- OptionMonadND
- WP
- OptionMonadWP
- Graph_Genus
- List_Aux
- Executable_Permutations
- Digraph_Map_Impl
- Planar_Complete
- Reachablen
- Permutations_2
- Planar_Subdivision
- Planar_Subgraph
- Kuratowski_Combinatorial
- Simpl_Anno
- Check_Non_Planarity_Impl
- Check_Non_Planarity_Verification
- AutoCorres_Misc
- Setup_AutoCorres
- Check_Planarity_Verification
- Planarity_Certificates

### Depends on

- Generating Cases from Labeled Subgoals
- Graph Theory
- List Index
- A Sequential Imperative Programming Language Syntax, Semantics, Hoare Logics and Verification Environment
- Executable Transitive Closures of Finite Relations

## Cite

×

Planarity_Certificates-AFP

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

Download

## Download

× Download latest

Older releases:

- Sep 13, 2023 : Isabelle2023
- Oct 27, 2022 : Isabelle2022
- Dec 14, 2021 : Isabelle2021-1
- Feb 23, 2021 : Isabelle2021
- Apr 20, 2020 : Isabelle2020
- Jun 11, 2019 : Isabelle2019
- Aug 16, 2018 : Isabelle2018
- Oct 10, 2017 : Isabelle2017
- Dec 17, 2016 : Isabelle2016-1
- Feb 22, 2016 : Isabelle2016