Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00573
Extending Partial Orthogonal Drawings
Vol. 25, no. 1, pp. 581602, 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 NPcomplete to find an
extension that minimizes the number of bends or has a fixed number
of bends per edge.
This work is licensed under the terms of the CCBY license.

Submitted: April 2021.
Reviewed: June 2021.
Revised: August 2021.
Accepted: September 2021.
Final: October 2021.
Published: October 2021.
Communicated by
Giuseppe Liotta

Journal Supporters
