Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights.
Journal
Graph Drawing, 16th International Symposium, GD 2008, Heraklion, Crete, Greece, September 21-24, 2008. Revised Papers
Pages
67-77
Date Issued
2008
Author(s)
Chen, Chieh-Yu
Hung, Ya-Fei
HSUEH-I LU
Abstract
A visibility representation of a graph G is to represent the nodes of G with non-overlapping horizontal line segments such that the line segments representing any two distinct adjacent nodes are vertically visible to each other. If G is a plane graph, i.e., a planar graph equipped with a planar embedding, a visibility representation of G has the additional requirement of reflecting the given planar embedding of G. For the case that G is an n-node four-connected plane graph, we give an O(n)-time algorithm to produce a visibility representation of G with height at most . To ensure that the first-order term of the upper bound is optimal, we also show an n-node four-connected plane graph G, for infinite number of n, whose visibility representations require heights at least . © 2009 Springer Berlin Heidelberg.
Type
conference paper