Algorithms for Drawing Media

Eppstein, David (2004) Algorithms for Drawing Media. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 173-183 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_19).

Full text not available from this repository.

Abstract

We describe algorithms for drawing media, systems of states, tokens and actions that have state transition graphs in the form of partial cubes. Our algorithms are based on two principles: embedding the state transition graph in a low-dimensional integer lattice and projecting the lattice onto the plane, or drawing the medium as a planar graph with centrally symmetric faces.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_19
Classifications:P Styles > P.780 Symmetric
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.540 Planar
ID Code:584

Repository Staff Only: item control page

References

F. Aurenhammer and J. Hagauer. Recognizing binary Hamming graphs in 0(n^2 log n) time. Mathematical Systems Theory 28:387-395, 1995.

S. Bhatt and S. Cosmodakis. The complexity of minimizing wire lengths in VLSI layouts. Inform. Proc. Lett. 25:263-267, 1987.

T. M. Chan. On levels in arrangements of curves. Discrete & Comput. Geom. 29(3):375_393, April 2003.

G. Di Battista and R. Tamassia. Incremental planarity testing. Proc. 30th IEEE Symp. Foundations of Computer Science (FOCS 1989), pp. 436-441, 1989.

D. Eppstein. Layered graph drawing. http://www.ics.uci.edu/~eppstein/junkyard/thickness/.

D. Eppstein. The lattice dimension of a graph. To appear in Eur. J. Combinatorics, arXiv:cs.DS/0402028.

D. Eppstein and J.-C. Falmagne. Algorithms for media. ACM Computing Research Repository, June 2002, arXiv:cs.DS/0206033.

J. C. Falmagne and S. Ovchinnikov. Media theory. Discrete Applied Mathematics 121(1-3):103-118, September 2002.

H. de Fraysseix and P. Ossona de Mendez. Stretching of Joedan arc contact systems. Proc. 11th Int. Symp. Graph Drawing (GD 2003), pp. 71-85. Springer-Verlag, Lecture Notes in Computer Science 2912, 2003.

J. E. Goodman and R. Pollack. Allowable sequences and order types in discrete and computational geometry. New Trends in Discrete and Computational Geometry, chapter V, pp. 103-134. Springer-Verlag, Algorithms and Combinatorics 10, 1993.

W. Imrich and S. Klavzar. On the complexity of recognizing Hamming graphs and related classes of graphs. Eur. J. Combinatorics 17:209-221, 1996.

W. Imrich and S. Klavzar. Product Graphs. John Wiley & Sons, 2000.

P. Mutzel. The SPQR-tree data structure in graph drawing. Proc. 30th Int. Coll. Automata, Languages and Computation (ICALP 2003), pp. 34-46. Springer-Verlag, Lecture Notes in Computer Science 2719, June 2003.

S. Ovchinnikov. The lattice dimension of a tree. arXiv.org, February 2004, arXiv:math. CO/0402246.

P. Winkler. Isometric embeddings in products of complete graphs. Discrete Applied Mathematics 7:221-225, 1984.

T.-T. Wong, W.-S. Luk, and P.-A. Heng. Sampling with Hammersley and Halton points. J. Graphics Tools 2(2):9-24, 1997.