Drawing HV-Restricted Planar Graphs

DOI10.1007/978-3-642-54423-1_14MaRDI QIDQ5405036zbMATH OpenOpenAlexFDO

Authors Stephane Durocher, Stefan Felsner, Saeed Mehrabi, Debajyoti Mondal

Publication date 31 March 2014

Published in LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.06760

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: A strict orthogonal drawing of a graph $G=(V,E)$ in $mathbb{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 Mav{n}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.

Recommendations

• Strictly convex drawings of planar graphs
• Strictly convex drawings of planar graphs
• Curve-constrained drawings of planar graphs
• Convex drawings of hierarchical planar graphs and clustered planar graphs
• scientific article; zbMATH DE number 3959478
• Hypergraph planarity and the complexity of drawing venn diagrams
• Planarizing graphs and their drawings by vertex splitting
• Planar drawings of higher-genus graphs
• Planar drawings of higher-genus graphs
• Drawing partially embedded and simultaneously planar graphs

Cited in

(5)

• scientific article; zbMATH DE number 1262793 (Why is no real title available?)
• On the complexity of HV-rectilinear planarity testing
• Orthogonal planarity testing of bounded treewidth graphs
• HV-planarity: algorithms and complexity
• Sketched representations and orthogonal planarity of bounded treewidth graphs

This page was built for publication: Drawing HV-Restricted Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405036)