skip to main content

CS 598 JGE - Algorithms for 1D Structures

Fall 2020

Algorithms for 1D StructuresCS598JGE67897E641100 - 1215 T R    Jeff G Erickson

Official Description

Subject offerings of new and developing areas of knowledge in computer science intended to augment the existing curriculum. See Class Schedule or departmental course information for topics and prerequisites. Course Information: May be repeated in the same or separate terms if topics vary.

Section Description

Algorithms for 1D Structures. Entirely online with some mix of asynchronous and synchronous components that may vary over the semester and based on needs of students and instructor. This course will be a broad introduction to algorithms for curves and graphs embedded in the plane or other surfaces. Algorithmic questions about curves have been a driving force in topology since its inception more than a century ago. Planar and near-planar graphs have long been fertile ground for algorithms research, both because they naturally model many classes of networks that arise in practice, and because they admit simpler and faster algorithms than more general graphs. There is a rich interplay between these two domains, drawing on a common pool of techniques from geometry, topology, and combinatorics. Potential topics include topological graph theory; homotopy, homology, and other topological invariants; specialized algorithms for shortest paths, maximum flows, and minimum cuts; efficient a

Last updated