Περιγραφή θέματος

  • Γενικά

  • Περιεχόμενα μαθήματος

      • From applications to graphs

      • Review of fundamental graph algorithms

      • Optimization algorithms for graphs:

        • flow

        • matchings

        • connectivity

        • routing

        • Euler tours

        • Hamiltonian tours, etc.

      • Planar Graphs:

        • Dual Graphs

        • Planar Orientations

        • Planar Representations

        • Visibility Representations

      • Graph Visualization:

        • Graphs and Their Drawings

        • Paradigms for Graph Drawing

        • Divide and Conquer Techniques for Drawing Trees and Series-Parallel graphs

        • Flow and Orthogonal Drawings

        • Flow and Upward Planarity

        • Incremental Construction

        • Nonplanar Orientations

        • Layered Drawings of Digraphs

        • Force-Directed Methods

        • Circular Drawings of Graphs

        • Lower Bounds

        • Automatic Label Placement

      • Other Topics.

  • Σημειώσεις προερχόμενες από εργασίες φοιτητών

    • Depth first search & Directed Acyclic Graphs Αρχείο

      Depth First Search (DFS), DFS algorithm, parenthesis theorem, edge classification, directed acyclic graphs, topological numberings and sortings, single source shortest path, single source longest path, Bellman Ford algorithm, all pairs shortest paths, Program Evaluation and Review Technique (PERT).

    • Planar orientation Αρχείο

      Numbering directed acyclic graphs, properties of planar acyclic digraphs, tessellation representations, plane tessellation representation, sphere tessellation representation, visibility representations, constrained visibility representation, polyline drawings.

    • st-Orientation Αρχείο

      st-orientation / bipolar orientation, Even - Tarjan algorithm, a streamlined depth-first search algorithm, an algorithm for direct st-orientation computation - STN algorithm.

    • Circular drawing Αρχείο

      Circular graph drawing, Circular Drawing on a single embedding circle, Circular algorithm, circular drawings of nonbiconnected graphs on multiple embedding circles, circular-with radial algorithm, circular drawing of user defined groups on multiple embedding circles.

    • Euler & Hamilton circuits Αρχείο

      Euler paths and circuits, the Konisberg Bridge problem, Euler's theorem, Fleury's algorithm, Eulerization and semi-Eulerization, Hamilton paths and circuits, algorithm for finding a Hamilton circuit, Hamilton paths and circuits in directed graphs, Travelling salesman problem.