129.94.177.188: /* Ideals with traces */

2013-10-03T05:26:50Z

Ideals with traces

New page

[[File:Upward planar drawing.svg|thumb|240px|An upward planar drawing]]
[[File:Not upward planar.svg|thumb|This planar DAG has no upward drawing, because its source and sink cannot both be in the same face]]
In [[graph drawing]], an '''upward planar drawing''' of a [[directed acyclic graph]] is an [[Graph embedding|embedding]] of the graph into the [[Euclidean plane]], in which the edges are represented as [[planar graph|non-crossing]] [[Monotonic function|monotonic upwards]] curves. That is, the curve representing each edge should have the property that every horizontal line intersects it in at most one point, and no two edges may intersect except at a shared endpoint.<ref>{{harvtxt|Garg|Tamassia|1995}}; {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}.</ref> In this sense, it is the ideal case for [[layered graph drawing]], a style of graph drawing in which edges are monotonic curves that may cross, but in which crossings are to be minimized.

==Characterizations==
A directed acyclic graph must be [[planar graph|planar]] in order to have an upward planar drawing, but not every planar acyclic graph has such a drawing. Among the planar directed acyclic graphs with a single source (vertex with no incoming edges) and sink (vertex with no outgoing edges), the graphs with upward planar drawings are the [[st-planar graph|''st''-planar graphs]], planar graphs in which the source and sink both belong to the same face of at least one of the planar embeddings of the graph. More generally, a graph ''G'' has an upward planar drawing if and only if it is directed and acyclic, and is a subgraph of an ''st''-planar graph on the same vertex set.<ref>{{harvtxt|Garg|Tamassia|1995}}, pp. 111–112; {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, 6.1 "Inclusion in a Planar ''st''-Graph", pp. 172–179; {{harvtxt|Di Battista|Tamassia|1988}}; {{harvtxt|Kelly|1987}}.</ref>

In an upward embedding, the sets of incoming and outgoing edges incident to each vertex are contiguous in the [[cyclic order]]ing of the edges at the vertex. A planar embedding of a given directed acyclic graph is said to be ''bimodal'' when it has this property. Additionally, the angle between two consecutive edges with the same orientation at a given vertex may be labeled as ''small'' if it is less than π, or ''large'' if it is greater than π. Each source or sink must have exactly one large angle, and each vertex that is neither a source nor a sink must have none. Additionally, each internal face of the drawing must have two more small angles than large ones, and the external face must have two more large angles than small ones. A ''consistent assignment'' is a labeling of the angles that satisfies these properties; every upward embedding has a consistent assignment. Conversely, every directed acyclic graph that has a bimodal planar embedding with a consistent assignment has an upward planar drawing, that can be constructed from it in linear time.<ref>{{harvtxt|Garg|Tamassia|1995}}, pp. 112–115; {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, 6.2 "Angles in Upward Drawings", pp. 180–188; {{harvtxt|Bertolazzi|Di Battista|1991}}; {{harvtxt|Bertolazzi|Di Battista|Liotta|Mannino|1994}}.</ref>

Another characterization is possible for graphs with a single source. In this case an upward planar embedding must have the source on the outer face, and every undirected cycle of the graph must have at least one vertex at which both cycle edges are incoming (for instance, the vertex with the highest placement in the drawing). Conversely, if an embedding has both of these properties, then it is equivalent to an upward embedding.<ref>{{harvtxt|Garg|Tamassia|1995}}, p. 115; {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, 6.7.2 "Forbidden Cycles for Single-Source Digraphs", pp. 209–210; {{harvtxt|Thomassen|1989}}.</ref>

==Computational complexity==
Several special cases of upward planarity testing are known to be possible in [[polynomial time]]:
*Testing whether a graph is ''st''-planar may be accomplished in [[linear time]] by adding an edge from ''s'' to ''t'' and testing whether the remaining graph is planar. Along the same lines, it is possible to construct an upward planar drawing (when it exists) of a directed acyclic graph with a single source and sink, in linear time.<ref>{{harvtxt|Garg|Tamassia|1995}}, p. 119; {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, p. 179.</ref>
*Testing whether a directed graph with a fixed planar embedding can be drawn upward planar, with an embedding consistent with the given one, can be accomplished by checking that the embedding is bipolar and modeling the consistent assignment problem as a [[Flow network|network flow]] problem. The running time is linear in the size of the input graph, and polynomial in its number of sources and sinks.<ref>{{harvtxt|Garg|Tamassia|1995}}, pp. 119–121; {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, 6.3 "Upward Planarity Testing of Embedded Digraphs", pp. 188–192; {{harvtxt|Bertolazzi|Di Battista|1991}}; {{harvtxt|Bertolazzi|Di Battista|Liotta|Mannino|1994}}; {{harvtxt|Abbasi|Healy|Rextin|2010}}.</ref>
*Because oriented [[polyhedral graph]]s have a unique planar embedding, the existence of an upward planar drawing for these graphs may be tested in polynomial time.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, pp. 191–192; {{harvtxt|Bertolazzi|Di Battista|1991}}; {{harvtxt|Bertolazzi|Di Battista|Liotta|Mannino|1994}}.</ref>
*Testing whether an [[outerplanar graph|outerplanar]] directed acyclic graph has an upward planar drawing is also polynomial.<ref>{{harvtxt|Garg|Tamassia|1995}}, pp. 125–126; {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, 6.7.1 "Outerplanar Digraph", p. 209; {{harvtxt|Papakostas|1995}}.</ref>
*Every [[series-parallel graph]], oriented consistently with the series-parallel structure, is upward planar. An upward planar drawing can be constructed directly from the series-parallel decomposition of the graph.<ref name="special">{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, 6.7.4 "Some Classes of Upward Planar Digraphs", p. 212.</ref> More generally, arbitrary [[Orientation (graph theory)|orientations]] of undirected series-parallel graphs may be tested for upward planarity in polynomial time.<ref>{{harvtxt|Didimo|Giordano|Liotta|2009}}.</ref>
*Every [[Polytree|oriented tree]] is upward planar.<ref name="special"/>
*Every [[bipartite graph|bipartite]] planar graph, with its edges oriented consistently from one side of the bipartition to the other, is upward planar<ref name="special"/><ref>{{harvtxt|Di Battista|Liu|Rival|1990}}.</ref>
*A more complicated polynomial time algorithm is known for testing upward planarity of graphs that have a single source, but multiple sinks, or vice versa.<ref>{{harvtxt|Garg|Tamassia|1995}}, pp. 122–125; {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, 6.5 "Optimal Upward Planarity Testing of Single-Source Digraphs", pp. 195–200; {{harvtxt|Hutton|Lubiw|1996}}; {{harvtxt|Bertolazzi|Di Battista|Mannino|Tamassia|1998}}.</ref>
*Testing upward planarity can be performed in polynomial time when there are a constant number of triconnected components and cut vertices, and is [[parameterized complexity|fixed-parameter tractable]] in these two numbers.<ref>{{harvtxt|Chan|2004}}; {{harvtxt|Healy|Lynch|2006}}.</ref> It is also fixed-parameter tractable in the [[cyclomatic number]] of the input graph.<ref>{{harvtxt|Healy|Lynch|2006}}.</ref>
*If the ''y''-coordinates of all vertices are fixed, then a choice of ''x''-coordinates that makes the drawing upward planar can be found in polynomial time.<ref>{{harvtxt|Jünger|Leipert|1999}}.</ref>
However, it is [[NP-complete]] to determine whether a planar directed acyclic graph with multiple sources and sinks has an upward planar drawing.<ref>{{harvtxt|Garg|Tamassia|1995}}, pp. 126–132; {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, 6.6 "Upward Planarity Testing is NP-complete", pp. 201–209; {{harvtxt|Garg|Tamassia|2001}}.</ref>

==Straight-line drawing and area requirements==
[[Fáry's theorem]] states that every planar graph has a drawing in which its edges are represented by straight line segments, and the same is true of upward planar drawing: every upward planar graph has a straight upward planar drawing.<ref name="fary">{{harvtxt|Di Battista|Frati|2012}}; {{harvtxt|Di Battista|Tamassia|Tollis|1992}}.</ref>
A straight-line upward drawing of a [[transitive reduction|transitively reduced]] ''st''-planar graph may be obtained by the technique of [[dominance drawing]], with all vertices having integer coordinates within an ''n'' × ''n'' grid.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, 4.7 "Dominance Drawings", pp. 112–127; {{harvtxt|Di Battista|Tamassia|Tollis|1992}}.</ref> However, certain other upward planar graphs may require exponential area in all of their straight-line upward planar drawings.<ref name="fary"/> If a choice of embedding is fixed, even oriented series parallel graphs and oriented trees may require exponential area.<ref>{{harvtxt|Di Battista|Frati|2012}}; {{harvtxt|Bertolazzi|Cohen|Di Battista|Tamassia|1994}}; {{harvtxt|Frati|2008}}.</ref>

==Hasse diagrams==
Upward planar drawings are particularly important for [[Hasse diagram]]s of [[partially ordered set]]s, as these diagrams are typically required to be drawn upwardly. In graph-theoretic terms, these correspond to the [[transitive reduction|transitively reduced]] directed acyclic graphs; such a graph can be formed from the covering relation of a partial order, and the partial order itself forms the [[reachability]] relation in the graph. If a partially ordered set has one minimal element, has one maximal element, and has an upward planar drawing, then it must necessarily form a [[lattice (order)|lattice]], a set in which every pair of elements has a unique greatest lower bound and a unique least upper bound.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, 6.7.3 "Forbidden Structures for Lattices", pp. 210–212; {{harvtxt|Platt|1976}}.</ref> The Hasse diagram of a lattice is planar if and only if its [[order dimension]] is at most two.<ref>{{harvtxt|Garg|Tamassia|1995}}, pp. 118; {{harvtxt|Baker|Fishburn|Roberts|1972}}.</ref> However, some partial orders of dimension two and with one minimal and maximal element do not have an upward planar drawing (take the order defined by the transitive closure of <math>a < b, a < c, b < d, b < e, c < d, c < e, d < f, e < f</math>).

==References==
;Footnotes
{{reflist|30em}}

;Surveys and textbooks
{{refbegin|30em}}
*{{citation
| last1 = Di Battista | first1 = Giuseppe
| last2 = Eades | first2 = Peter | author2-link = Peter Eades
| last3 = Tamassia | first3 = Roberto | author3-link = Roberto Tamassia
| last4 = Tollis | first4 = Ioannis G.
| contribution = Flow and Upward Planarity
| isbn = 978-0-13-301615-4
| pages = 171–213
| publisher = [[Prentice Hall]]
| title = Graph Drawing: Algorithms for the Visualization of Graphs
| year = 1998}}.
*{{citation
| last1 = Di Battista | first1 = Giuseppe
| last2 = Frati | first2 = Fabrizio
| contribution = Drawing trees, outerplanar graphs, series-parallel graphs, and planar graphs in small area
| doi = 10.1007/978-1-4614-0110-0_9
| isbn = 9781461401100
| pages = 121–165
| publisher = Springer
| series = Algorithms and combinatorics
| title = Thirty Essays on Geometric Graph Theory
| volume = 29
| year = 2012}}. Section 5, "Upward Drawings", pp. 149–151.
*{{citation
| last1 = Garg | first1 = Ashim
| last2 = Tamassia | first2 = Roberto
| doi = 10.1007/BF01108622
| issue = 2
| journal = [[Order (journal)|Order]]
| mr = 1354797
| pages = 109–133
| title = Upward planarity testing
| volume = 12
| year = 1995}}.
{{refend}}

;Research articles
{{refbegin|30em}}
*{{citation
| last1 = Abbasi | first1 = Sarmad
| last2 = Healy | first2 = Patrick
| last3 = Rextin | first3 = Aimal
| doi = 10.1016/j.ipl.2010.02.004
| issue = 7
| journal = Information Processing Letters
| mr = 2642837
| pages = 274–278
| title = Improving the running time of embedded upward planarity testing
| volume = 110
| year = 2010}}.
*{{citation
| last1 = Baker | first1 = K. A.
| last2 = Fishburn | first2 = P. C.
| last3 = Roberts | first3 = F. S.
| doi = 10.1002/net.3230020103
| issue = 1
| journal = Networks
| pages = 11–28
| title = Partial orders of dimension 2
| volume = 2
| year = 1972}}.
*{{citation
| last1 = Bertolazzi | first1 = Paola
| last2 = Cohen | first2 = Robert F.
| last3 = Di Battista | first3 = Giuseppe
| last4 = Tamassia | first4 = Roberto | author4-link = Roberto Tamassia
| last5 = Tollis | first5 = Ioannis G.
| doi = 10.1142/S0218195994000215
| issue = 4
| journal = International Journal of Computational Geometry & Applications
| mr = 1310911
| pages = 385–402
| title = How to draw a series-parallel digraph
| volume = 4
| year = 1994}}.
*{{citation
| last1 = Bertolazzi | first1 = Paola
| last2 = Di Battista | first2 = Giuseppe
| contribution = On upward drawing testing of triconnected digraphs
| doi = 10.1145/109648.109679
| isbn = 0-89791-426-0
| location = New York, NY, USA
| pages = 272–280
| publisher = ACM
| title = Proceedings of the Seventh Annual Symposium on Computational Geometry (SCG '91, North Conway, New Hampshire, USA)
| year = 1991}}.
*{{citation
| last1 = Bertolazzi | first1 = P.
| last2 = Di Battista | first2 = G.
| last3 = Liotta | first3 = G.
| last4 = Mannino | first4 = C.
| doi = 10.1007/BF01188716
| issue = 6
| journal = [[Algorithmica]]
| mr = 1297810
| pages = 476–497
| title = Upward drawings of triconnected digraphs
| volume = 12
| year = 1994}}.
*{{citation
| last1 = Bertolazzi | first1 = Paola
| last2 = Di Battista | first2 = Giuseppe
| last3 = Mannino | first3 = Carlo
| last4 = Tamassia | first4 = Roberto | author4-link = Roberto Tamassia
| doi = 10.1137/S0097539794279626
| issue = 1
| journal = [[SIAM Journal on Computing]]
| mr = 1614821
| pages = 132–169
| title = Optimal upward planarity testing of single-source digraphs
| volume = 27
| year = 1998}}.
*{{citation
| last = Chan | first = Hubert
| contribution = A parameterized algorithm for upward planarity testing
| doi = 10.1007/978-3-540-30140-0_16
| pages = 157–168
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = [[European Symposium on Algorithms|Proc. 12th European Symposium on Algorithms (ESA '04)]]
| volume = 3221
| year = 2004}}.
*{{citation
| last1 = Di Battista | first1 = Giuseppe
| last2 = Liu | first2 = Wei-Ping
| last3 = Rival | first3 = Ivan | author3-link = Ivan Rival
| doi = 10.1016/0020-0190(90)90045-Y
| issue = 6
| journal = [[Information Processing Letters]]
| mr = 1084490
| pages = 317–322
| title = Bipartite graphs, upward drawings, and planarity
| volume = 36
| year = 1990}}.
*{{citation
| last1 = Di Battista | first1 = Giuseppe
| last2 = Tamassia | first2 = Roberto | author2-link = Roberto Tamassia
| doi = 10.1016/0304-3975(88)90123-5
| issue = 2-3
| journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
| mr = 980241
| pages = 175–198
| title = Algorithms for plane representations of acyclic digraphs
| volume = 61
| year = 1988}}.
*{{citation
| last1 = Di Battista | first1 = Giuseppe
| last2 = Tamassia | first2 = Roberto | author2-link = Roberto Tamassia
| last3 = Tollis | first3 = Ioannis G.
| doi = 10.1007/BF02187850
| issue = 4
| journal = [[Discrete and Computational Geometry]]
| mr = 1148953
| pages = 381–401
| title = Area requirement and symmetry display of planar upward drawings
| volume = 7
| year = 1992}}.
*{{citation
| last1 = Didimo | first1 = Walter
| last2 = Giordano | first2 = Francesco
| last3 = Liotta | first3 = Giuseppe
| doi = 10.1137/070696854
| issue = 4
| journal = [[SIAM Journal on Discrete Mathematics]]
| mr = 2594962
| pages = 1842–1899
| title = Upward spirality and upward planarity testing
| volume = 23
| year = 2009}}.
*{{citation
| last = Frati | first = Fabrizio
| doi = 10.1142/S021819590800260X
| issue = 3
| journal = International Journal of Computational Geometry & Applications
| mr = 2424444
| pages = 251–271
| title = On minimum area planar upward drawings of directed trees and other families of directed acyclic graphs
| volume = 18
| year = 2008}}.
*{{citation
| last1 = Garg | first1 = Ashim
| last2 = Tamassia | first2 = Roberto | author2-link = Roberto Tamassia
| doi = 10.1137/S0097539794277123
| issue = 2
| journal = [[SIAM Journal on Computing]]
| mr = 1861292
| pages = 601–625
| title = On the computational complexity of upward and rectilinear planarity testing
| volume = 31
| year = 2001}}.
*{{citation
| last1 = Healy | first1 = Patrick
| last2 = Lynch | first2 = Karol
| doi = 10.1142/S0129054106004285
| issue = 5
| journal = International Journal of Foundations of Computer Science
| pages = 1095–1114
| title = Two fixed-parameter tractable algorithms for testing upward planarity
| volume = 17
| year = 2006}}.
*{{citation
| last1 = Hutton | first1 = Michael D.
| last2 = Lubiw | first2 = Anna | author2-link = Anna Lubiw
| doi = 10.1137/S0097539792235906
| issue = 2
| journal = [[SIAM Journal on Computing]]
| mr = 1379303
| pages = 291–311
| title = Upward planar drawing of single-source acyclic digraphs
| volume = 25
| year = 1996}}. First presented at the 2nd ACM-SIAM Symposium on Discrete Algorithms, 1991.
*{{citation
| last1 = Jünger | first1 = Michael
| last2 = Leipert | first2 = Sebastian
| contribution = Level planar embedding in linear time
| doi = 10.1007/3-540-46648-7_7
| isbn = 978-3-540-66904-3
| pages = 72–81
| series = Lecture Notes in Computer Science
| title = [[International Symposium on Graph Drawing|Graph Drawing (Proc. GD '99)]]
| volume = 1731
| year = 1999}}.
*{{citation
| last = Kelly | first = David
| doi = 10.1016/0012-365X(87)90008-2
| issue = 2-3
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
| mr = 885497
| pages = 197–216
| title = Fundamentals of planar ordered sets
| volume = 63
| year = 1987}}.
*{{citation
| last = Papakostas | first = Achilleas
| contribution = Upward planarity testing of outerplanar dags (extended abstract)
| doi = 10.1007/3-540-58950-3_385
| location = Berlin
| mr = 1337518
| pages = 298–306
| publisher = Springer
| series = Lecture Notes in Computer Science
| title = Graph Drawing: DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings
| volume = 894
| year = 1995}}.
*{{citation
| last = Platt | first = C. R.
| doi = 10.1016/0095-8956(76)90024-1
| issue = 1
| journal = [[Journal of Combinatorial Theory]] | series = Ser. B
| pages = 30--39
| title = Planar lattices and planar graphs
| volume = 21
| year = 1976}}.
*{{citation
| last = Thomassen | first = Carsten | authorlink = Carsten Thomassen
| doi = 10.1007/BF00353654
| issue = 4
| journal = [[Order (journal)|Order]]
| mr = 1010384
| pages = 349–361
| title = Planar acyclic oriented graphs
| volume = 5
| year = 1989}}.
{{refend}}

[[Category:Planar graphs]]

Singular trace - Revision history

129.94.177.188: /* Ideals with traces */