Drawing graphs in two layers. (English) Zbl 0819.68086

Summary: Let \(G= (U, L, E)\) be a bipartite graph with vertex set \(U\cup L\) and edge set \(E\subseteq U\times L\). A typical convention for drawing \(G\) is to put the vertices of \(U\) on the line and the vertices of \(L\) on a separate, parallel line and then to represent edges by placing open straight line segments between the vertices that determine them. In this convention, a drawing is biplanar if edges do not cross, and a subgraph of \(G\) is biplanar if it has a biplanar drawing. The main results of this paper are the following: (1) it is NP-complete to determine whether \(G\) has a biplanar subgraph with at least \(K\) edges; (2) it is also NP- complete to determine whether \(G\) has such a subgraph when the position for the vertices in either \(U\) or \(L\) are specified; (3) when the position of the vertices in both \(U\) and \(L\) are specified, the problem can be solved in polynomial time by transformation to the longest ascending subsequence problem.


68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C10 Planar graphs; geometric and topological aspects of graph theory


bipartite graph
Full Text: DOI


[1] Angluin, D.; Valiant, L. G., Fast probabilistic algorithms for Hamilton circuits and matchings, J. Comput. System Sci., 18, 155-193 (1979) · Zbl 0437.05040
[2] Atallah, M. J.; Kosaraju, S. R., An efficient algorithm for maxdominance with applications, Algorithmica, 4, 221-236 (1989) · Zbl 0664.68070
[3] Dijkstra, E. W., Some beautiful arguments using mathematical induction, Acta Inform., 13, 1-8 (1980) · Zbl 0435.68055
[4] Eades, P.; Kelly, D., Heuristics for reducing crossings in 2-layered networks, Ars Combin., 21A, 89-98 (1986) · Zbl 0598.05032
[5] Eades, P.; Lin, X., How to draw a directed graph, (Proc. 1989 IEEE Workshop on Visual Languages (1989), IEEE Computer Soc. Press: IEEE Computer Soc. Press Silver Spring, MD), 13-17
[6] Eades, P.; Mckay, B. D.; Wormald, N. C., On an edge crossing problem, (Proc. 9th Australian Computer Science Conf. (1986), Australian National University), 327-334
[7] Eades, P.; Sugiyama, K., How to draw a directed graph, J. Inform. Process., 13, 424-437 (1990) · Zbl 0764.68114
[8] Eades, P.; Tamassia, R., Algorithms for drawing graphs: an annotated bibliography, (Tech. Report CS-89-09 (1989), Department of Computer Science, Brown University) · Zbl 0804.68001
[9] Eades, P.; Wormald, N. C., Edge crossings in drawings of bipartite graphs, (Tech. Report 108 (1989), Department of Computer Science, University of Queensland) · Zbl 0804.68107
[10] Gansner, E. R.; North, S. C.; Vo, K. P., DAG — a program that draws directed graphs, Software Practice Experience, 18, 1047-1062 (1988) · Zbl 0661.68067
[11] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[12] Garey, M. R.; Johnson, D. S., Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods, 4, 312-316 (1983) · Zbl 0536.05016
[13] Gschwind, D. J.; Murtagh, T. P., A recursive algorithm for drawing hierarchical directed graphs, (Tech. Report CS-89-02 (1989), Williams College: Williams College Williamstown, MA)
[14] Karger, D.; Motwani, R.; Ramkumar, G. D.S., On approximating the longest path in a graph, (Dehne, F.; Sack, J.-R.; Santoro, N.; Whitesides, S., Algorithms and Data Structures (Proc. 3rd Workshop on Algorithms and Data Structures WADS’93). Algorithms and Data Structures (Proc. 3rd Workshop on Algorithms and Data Structures WADS’93), Lecture Notes in Computer Science, Vol. 709 (1993), Springer: Springer Berlin), 421-432 · Zbl 0876.68083
[15] Kelly, D., A view to graph layout problems, (Masters Thesis (1987), Department of Computer Science, University of Queensland)
[16] Lou, R. D.; Sarrafzadeh, M.; Lee, D. T., An optimal algorithm for the maximum two-chain problem, SODA 90, Proc. 1st Ann. ACM-SIAM Symp. on Discrete Algorithms, 149-158 (1990), San Francisco · Zbl 0800.68473
[17] Makinen, E., Experiments in drawing 2-level hierarchical graphs, (Tech. Report A-1988-1 (1988), Department of Computer Science, University of Tampere) · Zbl 0723.68083
[18] Messinger, E., Automatic layout of large directed graphs, (Tech. Report 87-07-08 (1987), Department of Computer Science, University of Washington)
[19] Orlowski, M.; Pachter, M., An algorithm for the determination of a longest increasing subsequence in a sequence, Comput. Math. Appl., 17, 1073-1075 (1989) · Zbl 0671.05002
[20] Paulich, F. N.; Tichy, W. F., EDGE: an extendible directed graph editor, Software Practice Experience, 20, 63-88 (1990)
[21] Rowe, L. A.; Davis, M.; Messinger, E.; Meyer, C.; Spirakis, C.; Tuan, A., A browser for directed graphs, Software Practice Experience, 17, 61-76 (1987)
[22] Sechen, C., VLSI Placement and Global Routing Using Simulated Annealing (1988), Kluwer: Kluwer Dordrecht
[23] Sugiyama, K., A cognitive approach for graph drawing, Cybernet. Systems, 18, 447-488 (1987)
[24] Sugiyama, K.; Misue, K., Visualizing structural information: hierarchical drawing of a compound digraph, (Tech. Report 86 (1989), Fujitsu Limited: Fujitsu Limited Numazu Shizuoka Japan), IIAS-SIS
[25] Sugiyama, K.; Tagawa, S.; Toda, M., Methods for visual understanding of hierarchical system structures, IEEE Trans. Systems Man Cybernet, SMC-11, 109-125 (1981)
[26] Ullman, J. D., Computational Aspects of VLSI (1984), Computer Science Press: Computer Science Press Rockville, MD · Zbl 0539.68021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.