# zbMATH — the first resource for mathematics

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.

##### MSC:
 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:
##### References:
  Angluin, D.; Valiant, L.G., Fast probabilistic algorithms for Hamilton circuits and matchings, J. comput. system sci., 18, 155-193, (1979) · Zbl 0437.05040  Atallah, M.J.; Kosaraju, S.R., An efficient algorithm for maxdominance with applications, Algorithmica, 4, 221-236, (1989) · Zbl 0664.68070  Dijkstra, E.W., Some beautiful arguments using mathematical induction, Acta inform., 13, 1-8, (1980) · Zbl 0435.68055  Eades, P.; Kelly, D., Heuristics for reducing crossings in 2-layered networks, Ars combin., 21A, 89-98, (1986) · Zbl 0598.05032  Eades, P.; Lin, X., How to draw a directed graph, (), 13-17  Eades, P.; Mckay, B.D.; Wormald, N.C., On an edge crossing problem, (), 327-334  Eades, P.; Sugiyama, K., How to draw a directed graph, J. inform. process., 13, 424-437, (1990) · Zbl 0764.68114  Eades, P.; Tamassia, R., Algorithms for drawing graphs: an annotated bibliography, () · Zbl 0804.68001  Eades, P.; Wormald, N.C., Edge crossings in drawings of bipartite graphs, () · Zbl 0804.68107  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  Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman New York · Zbl 0411.68039  Garey, M.R.; Johnson, D.S., Crossing number is NP-complete, SIAM J. algebraic discrete methods, 4, 312-316, (1983) · Zbl 0536.05016  Gschwind, D.J.; Murtagh, T.P., A recursive algorithm for drawing hierarchical directed graphs, ()  Karger, D.; Motwani, R.; Ramkumar, G.D.S., On approximating the longest path in a graph, (), 421-432 · Zbl 0876.68083  Kelly, D., A view to graph layout problems, ()  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  Makinen, E., Experiments in drawing 2-level hierarchical graphs, () · Zbl 0723.68083  Messinger, E., Automatic layout of large directed graphs, ()  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  Paulich, F.N.; Tichy, W.F., EDGE: an extendible directed graph editor, Software practice experience, 20, 63-88, (1990)  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)  Sechen, C., VLSI placement and global routing using simulated annealing, (1988), Kluwer Dordrecht  Sugiyama, K., A cognitive approach for graph drawing, Cybernet. systems, 18, 447-488, (1987)  Sugiyama, K.; Misue, K., Visualizing structural information: hierarchical drawing of a compound digraph, (), IIAS-SIS  Sugiyama, K.; Tagawa, S.; Toda, M., Methods for visual understanding of hierarchical system structures, IEEE trans. systems man cybernet, SMC-11, 109-125, (1981)  Ullman, J.D., Computational aspects of VLSI, (1984), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.