arXiv Open Access 2020

Extending Partial Orthogonal Drawings

Patrizio Angelini Ignaz Rutter Sandhya T P

Lihat Sumber

Abstrak

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

Topik & Kata Kunci

cs.DM cs.CG

Penulis (3)

Patrizio Angelini

Ignaz Rutter

Sandhya T P

Format Sitasi

APA MLA BibTeX

Angelini, P., Rutter, I., P, S.T. (2020). Extending Partial Orthogonal Drawings. https://arxiv.org/abs/2008.10280

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