On the complexity of orthogonal compaction

DOI10.1016/S0925-7721(01)00010-4zbMath0990.68169OpenAlexW1549747920MaRDI QIDQ5943322

Maurizio Patrignani

Publication date: 9 September 2001

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0925-7721(01)00010-4

zbMATH Keywords

orthogonal grid drawingsSAT reduction

Mathematics Subject Classification ID

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

Related Items

Efficient cell-based migration of VLSI layout, Optimal three-dimensional orthogonal graph drawing in the general position model., Minimum rectilinear polygons for given angle sequences, Drawing database schemas, On Turn-Regular Orthogonal Representations, Upward planar drawings with two slopes, Hardness of Approximate Compaction for Nonplanar Orthogonal Graph Drawings, Minimum Rectilinear Polygons for Given Angle Sequences, Parameterized approaches to orthogonal compaction, On embedding a graph in the grid with the maximum number of bends and other bad features, Orthogonal drawings of graphs with vertex and edge labels, On Turn-Regular Orthogonal Representations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Embedding rectilinear graphs in linear time
• Parallel concepts in graph theory
• Turn-regularity and optimal area drawings of orthogonal representations
• Rectilinear Graphs and Their Embeddings
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Computing orthogonal drawings with the minimum number of bends