Upward Planarity Checking: "Faces Are More than Polygons" (Extended Abstract)

Di Battista, Giuseppe and Liotta, Giuseppe (1998) Upward Planarity Checking: "Faces Are More than Polygons" (Extended Abstract). In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 72-86 (Official URL: http://dx.doi.org/1007/3-540-37623-2_6).

Full text not available from this repository.

Abstract

In this paper we look at upward planarity from a new perspective. Namely, we study the problem of checking whether a given drawing is upward planar. Our checker exploits the relationships between topology and geometry of upward planar drawings to verify the upward planarity of a significant family of drawings. The checker is simple and optimal both in terms of efficiency and in terms of degree.

Item Type:Conference Paper
Additional Information:1007/3-540-37623-2_6
Classifications:P Styles > P.840 Upward
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.540 Planar
ID Code:244

Repository Staff Only: item control page

References

P. Bertolazzi, G. Di Battista, and W. Didimo. Quasi upward planarity. Manuscript, 1998.

P. Bertolazzi, G. Di Battista, G. Liotta, and C. Mannino. Upward drawings for triconnected digraphs. Algoritmica, 6(12):476-497, 1994.

B. Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom., 6:485-524, 1991.

B. Chazelle and J. Incepri. Triangulation and shape-complexity. ACM Trans. Graph., 3(2):135-152, 1984.

O. Devillers, G. Liotta, R. Tamassia, and F. Preparata. Checking the convexity of polytopes and the planarity of subdivisions. In Algorithms and Data Structures (Proc. WADS 97), vol. 1272 of LNCS, pages 186-199, Springer-Verlag, 1997.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4:235-282, 1994.

G. Di Battista and R. Tamassia. Algorithms for plane representations of acyclic digraphs. Theoret. Comput. Sci., 61:175-198, 1988.

H. ElGindy, D. Avis, and G. T. Toussaint. Applications of a two-dimensionalhidden-line algorithm to other geometirc problem. Computing, 31:191-202, 1983.

K.R. Gabriel and R.R. Sokal. A new statistical approach to geographical analysis. Systematic Zoology. 18:54-64, 1969.

M.R. Garey, D.S. Johnson, F.P. Preparata, and R.E. Tarjan. Triangulating a simple polygon. Inform. Process. Lett., 7:175-179, 1978.

F. Harary. Graph Theory. Addison-Wesley, Reading, MA, 1972.

S. Hertel and K. Mehlhorn. Fast triangulation of simple polygons. In Proc. 4th Internat. Conference Found. Comp. Theory, vol. 158 of LNCS, pages 207-218, Springer-Verlag, 1983.

D. Kelly. Fundamentals of planar ordered sets. Discrete Math., 63:197-216, 1987.

G. Liotta, F.P. Preparata, and R. Tamassia. Robust proximity queries: an illustration of degree-driven algorithm design. SIAM J. Comput. to appear.

G. Liotta, F.P. Preparata, and R. Tamassia. Robust proximity queries: an illustration of degree-driven algorithm design. In proc. 13th Annu. ACM Symp. Comput. Geom., pages 156-165,1997.

K. Mehlhorn and S. Näher. Checkin Geometric Structures, Dec. 1996. Manual.

K. Mehlhorn, S. Näher, T. Schilz, S. Schirra, M. Seel, R. Seidel, and C. Uhrig. Checkin geometric programs or verification of geometric structures. In Proc. 12th Annu. ACM Symp. Comp. Geom., pages 159-165, 1996.

K. Mehlhorn, S. Näher, T. Schilz, S. Schirra, M. Seel, R. Seidel, and C. Uhrig. Checkin geometric programs or verification of geometric structures. Manuscript, 1997.

Franco P. Preparata and Michael I. Shamos. Computational geometry: an introduction. Springer-Verlag, New-York, 1985.

G. Toussaint. Efficient triangulation of simple polygons. Visual Comput., 7:280-295, 1991.

G. Toussaint. The relative neighborhood graph of a finite planar set. Pattern Recognition, 12:261-268, 1980.