Information Technology Reference
In-Depth Information
Bitonic st -orderings of Biconnected Planar Graphs
Martin Gronemann
Institutfur Informatik, Universitat zu Koln, Germany
gronemann@informatik.uni-koeln.de
Abstract. Vertex orderings play an important role in the designofgraph drawing
algorithms. Compared to canonical orderings, st -orderings lack a certain prop-
erty that is required by many drawing methods. In this paper, we propose a new
type of st -ordering for biconnected planar graphs that relates the ordering to the
embedding. We describe a linear-time algorithm to obtain such an ordering and
demonstrate its capabilities with two applications.
1
Introduction
Being afundamental part of incremental drawing procedures, various types of orderings
have been developed and improved over the years. De Fraysseix, Pach and Pollack [3]
introduced the canonical ordering to create straight-line drawings of maximal planar
graphs. Afterwards, Kant [10] extended this concept to the triconnected case. Obtain-
able in linear-time, both have been usedinthegraph drawing literature extensively.
A few attempts have been made to generalize them to the biconnected case by relax-
ing their properties [7,9]. However, an alternative that in nature works for biconnected
graphs and that can be computed in linear time, are st -orderings [6]. In the field of
graph drawing, they have been used in several methods, reaching from the construction
of visibility representations to drawings of non-planar graphs, see e.g. [4,12]. Although
canonical and st -orderings share some properties in the planar case, it seems that they
are usually not used in the same context.
In the following,weinvestigate these differences in more detail, especially one prop-
erty of canonical orderingsthatisused implicitly in many drawing algorithms. Consider
the successors of a single vertex in the clockwise ordering as implied by the embed-
ding. Then their ranks in the canonical ordering form an increasing and then decreasing
sequence, i.e., a bitonic sequence. Common st -orderings do not necessarily have this
property, rendering them unsuitable for some applications.
We c ounteract by introducing a new type of st -ordering for biconnected planar
graphs: the bitonic st -ordering ,an st -ordering in which the successors of every ver-
tex appear in the aforementioned pattern. We show that every biconnected planar graph
admits such an ordering. The proof is constructive and yields a linear-time algorithm
that computes the ordering and a corresponding embedding. For the case where a fixed
embedding is given, we prove that one cannot always find a bitonic st -order. In order to
further support our idea, we briefly describe two applications. In the first one, we extend
the straight-line algorithm of de Fraysseix, Pach and Pollack [3] to bitonic st -orderings.
In the second one, we describe how to obtain a special visibility representation and then
transform it into a rectilinear T-shaped polygon contact representation.
Search WWH ::




Custom Search