Table of Content

Topics in Discrete Mathematics (Diskrete Strukturen III)

Sommersemester 2026
Stefan Felsner

1. Vorlesung, 14.04.2025

        Order Theory
           Basics of order theory
               graphs related to a poset
               chains and antichains   
           Linear extensions and dimension
               linear extensions exist
               realizer and dimension
               dimension and embeddings - Ore definition
               dimension of Boolean lattice
                  standard examples

           2-dimensional orders
               conjugate order
               non-separating linear extension
           Transitive orientation of graphs
               forcing relation
           Incidence orders of graphs and dimension
               characterizing dimension 2

        Dimension of incidence orders and dimension of graphs
           critical pairs - comparing the two dimension concepts for graphs
           dimension of the complete graph
              HM-antichains in the Boolean lattice
        Dimension of planar graphs
           dim(G) at most 3 implies planarity

           Schnyder's dimension Theorem
              Schnyder woods - definition and existence
              paths and regions of a vertex
              containment orders of i-regions
              the 3-realizer

   
        Dimension of polytopes
           3-polytopes   
           the lower bound
           cyclic polytopes
        Grid drawings of planar graphs
           counting faces in regions
           the empty triangle of a face

        Orthogonal surfaces
           the OS obtained from face counting 
           OS and the Schnyder dimension theorem   
        Schnyder woods of 3-connected planar graphs
           primal-dual Schnyder woods

       Intersection and contact representations of graphs
         Examples: segment intersection graphs, triangle contact graphs
           Circle contact representations (Koebe's Thm.)
         Triangle contact representations from Schnyder woods
         Homothetic triangle contact representations
           Existence and 'monster packing'
           Connection with orthogonal surfaces
           Algorithm using Schnyder woods, linear equations and flips

       The dimension of planar maps
          Brightwell Trotter Theorem
             The split of a poset and the in-place split
             Dimension of grid intersection graphs (GIGs)
             Bipartite planar graphs admit segment contact representations