Extending Partial Orthogonal Drawings
Patrizio Angelini, Ignaz Rutter, T. P. Sandhya · Lecture notes in computer science · 2020
We study the planar orthogonal drawing style within the framework of partial representation extension. Let $$(G,H,\varGamma _H)$$ be a partial orthogonal drawing, i.e., G is a graph, $$H\subseteq G$$ is a subgraph and $$\varGamma _H$$ is a planar orthogonal drawing of H. We show that the existence of an orthogonal drawing $$\varGamma _G$$ of G that extends $$\varGamma _H$$ can be tested in linear time. If such a drawing exists, then there also is one that uses O(|V(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.