A Parameterized Algorithm for Upward Planarity Testing of Biconnected Graphs

Computer Science;algorithms;graph theory;graph drawing;parameterized complexity;upward planarity

Chan, Hubert

University of Waterloo

关键词: Computer Science;    algorithms;    graph theory;    graph drawing;    parameterized complexity;    upward planarity;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/1090/1/hy3chan2003.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

We can visualize a graph by producing a geometric representation of thegraph in which each node is represented by a single point on the plane,and each edge is represented by a curve that connects its twoendpoints. Directed graphs are often used to model hierarchical structures; inorder to visualize the hierarchy represented by such a graph, it isdesirable that a drawing of the graph reflects this hierarchy.This canbe achieved by drawing all the edges in the graph such that they allpoint in an upwards direction.A graph that has a drawing in which alledges point in an upwards direction and in which no edges cross is knownas an upward planar graph.Unfortunately, testing if a graph is upwardplanar is NP-complete. Parameterized complexity is a technique used to find efficientalgorithms 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 theproblem.If the parameter is fixed, the algorithm will run in polynomialtime. In this thesis, we investigate contracting an edge in an upward planargraph that has a specified embedding, and show that we can determinewhether or not the resulting embedding is upward planar given theorientation of the clockwise and counterclockwise neighbours of the givenedge.Using this result, we then show that under certain conditions, wecan join two upward planar graphs at a vertex and obtain a new upwardplanar graph.These two results expand on work done by Hutton andLubiw. Finally, we show that a biconnected graph has at most k!8^k-1 planarembeddings, where k is the number of triconnected components.By usingan algorithm by Bertolazzi et al. thattests whether a given embedding is upward planar, we obtain aparameterized algorithm, where the parameter is the number oftriconnected components, for testing the upward planarity of abiconnected graph.This algorithm runs in O(k!8^kn³) time.