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, Karlsruhe, Germany , 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
ID Code:797

Repository Staff Only: item control page

References

I. Barany and G. Rote, Strictly convex drawings of planar graphs, 2005. arXiv:cs.CG/0507030.

N. Bonichon, S. Felsner, and M. Mosbah, Convex drawings of 3-connected planar graphs, in Graph Drawing (Proc. GD '04), vol. 3383 of Lecture Notes in Comput. Sci., 2004, pp. 60-70.

G. Brightwell and W. T. Trotter, The order dimension of convex polytopes, SIAM J. Discrete Math., 6 (1993), pp. 230-245.

G. Brightwell and W. T. Trotter, The order dimension of planar maps, SIAM J. Discrete Math., 10 (1997), pp. 515-528.

G. Di Battista, R. Tamassia, and L. Vismara, Output-sensitive reporting of disjoint paths, Algorithmica, 23 (1999), pp. 302-340.

S. Felsner. http://www.math.tu-berlin.de/~felsner/Schnyder.bib.

S. Felsner, Convex drawings of planar graphs and the order dimension of 3-polytopes, Order, 18 (2001), pp. 19-37.

S. Felsner, Geodesic embeddings and planar graphs, Order, 20 (2003), pp. 135-150.

S. Felsner, Geometric Graphs and Arrangements, Vieweg Verlag, 2004.

S. Felsner and F. Zickfeld, Schnyder woods and orthogonal surfaces, 2006. http://www.math.tu-berlin.de/~felsner/swaos.pdf.

E. Fusy, D. Poulalhon, and G.Schaeffer, Dissection and trees, with applications to optimal mesh encoding and random sampling, in Proc. 16. ACM-SIAM Sympos. Discrete Algorithms, 2005, pp. 690-699.

G. Kant, Drawing planar graphs using the lmc-ordering, in Proc. 33rd IEEE Sympos. on Found. of Comp. Sci., 1992, pp. 101-110.

C. Lin, H. Lu, and I.-F. Sun, Improved compact visibility representation of planar graphs via Schnyder's realizer, SIAM J. Discrete Math., 18 (2004), pp. 19-29.

E. Miller, Planar graphs as minimal resolutions of trivariate monomial ideals, Documenta Math., 7 (2002), pp. 43-90.

W. Schnyder, Planar graphs and poset dimension, Order, 5 (1989), pp. 323-343.

W. Schnyder, Embedding planar graphs on the grid, in Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, 1990, pp. 138-148.

W. T. Trotter, Combinatorics and Partially Ordered Sets: Dimension Theory, The Johns Hopkins University Press, 1992.