Windrose planarity: embedding graphs with direction-constrained edges

DOI10.1137/1.9781611974331.CH70MaRDI QIDQ4575650zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(4)

• Windrose planarity: embedding graphs with direction-constrained edges
• A Census of Plane Graphs with Polyline Edges
• On the area-universality of triangulations
• 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)