Journal of Graph Algorithms and Applications

Extending Partial Orthogonal Drawings

Patrizio Angelini, Ignaz Rutter, and Sandhya T P

Vol. 25, no. 1, pp. 581-602, 2021. Regular paper.

Abstract We study the planar orthogonal drawing style within the framework of partial representation extension. Let $(G,H,\Gamma_H)$ be a partial orthogonal drawing, i.e., $G$ is a graph, $H\subseteq G$ is a subgraph, $\Gamma_H$ is a planar orthogonal drawing of $H$, and $|\Gamma_H|$ is the number of vertices and bends in~$\Gamma_H$. We show that the existence of an orthogonal drawing~$\Gamma_G$ of $G$ that extends $\Gamma_H$ can be tested in linear time. If such a drawing exists, then there is also one that uses $O(|\Gamma_H|)$ bends per edge. On the other hand, we show that it is NP-complete to find an extension that minimizes the number of bends or has a fixed number of bends per edge.