Geodesic
Extending Partial Orthogonal Drawings
Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 581-602.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2021_25_1_a26,
     author = {Patrizio Angelini and Ignaz Rutter and Sandhya T P},
     title = {Extending {Partial} {Orthogonal} {Drawings}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {581--602},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2021},
     doi = {10.7155/jgaa.00573},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00573/}
}
TY  - JOUR
AU  - Patrizio Angelini
AU  - Ignaz Rutter
AU  - Sandhya T P
TI  - Extending Partial Orthogonal Drawings
JO  - Journal of Graph Algorithms and Applications
PY  - 2021
SP  - 581
EP  - 602
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00573/
DO  - 10.7155/jgaa.00573
LA  - en
ID  - JGAA_2021_25_1_a26
ER  - 
%0 Journal Article
%A Patrizio Angelini
%A Ignaz Rutter
%A Sandhya T P
%T Extending Partial Orthogonal Drawings
%J Journal of Graph Algorithms and Applications
%D 2021
%P 581-602
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00573/
%R 10.7155/jgaa.00573
%G en
%F JGAA_2021_25_1_a26
Patrizio Angelini; Ignaz Rutter; Sandhya T P. Extending Partial Orthogonal Drawings. Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 581-602. doi : 10.7155/jgaa.00573. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00573/

Cité par Sources :