Visibility representations of four-connected plane graphs with near optimal heights
Journal
Computational Geometry: Theory and Applications
Journal Volume
42
Journal Issue
9
Pages
865-872
Date Issued
2009
Author(s)
Chen, C.-Y.
Hung, Y.-F.
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 ⌈n2⌉+2⌈n- 22⌉. 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 n2. © 2009 Elsevier B.V. All rights reserved.
Type
journal article