Hardness of approximate compaction for nonplanar orthogonal graph drawings

DOI10.1007/978-3-642-25878-7_35MaRDI QIDQ3223969zbMATH OpenOpenAlexFDO

Authors Michael J. Bannister, David Eppstein

Publication date 9 March 2012

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-25878-7_35

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Inapproximability of orthogonal compaction
• On the complexity of orthogonal compaction
• scientific article; zbMATH DE number 2080085
• scientific article; zbMATH DE number 2185601
• scientific article; zbMATH DE number 1342138

Cites work

• k-Degenerate Graphs
• Complexity of finding non-planar rectilinear drawings of graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On Rectilinear Drawing of Graphs
• On the complexity of orthogonal compaction
• The three-phase method: a unified approach to orthogonal graph drawing
• The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing
• Turn-regularity and optimal area drawings of orthogonal representations

Cited in

(5)

• scientific article; zbMATH DE number 2185601 (Why is no real title available?)
• Inapproximability of orthogonal compaction
• On the Hardness of Orthogonal-Order Preserving Graph Drawing
• On the complexity of orthogonal compaction
• Parameterized approaches to orthogonal compaction

This page was built for publication: Hardness of approximate compaction for nonplanar orthogonal graph drawings

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