Abstract: The concept of systematically searching a graph was first developed over a century ago. In the late 60s and 70s, considerable attention was given to the algorithmic importance of the two most obvious search strategies, namely Depth First Search and Breadth First Search. In 1976 Rose, Tarjan and Lueker developed a variation of Breadth First Search called Lexicographic Breadth First Search (LBFS). They showed that LBFS yields a very simple linear time algorithm for recognizing chordal graphs (graphs without induced cycles of size greater than 3). Although little work was done on LBFS for the following 15 years, recently it has received a great deal of attention. In particular it has been shown that LBFS can be used both alone and in multiple sweeps to recognize various restricted families of graphs as well as to determine specific properties on such graphs.
In this talk we survey these results and indicate open problems in the area.
Abstract:
Dynamic Geometry deals with the kind of problems that arise in
interactive geometry software: Given a construction (points, lines,
conics linked by operations like "point" of intersection of two lines,
connecting line of two points, perpendicular line to another line
through a point and others) we would like to move "free" elements and
update the construction accordingly. The main problem here arises from
ambiguities in the operations: A line and a circle have up to two
intersections, two conics intersect in up to four points, two lines
have two angular bisectors,... After a change of parameters the two
or four solutions of an equation system must be assigned to the right
point. In this talk I will show that there is no easy way to give an
algorithm that updates constructions in a
The theory is implemented in the Interactive Geometry Software Cinderella. More information about Cinderella is available at http://www.cinderella.de.