Planar Graph Ontology

FLOW ALGEBRA
TITLE: Planar Graph Ontology
DOMAIN: Discrete Mathematics / Graph Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/planar-graph-ontology.html
VERSION: 1.0
AUTHORSHIP: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
STATUS: Mathematical reference model; source page content not independently verified.

1. PURPOSE
Represent planarity, plane embeddings, faces, Euler's formula, planar graph constraints, dual graphs, and verifiable inference rules as typed semantic operations.

2. TYPES
Vertex := unique identifier
Edge := unordered pair of distinct vertices (simple graph)
Graph := (V:Set[Vertex], E:Set[Edge])
PlaneEmbedding := (graph:Graph, rotation_system, outer_face)
Face := boundary walk in a fixed plane embedding
Boolean := {true,false}
Natural := nonnegative integer
Certificate := embedding witness | nonplanarity witness | proof record

3. CORE ENTITIES AND RELATIONS
PlanarGraph(G) := exists embedding of G in the plane with no edge crossings except shared endpoints.
PlaneGraph(G,phi) := graph G together with a specified crossing-free plane embedding phi.
Incident(v,e) := v is an endpoint of e.
Adjacent(u,v) := {u,v} in E.
Bounds(f,e,phi) := edge e occurs on the boundary walk of face f in embedding phi.
Dual(G,phi) := graph with one vertex per face and one dual edge per primal edge; may contain loops or parallel edges.
Connected(G) := every pair of vertices is joined by a path.
Simple(G) := no loops and no parallel edges.

4. FLOW OPERATIONS
flow PLANARITY_CHECK(G:Graph) -> (Boolean,Certificate):
  validate graph representation
  run a sound planarity test
  if planar: return (true, crossing_free_embedding)
  else: return (false, Kuratowski_subdivision_or_other_valid_certificate)

flow FACE_ENUMERATION(G:Graph, phi:PlaneEmbedding) -> Set[Face]:
  require phi is a valid crossing-free embedding of G
  enumerate facial boundary walks including the outer face
  return faces

flow EULER_CHECK(G:Graph, phi:PlaneEmbedding) -> Boolean:
  require G finite and phi valid
  let n = |V|; m = |E|; f = number_of_faces(phi)
  let c = number_of_connected_components(G)
  return (n - m + f == 1 + c)

flow DUAL_CONSTRUCT(G:Graph, phi:PlaneEmbedding) -> Graph:
  require a valid plane embedding
  create one dual vertex for each face
  for each primal edge, connect its two incident faces (possibly equal)
  preserve multiplicities and loops
  return dual graph

5. FORMAL LAWS AND THEOREMS
L1: For a finite connected plane graph, |V| - |E| + |F| = 2.
L2: For a finite plane graph with c >= 1 connected components, |V| - |E| + |F| = 1 + c.
L3: For a simple planar graph with n >= 3, m <= 3n - 6.
L4: For a simple bipartite planar graph with n >= 3, m <= 2n - 4.
L5: Every finite simple planar graph has a vertex of degree at most 5.
L6: Every planar graph is 4-colourable (Four Colour Theorem).
L7: K5 and K3,3 are nonplanar.
L8: Kuratowski's theorem: a finite graph is planar iff it contains no subdivision of K5 or K3,3.
L9: Every subgraph of a planar graph is planar.
L10: Planarity is invariant under graph isomorphism.
L11: Edge contraction preserves planarity; consequently every minor of a planar graph is planar.
L12: The number and boundaries of faces depend on the chosen embedding; face counts obey Euler's formula.

6. INFERENCE RULES
R1: PLANARITY_CHECK(G)=(true,phi) => PlanarGraph(G).
R2: ValidEmbedding(G,phi) => EulerCheck(G,phi)=true.
R3: Simple(G) and |V|>=3 and |E|>3|V|-6 => not PlanarGraph(G).
R4: Simple(G) and Bipartite(G) and |V|>=3 and |E|>2|V|-4 => not PlanarGraph(G).
R5: ContainsSubdivision(G,K5) or ContainsSubdivision(G,K3,3) => not PlanarGraph(G).
R6: PlanarGraph(G) and H is a subgraph of G => PlanarGraph(H).
R7: PlanarGraph(G) and H is a minor of G => PlanarGraph(H).
R8: Isomorphic(G,H) => (PlanarGraph(G) iff PlanarGraph(H)).

