Back to Search
Start Over
Windrose Planarity: Embedding Graphs with Direction-Constrained Edges
- Source :
- Scopus-Elsevier
- Publication Year :
- 2015
-
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 $u \in UR(v)$ is above and to the right of $v$, (ii) each neighbor $u \in UL(v)$ is above and to the left of $v$, (iii) each neighbor $u \in DL(v)$ is below and to the left of $v$, (iv) each neighbor $u \in DR(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 $3n \times 3n$ grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.<br />Appeared in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)
- Subjects :
- Computational Geometry (cs.CG)
FOS: Computer and information sciences
0102 computer and information sciences
02 engineering and technology
Computer Science::Computational Geometry
01 natural sciences
Combinatorics
Planar graph
symbols.namesake
Mathematics (miscellaneous)
Graph drawing
0202 electrical engineering, electronic engineering, information engineering
Mathematics (all)
Partition (number theory)
Mathematics
Combinatorial embedding
Planarity testing
Vertex (geometry)
Exponential function
Algorithm
Monotone polygon
010201 computation theory & mathematics
symbols
Embedding
Computer Science - Computational Geometry
020201 artificial intelligence & image processing
Upward planarity
Software
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Scopus-Elsevier
- Accession number :
- edsair.doi.dedup.....d7661b0c877807b78890f908c1a5431c