On the complexity of the maximum biplanar subgraph problem

DOI10.1016/S0020-0255(00)00048-7zbMath0980.68058MaRDI QIDQ5946290

Chang Wu Yu

Publication date: 14 October 2001

Published in: Information Sciences (Search for Journal in Brave)

zbMATH Keywords

bipartite graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient parallel algorithms for doubly convex-bipartite graphs
• Solving the shortest-paths problem on bipartite permutation graphs efficiently
• Interval graphs and maps of DNA
• Bipartite permutation graphs
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Edge crossings in drawings of bipartite graphs
• Drawing graphs in two layers
• An O(logn) parallel connectivity algorithm
• On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem
• Maximum matching in a convex bipartite graph

This page was built for publication: On the complexity of the maximum biplanar subgraph problem