On the Computational Complexity of Upward and Rectilinear Planarity Testing

Garg, Ashim and Tamassia, Roberto (1995) On the Computational Complexity of Upward and Rectilinear Planarity Testing. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 286-297 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_384).

Full text not available from this repository.

Abstract

A directed graph is upward planar if it can be drawn in the plane such that every edge is a monotonically increasing curve in the vertical direction, and no two edges cross. An undirected graph is rectilinear planar if it can be drawn in the plane such that every edge is a horizontal or vertical segment, and no two edges cross. Testing upward planarity and rectilinear planarity are fundamental problems in the effective visualization of various graph and network structures. In this paper we show that upward planarity testing and rectilinear planarity testing are NP-complete problems. We also show that it is NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an o(n^{1-\epsilon}) error, for any \epsilon \geq 0.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_384
Classifications:G Algorithms and Complexity > G.770 Planarity Testing
ID Code:194

Repository Staff Only: item control page

References

P. Bertolazzi and G. Di Battista. On upward drawing testing of triconnected digraphs. In Proc. 7th Annu. ACM Sympos. Comput. Geom., pp. 272-280, 1991.

P. Bertolazzi, G. Di Battista, G. Liotta, and C. Mannino. Upward drawings of triconnected digraphs. Algorithmica, to appear.

P. Bertolazzi, G. Di Battista, C. Mannino, and R. Tamassia. Optimal upward planarity testing of single-source digraphs. In Proc. European Symposium on Algorithmics, LNCS vol. 726, pp. 37-48. Springer-Verlag, 1993.

T. Biedl and G. Kant. A better heuristic for orthogonal graph drawings. In Proc. European Symp. on Algorithms, LNCS vol. 855, pp. 24-35. Springer-Verlag 1994.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Algorithms for drawing graphs: an annotated bibliography. Comput. Geom. Theory Appl., to appear. Preprint available by ftp from ftp. cs. brown.edu:pub/papers/compgeo/.

G. Di Battista, G. Liotta, and F. Vargiu. Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs. In Proc. Workshop Algorithms Data Struct., LNCS vol. 709, pp. 151-162. Springer-Verlag, 1993.

G. Di Battista, W.P. Liu, and I. Rival. Bipartite graphs upward drawings and planarity. Inform. Process. Lett., 36:317-322, 1990.

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

S. Even and G. Granot. Rectilinear planar drawings with few bends in each edge. Technical Report 797, Computer Science Dept., Technion", 1994.

M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York, NY, 1979.

A. Garg and R. Tamassia. On the computational complexity of upward and rectilinear planarity testing. Report CS-94-10, Comput. Sci. Dept., Brown Univ., Providence, RI, 1994.

M.D. Hutton and A. Lubiw. Upward planar drawing of single source acyclic digraphs. In Proc. 2nd ACM-SIAM Sympos. Discrete Algorithms, pp. 203-211, 1991.

G. Kant. Drawing planar graphs using the lmc-ordering. In Proc. 33th Annu. IEEE Sympos. Found. Comput. Sci., pp. 101-110, 1992.

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

D. Kelly and I. Rival. Planar lattices. Canad. J. Math., 27(3):636-665, 1975.

A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In Theory of Graphs: Internat. Symposium (Rome 1966), pp. 215-232, New York, 1967. Gordon and Breach.

Y. Liu, P. Marchioro, and R. Petreschi. A single bend embedding algorithm for cubic graphs. Manuscript, 1994.

Y. Liu, P. Marchioro, R. Petreschi, and B. Simeone. Theoretical results on at most 1-bend embeddability of graphs. Technical report, Dipartimento di Statistica, Univ. di Roma "La Sapienza", 1990.

Y. Liu, A. Morgana, and B. Simeone. General theoretical results on rectilinear embeddability of graphs. Acta Math. Appl. Sinica, 7:187-192, 1991.

Y. Liu, A. Morgana, and B. Simeone. A linear algorithm for 3-bend embeddings of planar graphs in the grid. Manuscript, 1993.

A. Papakostas. Upward planarity testing of outerplanar dags. In Proc. Graph Drawing '94, 1994.

C. Platt. Planar lattices and planar graphs. J. Combin. Theory Ser. B, 21:30-39, 1976.

I. Rival. Reading, drawing, and order. In I. G. Rosenberg and G. Sabidussi, editors, Algebras and Orders, pp. 359-404. Kluwer Academic Publishers, 1993.

Y. Shiloach. Arrangements of Planar Graphs on the Planar Lattice. PhD thesis, Weizmann Institute of Science, 1976.

J.A. Storer. On minimal node-cost planar embeddings. Networks, 14:181-212, 1984.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421-444, 1987.

R. Tamassia and I.G. Tollis. Planar grid embedding in linear time. IEEE Trans. on Circuits and Systems, CAS-36(9):1230-1234, 1989.

C. Thomassen. Planar acyclic oriented graphs. Order, 5(4):349-361, 1989.

L. Valiant. Universality considerations in VLSI circuits. IEEE Trans. Comput., C-30(2):135, 1981.

G. Vijayan and A. Wigderson. Rectilinear graphs and their embeddings. SIAM J. Comput., 14:355-372, 1985.