Applications of Parameterized st-Orientations in Graph Drawing Algorithms

TitleApplications of Parameterized st-Orientations in Graph Drawing Algorithms
Publication TypeBook Chapters
Year of Publication2006
AuthorsPapamanthou C, Tollis IG
EditorHealy P, Nikolov NS
Book TitleGraph Drawing
Series TitleLecture Notes in Computer Science
Pagination355 - 367
PublisherSpringer Berlin Heidelberg
ISBN Number978-3-540-31425-7, 978-3-540-31667-1
KeywordsAlgorithm Analysis and Problem Complexity, Computer Graphics, Data structures, Discrete Mathematics in Computer Science

Many graph drawing algorithms use st-numberings (st-orien-tations or bipolar orientations) as a first step. An st-numbering of a biconnected undirected graph defines a directed graph with no cycles, one single source s and one single sink t. As there exist exponentially many st-numberings that correspond to a certain undirected graph G, using different st-numberings in various graph drawing algorithms can result in aesthetically different drawings with different area bounds. In this paper, we present results concerning new algorithms for parameterized st-orientations, their impact on graph drawing algorithms and especially in visibility representations.