Embeddability Problems for Upward Planar Digraphs

Giordano, Francesco and Liotta, Giuseppe and Whitesides, Sue H. (2009) Embeddability Problems for Upward Planar Digraphs. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 242-253 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_23).

Full text not available from this repository.

Abstract

We study two embedding problems for upward planar digraphs. Both problems arise in the context of drawing sequences of upward planar digraphs having the same set of vertices, where the location of each vertex is to remain the same for all the drawings of the graphs. We develop a method, based on the notion of book embedding, that gives characterization results for embeddability as well as testing and drawing algorithms.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_23
Classifications:P Styles > P.840 Upward
G Algorithms and Complexity > G.490 Embeddings
ID Code:910

Repository Staff Only: item control page

References

Badent, M., Di Giacomo, E., Liotta, G.: Drawing colored graphs on colored points. In: WADS 2007. LNCS, vol. 4619, pp. 102–113 Springer, Heidelberg (2007)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.: Graph Drawing. Prentice Hall, Englewood Cliffs (1999)

Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theoretical Computer Science 61(2-3), 175–198 (1988)

Enomoto, H., Miyauchi, M.: Embedding graphs into a three page book with O(M log N ) crossings of edges over the spine. SIAM J. of Discrete Math. 12(3), 337–341 (1999)

Frati, F., Kaufmann, M., Kobourov, S.: Constrained simultaneous and near-simultaneous embeddings. In: GD 2007. LNCS, vol. 4875, pp. 268–279 (2007)

Giordano, F., Liotta, G., Mchedlidze, T., Symvonis, A.: Computing upward topological book embeddings of upward planar digraphs. In: ISAAC 2007. LNCS, vol. 4835, pp. 172–183 (2007)

Giordano, F., Liotta, G., Whitesides, S.: Drawing a sequence of upward planar digraphs: Characterization results and testing algorithms. Tech. rep., Universita degli Studi di Perugia (2008), RT-008-01

Goodman, J.,Pollack, R.: On the combinatorial classification of nondegenerate configurations in the plane. J. of Combinatorial Theory, Ser. A 29(2), 220–235 (1980)

Halton, J.H.: On the thickness of graphs of given degree. Inform. Sciences 54, 219–238 (1991)

Jünger, M., Leipert, S.: Level planar embedding in linear time. J. of Graph Algorithms and Applications 6(1), 67–113 (2002)

Jünger, M., Leipert, S., Mutzel, P.: Level planarity testing in linear time. In: GD 1998. LNCS, vol. 1547, pp. 224–237 (1998)

Kaufmann, M., Wagner, D.: Ed., Drawing Graphs, LNCS, vol. 2025. Springer-Verlag (2001)

Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs and Combin. 17(4), 717–728 (2001)