Extending Partial Orthogonal Drawings

Abstract

We study the planar orthogonal drawing style within the framework of partial representation extension. Let $(G,H,\hat{I}{“}_H)$ be a partial orthogonal drawing, i.e., G is a graph, $H\subseteq G$ is a subgraph and $\hat{I}{“}_H$ is a planar orthogonal drawing of H. We show that the existence of an orthogonal drawing $\hat{I}{“}_G$ of $G$ that extends $\hat{I}{“}_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.

Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)