تقرير
Extending Partial Orthogonal Drawings
| العنوان: | Extending Partial Orthogonal Drawings |
|---|---|
| المؤلفون: | Angelini, Patrizio, Rutter, Ignaz, P, Sandhya T |
| سنة النشر: | 2020 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Discrete Mathematics, Computer Science - Computational Geometry, 05C10, G.2.2 |
| الوصف: | 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 and ${\Gamma}_H$ is a planar orthogonal drawing of 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 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. Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020) |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2008.10280 |
| رقم الأكسشن: | edsarx.2008.10280 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |