On the complexity of the maximum biplanar subgraph problem

DOI10.1016/S0020-0255(00)00048-7MaRDI QIDQ5946290zbMATH OpenFDO

Authors C. W. Yu

Publication date 14 October 2001

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0020-0255(00)00048-7

zbMATH Keywords

bipartite graph

Mathematics Subject Classification ID

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

Recommendations

• Drawing graphs in two layers
• On bipartite drawings and the linear arrangement problem
• On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem
• On the complexity of the k-chain subgraph cover problem
• Biplanar graphs: A survey

Cites work

• An O(logn) parallel connectivity algorithm
• Bipartite permutation graphs
• Drawing graphs in two layers
• Edge crossings in drawings of bipartite graphs
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Efficient parallel algorithms for doubly convex-bipartite graphs
• Graph theory with applications
• scientific article; zbMATH DE number 3963860 (Why is no real title available?)
• scientific article; zbMATH DE number 4063153 (Why is no real title available?)
• scientific article; zbMATH DE number 43583 (Why is no real title available?)
• scientific article; zbMATH DE number 49142 (Why is no real title available?)
• Interval graphs and maps of DNA
• Maximum matching in a convex bipartite graph
• On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem
• Solving the shortest-paths problem on bipartite permutation graphs efficiently
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(4)

• Drawing graphs in two layers
• Biplanar graphs: A survey
• On the computational complexity of edge concentration
• A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5946290)