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

DOI10.1109/31.1746zbMATH Open0654.68089OpenAlexW2154845271MaRDI QIDQ3801097FDOQ3801097

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

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

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)

Cited In (12)

• 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
• Title not available (Why is that?)
• Orthogonal drawings of graphs for the automation of VLSI circuit design
• Constructing compact rectilinear planar layouts using canonical representation of planar graphs

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)