Master's thesis: A Parameterized Algorithm for Upward Planarity Testing of Biconnected Graphs

final version: [ PostScript (364kB) ] [ PDF (490kB) ] [ DjVu (605kB) ] Creative Commons BY-ND 3.0 License

Presentation: 11:00am, May 6, 2003, DC 1331 [ slides (289kB PDF) ]

Abstract

We can visualize a graph by producing a geometric representation of the graph in which each node is represented by a single point on the plane, and each edge is represented by a curve that connects its two endpoints.

Directed graphs are often used to model hierarchical structures; in order to visualize the hierarchy represented by such a graph, it is desirable that a drawing of the graph reflects this hierarchy. This can be achieved by drawing all the edges in the graph such that they all point in an upwards direction. A graph that has a drawing in which all edges point in an upwards direction and in which no edges cross is known as an upward planar graph. Unfortunately, testing if a graph is upward planar is NP-complete.

Parameterized complexity is a technique used to find efficient algorithms for hard problems, and in particular, NP-complete problems. The main idea is that the complexity of an algorithm can be constrained, for the most part, to a parameter that describes some aspect of the problem. If the parameter is fixed, the algorithm will run in polynomial time.

In this thesis, we investigate contracting an edge in an upward planar graph that has a specified embedding, and show that we can determine whether or not the resulting embedding is upward planar given the orientation of the clockwise and counterclockwise neighbours of the given edge. Using this result, we then show that under certain conditions, we can join two upward planar graphs at a vertex and obtain a new upward planar graph. These two results expand on work done by Hutton and Lubiw [HL96].

Finally, we show that a biconnected graph has at most k!8k-1 planar embeddings, where k is the number of triconnected components. By using an algorithm by Bertolazzi et al. [BDBMT98] that tests whether a given embedding is upward planar, we obtain a parameterized algorithm, where the parameter is the number of triconnected components, for testing the upward planarity of a biconnected graph. This algorithm runs in O(k!8kn3) time.

Contents

  1. Introduction
    1. Upward planarity
      1. Related problems
      2. Algorithms on special classes of graphs
      3. Combinatorial characterizations
    2. Parameterized complexity
    3. Thesis outline
  2. Definitions
    1. Graphs
    2. Topology
    3. Graph drawing
  3. Technical lemmas
    1. Transformations
    2. Edge contraction and planar embeddings
    3. Edge reversal
  4. Edge contraction and upward planarity
  5. Joining subgraphs
  6. Biconnected graphs
  7. Conclusions and future work

Bibliography