Lower bounds for planar orthogonal drawings of graphs

DOI10.1016/0020-0190(91)90059-QMaRDI QIDQ1182115zbMATH OpenWikidataFDO

Authors Roberto Tamassia, Jeffrey Scott Vitter, Ioannis G. Tollis

Publication date 27 June 1992

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90059-Q

zbMATH Keywords

bendsorthogonal drawingsplanar embeddingVLSI layout

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• New Lower Bounds For Orthogonal Drawings
• Relating bends and size in orthogonal graph drawings
• scientific article; zbMATH DE number 2080105
• Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings
• scientific article; zbMATH DE number 1953108

Cites work

• Algorithms for drawing graphs: An annotated bibliography
• Amortized Computational Complexity
• scientific article; zbMATH DE number 65738 (Why is no real title available?)
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On minimal-node-cost planar embeddings

Cited in

(23)

• Drawing \(K_{2,n}\): A lower bound
• Advances in the theory and practice of graph drawing
• Algorithms for area-efficient orthogonal drawing
• A better heuristic for orthogonal graph drawings
• Bend-optimal orthogonal drawings of triconnected plane graphs
• Bend-minimum orthogonal drawings in quadratic time
• An efficient parallel algorithm for finding rectangular duals of plane triangular graphs
• Drawing planar graphs using the canonical ordering
• Orthogonal drawings of graphs for the automation of VLSI circuit design
• On embedding a graph in the grid with the maximum number of bends and other bad features
• Schnyder decompositions for regular plane graphs and application to drawing
• scientific article; zbMATH DE number 2084285 (Why is no real title available?)
• On the Hardness of Orthogonal-Order Preserving Graph Drawing
• New Lower Bounds For Orthogonal Drawings
• Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings
• scientific article; zbMATH DE number 2080105 (Why is no real title available?)
• Computing and Combinatorics
• Planar Lombardi Drawings for Subcubic Graphs
• Efficient Algorithms for Ortho-Radial Graph Drawing.
• L-shaped point set embeddings of high-degree plane graphs
• Planar Confluent Orthogonal Drawings of 4-Modal Digraphs
• Planar confluent orthogonal drawings of 4-modal digraphs
• A topology-shape-metrics framework for ortho-radial graph drawing

This page was built for publication: Lower bounds for planar orthogonal drawings of graphs

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