Isometric Diamond Subgraphs

Eppstein, David (2009) Isometric Diamond Subgraphs. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 384-395 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_37).

Full text not available from this repository.

Abstract

We test in polynomial time whether a graph embeds in a distance-preserving way into the hexagonal tiling, the three-dimensional diamond structure, or analogous higher-dimensional structures.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_37
Classifications:G Algorithms and Complexity > G.490 Embeddings
P Styles > P.720 Straight-line
P Styles > P.060 3D
ID Code:926

Repository Staff Only: item control page

References

Balaban, A.T.: Graphs of multiple 1, 2-shifts in carbonium ions and related systems. Rev. Roum. Chim. 11, 1205 (1966)

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

Dilworth, R.P.: A decomposition theorem for partially ordered sets. Annals of Mathematics 51, 161–166 (1950)

Djokovic, D.Z.: Distance preserving subgraphs of hypercubes. J. Combinatorial Theory, Ser. B 14, 263–267 (1973)

Eades, P., Whitesides, S.: The logic engine and the realization problem for nearest neighbor graphs. Theoretical Computer Science 169(1), 23–37 (1996)

Eppstein, D.: Algorithms for drawing media. In: Pach, J. (ed.) Proc. 12th Int. Symp. Graph Drawing (GD 2004).LNCS, vol.3383 pp. 173–183. Springer, Heidelberg (2005)

Eppstein, D.: The lattice dimension of a graph. Eur. J. Combinatorics 26(5), 585–592 (July 2005), URL http://dx.doi.org/10.1016/j.ejc.2004.05.001

Eppstein, D.: Cubic partial cubes from simplicial arrangements. Electronic J. Combinatorics 13(1), R79 (2006)

Eppstein, D.: Recognizing partial cubes in quadratic time. In: Proc. 19th Symp. Discrete Algorithms. pp. 1258–1266. ACM and SIAM (2008)

Eppstein, D.: The topology of bendless three-dimensional orthogonal graph drawing. In: Proc. 16th Int. Symp. Graph Drawing (2008)

Eppstein, D., Falmagne, J.C., Ovchinnikov, S.: Media Theory: Applied Interdisciplinary Mathematics. Springer, Heidelberg (2008)

Felsner, S., Raghavan, V., Spinrad, J.: Recognition algorithms for orders of small width and graphs of small Dilworth number. Order 20(4), 351–364 (2003)

Mislow, K.: Role of pseudorotation in the stereochemistry of nucleophilic displacement reactions. Acc. Chem. Res. 3(10), 321–331 (1970)

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