7. SEMANTIC RELATIONSHIPS
PlanarGraph IS_A Graph
PlaneGraph IS_A EmbeddedGraph
PlanarGraph HAS_POSSIBLE_REPRESENTATION PlaneGraph
PlaneGraph HAS_PART Vertex
PlaneGraph HAS_PART Edge
PlaneGraph HAS_REGION Face
PlaneGraph SUPPORTS_CONSTRUCTION DualGraph
PlanarityTest PRODUCES Certificate
EulerFormula CONSTRAINS VertexCount, EdgeCount, FaceCount, ComponentCount
KuratowskiObstruction IMPLIES Nonplanarity
GraphMinor PRESERVES Planarity FROM_PARENT_TO_MINOR

8. SEMANTIC_EQUIVALENCE
"planar graph" == "graph admitting a crossing-free plane embedding"
"plane graph" != "planar graph" (a plane graph includes a fixed embedding)
"graph drawing" != "plane embedding" (a drawing may have crossings)
"dual graph" is embedding-dependent in general
"nonplanar" != "not yet shown planar"

9. VALIDATION
V1: Check endpoints belong to V and edge identifiers are well-formed.
V2: Distinguish simple graphs from multigraphs before applying edge bounds.
V3: Verify embedding rotation and facial walks; check no crossings.
V4: Apply Euler formula with the correct component count and outer face.
V5: Do not infer planarity merely because Euler's formula or edge bounds hold.
V6: Require explicit witness or trusted exact algorithm for positive planarity claims.
V7: Do not confuse geometric straight-line drawings with arbitrary topological embeddings.
V8: Preserve the chosen embedding when computing duals and faces.

10. CONFIDENCE
CONFIDENCE.formal_theorem := 1.0 when assumptions and theorem application are verified
CONFIDENCE.algorithmic_result := 1.0 only for verified exact algorithm and valid input
CONFIDENCE.heuristic_claim := calibrated estimate, never proof
CONFIDENCE.unverified_source_claim := unknown
Store evidence, assumptions, algorithm version and validation status with every result.

11. FLOW_HASH
FLOW_HASH.algorithm := SHA-256
FLOW_HASH.input := canonical_utf8(title, version, source_url, type_definitions, operations, laws, inference_rules, validation)
FLOW_HASH.value := COMPUTE_AT_INGESTION
Do not treat an uncomputed hash as a valid digest.

12. UPDATE_MODEL
UPDATE_MODEL.trigger := source_revision | mathematical_correction | schema_revision | algorithm_revision
UPDATE_MODEL.steps := retrieve_source; compare_changes; verify_formal_laws; rerun_tests; increment_version; recompute_FLOW_HASH; publish_with_provenance
UPDATE_MODEL.policy := retain_previous_versions_and_change_log

13. AI_CONSUMPTION
AI_CONSUMPTION.mode := typed_semantic_reference
AI_CONSUMPTION.tasks := classification | constraint_checking | embedding_validation | graph_reasoning | knowledge_graph_alignment
AI_CONSUMPTION.requirements := cite_theorem_assumptions; distinguish proof_from_heuristic; report_certificates; preserve_embedding_context; do_not_invent_results
AI_CONSUMPTION.output := (claim, evidence, assumptions, confidence, validation_status, provenance)

14. EXAMPLE
G := K4
|V| = 4; |E| = 6
A plane embedding has |F| = 4
Euler: 4 - 6 + 4 = 2 => valid for connected plane graph
Conclusion: K4 is planar; the Euler equality is a consistency check, not by itself a proof of planarity.

END FLOW ALGEBRA