A direct linear-time planarity test for unflippable modules

DOI10.1080/00207168708803570MaRDI QIDQ3804209zbMATH OpenOpenAlexFDO

Authors Amihood Amir

Publication date 1987

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph planar embeddingintegrated circuit layoutmodulesplanar routingriver routingterminals

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Recommendations

• On the linearity of testing planarity of graphs
• Testing planarity of geometric automorphisms in linear time
• Testing Full Outer-2-planarity in Linear Time
• scientific article; zbMATH DE number 1377359
• A linear-time algorithm for testing outer-1-planarity
• A linear-time algorithm for testing outer-1-planarity
• A linear-time algorithm for testing full outer-2-planarity
• A new approach to the linearity of testing planarity of graphs
• On test modules for flat dimension
• Fully-dynamic planarity testing in polylogarithmic time

Cites work

• Computing an st-numbering
• Efficient Planarity Testing
• scientific article; zbMATH DE number 3315017 (Why is no real title available?)
• Optimal Placement for River Routing

This page was built for publication: A direct linear-time planarity test for unflippable modules

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