Bijective comparison of optimal planarity algorithms

DOI10.1080/03081089508818361MaRDI QIDQ4838131zbMATH OpenOpenAlexWikidataFDO

Authors Laura A. Bloom

Publication date 20 November 1995

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/03081089508818361

zbMATH Keywords

graph embeddingHopcroft-Tarian algorithmplanarity testing

Mathematics Subject Classification ID

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

Recommendations

• A near-optimal planarization algorithm
• scientific article; zbMATH DE number 3965443
• An efficient parallel algorithm for planarity
• scientific article; zbMATH DE number 1696626
• A polynomial-time bicriteria approximation scheme for planar bisection
• Optimal k-level planarization and crossing minimization
• A GENERAL APPROXIMATION ALGORITHM FOR PLANAR MAPS WITH APPLICATIONS
• scientific article; zbMATH DE number 1305475

Cites work

• Depth-First Search and Linear Graph Algorithms
• Efficient Planarity Testing
• Embedding Graphs in the Plane—Algorithmic Aspects
• scientific article; zbMATH DE number 1792682 (Why is no real title available?)
• Ranking and unranking planar embeddings
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The two basic linear time Planarity algorithms: Are they the same?

Cited in

(1)

• The two basic linear time Planarity algorithms: Are they the same?

This page was built for publication: Bijective comparison of optimal planarity algorithms

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