Combinatorial Characterization of Upward Planarity

Abstract

We give a combinatorial characterization of upward planar graphs in terms of upward planar orders, which are special linear extensions of edge posets.

Keywords

Upward planar graph / Planar st graph / Upward planar order

References

[1] Bertolazzi, G., Di Battista, G.: On upward drawings of triconnected digraphs. In: Proceedings of the 7th Annual Symposium on Computational Geometry, pp. 272–280 (1991)

[2] Bertolazzi G, Di Battista G, Liotta G, Mannino C. Upward drawings of triconnected digraphs. Algorithmica. 1994, 12 476-497

[3] Di Battista G, Tamassia R. Algorithms for plane representations of acyclic digraphs. Theor. Comput. Sci.. 1988, 61 2–3 175-198

[4] Fáry I. On straight line representation of planar graphs. Acta. Univ. Szeged. Sect. Sci. Math.. 1948, 11 229-233

[5] Garg A, Tamassia R. Upward planarity testing. Order. 1995, 12 2 109-133

[6] Hu, S., Lu, X., Ye, Y.: A graphical calculus for semi-groupal categories. Appl. Categ. Struct. arXiv:1604.07276 (to appear)

[7] Joyal A, Street R. The geometry of tensor calculus. I. Adv. Math.. 1991, 88 1 55-112

[8] Kelly D. Fundamentals of planar ordered sets. Discrete Math.. 1987, 63 2 197-216

[9] Rival I. Rosenberg IG, Sabidussi G. Reading, drawing, and order. Algebras and Orders, NATO ASI Series (Series C: Mathematical and Physical Sciences). 1993 Dordrecht: Springer. 359-404

[10] Trotter WT. Alavi Y, Lick DR. Order preserving embeddings of aographs. Theory and Applications of Graphs. Lecture Notes in Mathematics. 1978 Berlin: Springer. 572-579

[11] Tamassia R, Tollis IG. A unified approach to visibility representations of planar graphs. Discrete Comput. Geom.. 1986, 1 4 321-341

[12] Wagner K. Bemerkung zum Vierfarbenproblem. Jber. Deutsch. Math. Verein.. 1936, 46 26-32

Funding

NSFC(No.11431010)

the Fundamental Research Funds for the Central Universities