Schnyder Woods and Orthogonal Surfaces

Felsner, Stefan and Zickfeld, Florian (2007) Schnyder Woods and Orthogonal Surfaces. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006 , pp. 417-429(Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_40).

Full text not available from this repository.

Abstract

In this paper we study connections between Schnyder woods and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and dimension theory. Orthogonal surfaces explain the connections between these seemingly unrelated notions. We use these connections for an intuitive proof of the Brightwell-Trotter Theorem which says that the face lattice of a 3-polytope minus one face has dimension three. Our proof yields a companion linear time algorithm for the construction of the three linear orders that realize the face lattice. Coplanar orthogonal surfaces are in correspondance with a large class of convex straight line drawings of 3-connected planar graphs. We show that Schnyder's face counting approach with weighted faces can be used to construct all coplanar orthogonal surfaces and hence the corresponding drawings. Appropriate weights are computable in linear time.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-70904-6_40
Classifications: M Methods > M.800 Topology-shape-metrics
M Methods > M.600 Planar
P Styles > P.720 Straight-line
P Styles > P.600 Poly-line
URI: http://gdea.informatik.uni-koeln.de/id/eprint/797

Actions (login required)

View Item View Item