Inapproximability of orthogonal compaction

DOI10.7155/JGAA.00263MaRDI QIDQ3144115zbMATH OpenOpenAlexFDO

Authors Michael J. Bannister, David Eppstein, Joseph A. Simons

Publication date 7 December 2012

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1108.4705

zbMATH Keywords

compact orthogonal graph drawingsfixed-parameter-tractable algorithm

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We show that several problems of compacting orthogonal graph drawings to use the minimum number of rows, area, length of longest edge or total edge length cannot be approximated better than within a polynomial factor of optimal in polynomial time unless P = NP. We also provide a fixed-parameter-tractable algorithm for testing whether a drawing can be compacted to a small number of rows.

Recommendations

• Hardness of approximate compaction for nonplanar orthogonal graph drawings
• On the complexity of orthogonal compaction
• scientific article; zbMATH DE number 1974108
• scientific article; zbMATH DE number 2185601
• scientific article; zbMATH DE number 1342138

Cited in

(9)

• scientific article; zbMATH DE number 2185601 (Why is no real title available?)
• Hardness of approximate compaction for nonplanar orthogonal graph drawings
• On the approximability of orthogonal order preserving layout adjustment
• On the complexity of orthogonal compaction
• Parameterized approaches to orthogonal compaction
• Recognition and proper coloring of unit segment intersection graphs
• Parameterized approaches to orthogonal compaction
• Ortho-radial drawing in near-linear time
• Minimum rectilinear polygons for given angle sequences

This page was built for publication: Inapproximability of orthogonal compaction

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