Table of Content

Graphen, Ordnungen und Geometrie (Diskrete Strukturen III)

Sommersemester 2024
Stefan Felsner

1. Vorlesung, 16.04.2024

       Intersection graphs
         interval graphs
            α=Θ (greedy left to right independent set)
            χ=ω (greedy left to right coloring)
         unit squares Θ≤2α and χ≤2ω
         squares -- intersection graph is 4(ω-1) degenerate
            Θ≤4α and χ≤4ω-3

         rectangle intersection graphs
            the Asplund-Grünbaum bound: χ≤4ω²-3ω
         intersection graphs of pseudodiscs
            the union complexity 
            the coloring bound: χ≤19ω

         triangle-free graphs with large chromatic number
            classical constructions
            bounds on χ in terms of number of vertices
            segment intersection graphs 
              the construction of Pawlik et al.
       χ-boundedness
            examples and questions  
            circle graphs

     Coloring circle graphs
        Basics: circle and overlap graphs
           permutation graphs
        James Davies: Improved bounds for colouring circle graphs
           arxiv.org/pdf/2107.03585.pdf  
           coloring on the basis of pillars

          adding pillars to an arc
             binary tree order
          subdivided arc and color intervals - a poset
     Approximation algorithms for α
        segments stabbed by a line 

           a sqrt(α) approximation by dynamic progr.
        general segments
           divide and conquer with the median line
           levels in the recursion tree
        rectangles
           the crossing graph G

           computing a max indep set S in G
           computing a 2-maximal indep set I in S
           comparing |I| with a maximum indep set J 
      Geometric representations of planar graphs
         Drawings
           Force directed embeddings
              the energy of an embedding
              energy is strongly convex