Octilinear graph drawings are a standard paradigm extending the orthogonal graph drawing style by two additional slopes ( \(\pm 1\) ). We are interested in two constrained drawing problems where the input specifies a so-called representation, that is: a planar embedding; the angles occurring between adjacent edges; the bends along each edge. In Orthogonal Realizability one is asked to compute any orthogonal drawing satisfying the constraints, while in Orthogonal Compaction the goal is to find such a drawing using minimum area. While Orthogonal Realizability can be solved in linear time, Orthogonal Compaction is NP-hard even if the graph is a cycle. In contrast, already Octilinear Realizability is known to be NP-hard. In this paper we investigate the Octilinear Realizability and Octilinear Compaction problems. We prove that Octilinear Realizability remains NP-hard if at most one face is not convex or if each interior face has at most 8 reflex corners. We also strengthen the hardness proof of Octilinear Compaction, showing that Octilinear Compaction does not admit a PTAS even if the representation has no reflex corner except at most 4 incident to the external face. On the positive side, we prove that when the input graph is biconnected Octilinear Realizability is FPT in the number of reflex corners and for Octilinear Compaction we describe an XP algorithm on the number of edges represented with a \(\pm 1\) slope segment (i.e., the diagonals), again when the representation has no reflex corner except at most 4 incident to the external face.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Compaction and Realizability of Almost Convex Octilinear Representations

  • Henry Foerster,
  • Giacomo Ortali,
  • Lena Schlipf

摘要

Octilinear graph drawings are a standard paradigm extending the orthogonal graph drawing style by two additional slopes ( \(\pm 1\) ). We are interested in two constrained drawing problems where the input specifies a so-called representation, that is: a planar embedding; the angles occurring between adjacent edges; the bends along each edge. In Orthogonal Realizability one is asked to compute any orthogonal drawing satisfying the constraints, while in Orthogonal Compaction the goal is to find such a drawing using minimum area. While Orthogonal Realizability can be solved in linear time, Orthogonal Compaction is NP-hard even if the graph is a cycle. In contrast, already Octilinear Realizability is known to be NP-hard. In this paper we investigate the Octilinear Realizability and Octilinear Compaction problems. We prove that Octilinear Realizability remains NP-hard if at most one face is not convex or if each interior face has at most 8 reflex corners. We also strengthen the hardness proof of Octilinear Compaction, showing that Octilinear Compaction does not admit a PTAS even if the representation has no reflex corner except at most 4 incident to the external face. On the positive side, we prove that when the input graph is biconnected Octilinear Realizability is FPT in the number of reflex corners and for Octilinear Compaction we describe an XP algorithm on the number of edges represented with a \(\pm 1\) slope segment (i.e., the diagonals), again when the representation has no reflex corner except at most 4 incident to the external face.