Drawing HV-Restricted Planar Graphs
share
A strict orthogonal drawing of a graph G=(V, E) in R^2 is a drawing of G such that each vertex is mapped to a distinct point and each edge is mapped to a horizontal or vertical line segment. A graph G is HV-restricted if each of its edges is assigned a horizontal or vertical orientation. A strict orthogonal drawing of an HV-restricted graph G is good if it is planar and respects the edge orientations of G. In this paper, we give a polynomial-time algorithm to check whether a given HV-restricted plane graph (i.e., a planar graph with a fixed combinatorial embedding) admits a good orthogonal drawing preserving the input embedding, which settles an open question posed by Maňuch et al. (Graph Drawing 2010). We then examine HV-restricted planar graphs (i.e., when the embedding is not fixed), and give a complete characterization of the HV-restricted biconnected outerplanar graphs that admit good orthogonal drawings.
READ FULL TEXT