Planar embedding: linear-time algorithms for vertex placement and edge orderings

DOI10.1109/31.1746MaRDI QIDQ3801097zbMATH OpenOpenAlexFDO

Authors R. Jayakumar, Krishnaiyan Thulasiraman, M. N. S. Swamy

Publication date 1988

Published in IEEE Transactions on Circuits and Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/31.1746

zbMATH Keywords

PQ-treesplanar embeddingplanarity testinghorvert representationintersection-free drawing

Mathematics Subject Classification ID

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

Recommendations

• A linear algorithm for embedding planar graphs using PQ-trees
• scientific article; zbMATH DE number 1305401
• A linear-time algorithm for drawing a planar graph on a grid
• Planarity algorithms via PQ-trees (extended abstract)
• scientific article; zbMATH DE number 434911

Cited in

(12)

• Constructing compact rectilinear planar layouts using canonical representation of planar graphs
• Establishing order in planar subdivisions
• Dynamic maintenance of planar digraphs, with applications
• A linear algorithm for embedding planar graphs using PQ-trees
• Characterizing planar tanglegram layouts and applications to edge insertion problems
• O(n2) algorithms for graph planarization
• Drawing planar graphs using the canonical ordering
• Topological recognition of polyhedral objects from multiple views
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• Level Planar Embedding in Linear Time
• scientific article; zbMATH DE number 434911 (Why is no real title available?)
• Orthogonal drawings of graphs for the automation of VLSI circuit design

This page was built for publication: Planar embedding: linear-time algorithms for vertex placement and edge orderings

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