Extending Partial Orthogonal Drawings

2020/08/24 by Angelini, Patrizio, Rutter, Ignaz, P, Sandhya T · 1 citation
#05C10 #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2

paper · doi:10.48550/arxiv.2008.10280

Abstract

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⊆ 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.

Cited by

• Extending Biconnected Straight-Line Planar Drawings

Related

• Extending Orthogonal Planar Graph Drawings is Fixed-Parameter Tractable
• Extending orthogonal planar graph drawings is fixed-parameter tractable
• Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time
• Optimal Orthogonal Drawings in Linear Time
• On Smooth Orthogonal and Octilinear Drawings: Relations, Complexity and\n Kandinsky Drawings