This thesis presents several algorithms that update the vertex separation of a tree after the tree is modified; the vertex separation of a graph measures the largest number of vertices to the left of and including a vertex that are adjacent to vertices to the right of the vertex, when the vertices in the graph are arranged in the best possible linear ordering. Vertex separation was introduced by Lipton and Tarjan and has since been applied mainly in VLSI design. The tree is modified by either attaching another tree or removing a subtree. The first algorithm handles the special case when another tree is attached to the root, and the second algorithm updates the vertex separation after a subtree of the root is removed. The last two algorithms solve the more general problem when subtrees are attached to or removed from arbitrary vertices; they have good running time performance only in the amortized sense. The running time of all our algorithms is sublinear in the number of vertices in the tree, assuming certain information is precomputed for the tree. This improves upon current algorithms by Skodinis and Ellis, Sudborough, and Turner, both of which have linear running time for this problem. Lower and upper bounds on the vertex separation of a general graph are also derived. Furthermore, analogous bounds are presented for the cutwidth of a general graph, where the cutwidth of a graph equals the maximum number of edges that cross over a vertex, when the vertices in the graph are arranged in the best possible linear ordering.

This thesis presents several algorithms that update the vertex separation of a tree after the tree is modified; the vertex separation of a graph measures the largest number of vertices to the left of and including a vertex that are adjacent to vertices to the right of the vertex, when the vertices in the graph are arranged in the best possible linear ordering. Vertex separation was introduced by Lipton and Tarjan and has since been applied mainly in VLSI design. The tree is modified by either attaching another tree or removing a subtree. The first algorithm handles the special case when another tree is attached to the root, and the second algorithm updates the vertex separation after a subtree of the root is removed. The last two algorithms solve the more general problem when subtrees are attached to or removed from arbitrary vertices; they have good running time performance only in the amortized sense. The running time of all our algorithms is sublinear in the number of vertices in the tree, assuming certain information is precomputed for the tree. This improves upon current algorithms by Skodinis and Ellis, Sudborough, and Turner, both of which have linear running time for this problem. Lower and upper bounds on the vertex separation of a general graph are also derived. Furthermore, analogous bounds are presented for the cutwidth of a general graph, where the cutwidth of a graph equals the maximum number of edges that cross over a vertex, when the vertices in the graph are arranged in the best possible linear ordering.

This thesis presents the first sub-quadratic circle graph recognition algorithm, and develops improved algorithms for two important hierarchical decomposition schemes: modular decomposition and split decomposition. The modular decomposition algorithm results from unifying two different approaches previously employed to solve the problem: divide-and-conquer and factorizing permutations. It runs in linear-time, and is straightforward in its understanding, correctness, and implementation. It merely requires a collection of trees and simple traversals of these trees. The split-decomposition algorithm is similar in being straightforward in its understanding and correctness. An efficient implementation of the algorithm is described that uses the union-find data-structure. A novel charging argument is used to prove the running-time. The algorithm is the first to use the recent reformulation of split decomposition in terms of graph-labelled trees. This facilitates its extension to circle graph recognition. In particular, it allows us to efficiently apply a new lexicographic breadth-first search characterization of circle graphs developed in the thesis. Lexicographic breadth-first search is additionally responsible for the efficiency of the split decomposition algorithm, and contributes to the simplicity of the modular decomposition algorithm.

This thesis presents the first sub-quadratic circle graph recognition algorithm, and develops improved algorithms for two important hierarchical decomposition schemes: modular decomposition and split decomposition. The modular decomposition algorithm results from unifying two different approaches previously employed to solve the problem: divide-and-conquer and factorizing permutations. It runs in linear-time, and is straightforward in its understanding, correctness, and implementation. It merely requires a collection of trees and simple traversals of these trees. The split-decomposition algorithm is similar in being straightforward in its understanding and correctness. An efficient implementation of the algorithm is described that uses the union-find data-structure. A novel charging argument is used to prove the running-time. The algorithm is the first to use the recent reformulation of split decomposition in terms of graph-labelled trees. This facilitates its extension to circle graph recognition. In particular, it allows us to efficiently apply a new lexicographic breadth-first search characterization of circle graphs developed in the thesis. Lexicographic breadth-first search is additionally responsible for the efficiency of the split decomposition algorithm, and contributes to the simplicity of the modular decomposition algorithm.