Drawing graphs in two layers.

*(English)*Zbl 0819.68086Summary: 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 |

##### Keywords:

bipartite graph
PDF
BibTeX
XML
Cite

\textit{P. Eades} and \textit{S. Whitesides}, Theor. Comput. Sci. 131, No. 2, 361--374 (1994; Zbl 0819.68086)

Full Text:
DOI

##### References:

[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, (), 13-17 |

[6] | Eades, P.; Mckay, B.D.; Wormald, N.C., On an edge crossing problem, (), 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, () · Zbl 0804.68001 |

[9] | Eades, P.; Wormald, N.C., Edge crossings in drawings of bipartite graphs, () · 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 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, () |

[14] | Karger, D.; Motwani, R.; Ramkumar, G.D.S., On approximating the longest path in a graph, (), 421-432 · Zbl 0876.68083 |

[15] | Kelly, D., A view to graph layout problems, () |

[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, () · Zbl 0723.68083 |

[18] | Messinger, E., Automatic layout of large directed graphs, () |

[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 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, (), 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 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.