Windrose planarity: embedding graphs with direction-constrained edges

DOI10.1137/1.9781611974331.CH70zbMATH Open1410.68274arXiv1510.02659OpenAlexW4244967770MaRDI QIDQ4575650FDOQ4575650

Authors: Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Valentino Di Donato, Philipp Kindermann, Günter Rote, Ignaz Rutter 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: Given a planar graph $G$ and a partition of the neighbors of each vertex $v$ in four sets $UR(v)$, $UL(v)$, $DL(v)$, and $DR(v)$, the problem Windrose Planarity asks to decide whether $G$ admits a windrose-planar drawing, that is, a planar drawing in which (i) each neighbor $uinUR(v)$ is above and to the right of $v$, (ii) each neighbor $uinUL(v)$ is above and to the left of $v$, (iii) each neighbor $uinDL(v)$ is below and to the left of $v$, (iv) each neighbor $uinDR(v)$ is below and to the right of $v$, and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a given combinatorial embedding. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph with $n$ vertices that has a windrose-planar drawing, we can construct one with at most one bend per edge and with at most $2n-5$ bends in total, which lies on the $3nimes3n$ grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.

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

Recommendations

• Windrose planarity: embedding graphs with direction-constrained edges
• Drawing planar graphs on a curve.
• scientific article; zbMATH DE number 1830747
• Drawing planar graphs using the canonical ordering
• Curve-constrained drawings of planar graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cited In (4)

• On the area-universality of triangulations
• Windrose planarity: embedding graphs with direction-constrained edges
• A Census of Plane Graphs with Polyline Edges
• Bounded Embeddings of Graphs in the Plane

This page was built for publication: Windrose planarity: embedding graphs with direction-constrained edges

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