Information Technology Reference
In-Depth Information
interior visibilities
2
5
5
5
7
2
7
7
2
9
9
9
9
3
4
4
3
5
2
4
8
6
5
7
3
0
0
8
0
8
2
5
7
1
6
6
1
1
6
7
2
4
4
4
3
2
4
5
3
9
9
5
7
9
6
6
3
0
9
0
2
8
0
5
7
8
8
6
1
1
6
1
7
2
4
4
4
3
2
4
6
5
3
5
7
3
6
2
6
6
9
5
7
1
1
8
7
9
9
0
9
1
0
8
2
0
8
Fig. 3.
A planar graph with two faces, each of which can be flat-folded to give three
different patterns of vertical visibility (or “touching”) within it. These patterns can be
combined independently, giving nine flat-foldings of the whole graph.
It is also NP-hard to draw a plane graph with specified angles [16]. If both edge
lengths and angles are specified then the drawing is uniquely determined and
easy to construct, except in situations like ours where coincident edges give rise
to ambiguities.
There are a number of results for special cases that have a similar flavor to
ours, in that the whole plane graph can be realized if and only if each face can.
We now describe some of these special cases, most of which arise as the prelude
to finding an appropriate angle assignment.
Upward Planarity.
A directed acyclic graph (DAG) is
upward planar
[17] if it
has a planar drawing in which each edge is drawn as an increasing
y
-monotone
curve. Recognizing upward planar graphs is NP-hard [18] but Bertolazzi et al. [7]
gave a polynomial time algorithm for the special case of a plane graph whose
cyclic order of edges around each vertex is prescribed. The main issue in their
solution is to distinguish “small” versus “large” angles; if an upward planar
drawing is flattened onto a vertical line, then its small and large angles corre-
spond to our valley and mountain folds. The angle assignment is forced except at
