EPrints .org
Home || About || Browse || Search || Register || User Area || Help

Algorithms for Drawing Media

Eppstein, David (2004) Algorithms for Drawing Media. In Pach, János, Eds. Proceedings Graph Drawing, pages pp. 173-183, New York.

Full text of this item is not available.

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.

Display Formats:BibTex
EPrint Type:Conference Paper
Subjects:P Styles > P.780 Symmetric
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.540 Planar
ID Code:584
Deposited By:Selbach, Anna
Deposited On:19 July 2005
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=3383&spage=173

References

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

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

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

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

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

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

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

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

9. 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.

10. 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.

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

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

13. 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.

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

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

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


Site Administrator: gdea@informatik.uni-koeln.de