Orthogeodesic Point-Set Embedding of Trees

Di Giacomo, Emilio and Frati, Fabrizio and Fulek, Radoslav and Grilli, Luca and Krug, Marcus (2012) Orthogeodesic Point-Set Embedding of Trees. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 52-63 (Official URL: http://dx.doi.org/ 10.1007/978-3-642-25878-7_6).

Full text not available from this repository.

Abstract

Let S be a set of N grid points in the plane, and let G a graph with n vertices (n ≤ N ). An orthogeodesic point-set embedding of G on S is a drawing of G such that each vertex is drawn as a point of S and each edge is an orthogonal chain with bends on grid points whose length is equal to the Manhattan distance.We study the following problem. Given a family of trees F what is the minimum value f (n) such that every n-vertex tree in F admits an orthogeodesic point-set embedding on every grid-point set of size f (n)? We provide polynomial upper bounds on f (n) for both planar and non-planar orthogeodesic point-set embeddings as well as for the case when edges are required to be L-shaped chains.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_6
Classifications:G Algorithms and Complexity > G.490 Embeddings
M Methods > M.900 Tree
ID Code:1240

Repository Staff Only: item control page

References

Badent, M., Di Giacomo, E., Liotta, G.: Drawing colored graphs on colored points. Theoretical Computer Science 408(2-3), 129–142 (2008)

Bose, P.: On embedding an outer-planar graph on a point set. Computational Geometry: Theory and Applications 23, 303–312 (2002)

Bose, P., McAllister, M., Snoeyink, J.: Optimal algorithms to embed trees in a point set. Journal of Graph Algorithms and Applications 2(1), 1–15 (1997)

Brandenburg, F.J.: Drawing planar graphs on 8/9 n2 area. Electronic Notes in Discrete Mathematics 31, 37–40 (2008)

Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. Journal of Graph Algorithms and Applications 10(2), 353–366 (2006)

Di Giacomo, E., Grilli, L., Krug, M., Liotta, G., Rutter, I.: Hamiltonian Orthogeodesic Alternating Paths. In: Iliopoulos, C.S. (ed.) IWOCA 2011. LNCS, vol. 7056, pp. 170–181.Springer, Heidelberg (2011)

Di Giacomo, E., Liotta, G., Trotta, F.: Drawing colored graphs with constrained vertex positions and few bends per edge. Algorithmica 57, 796–818 (2010)

Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Mathematica 2,463–470 (1935)

Everett, H., Lazard, S., Liotta, G., Wismath, S.: Universal sets of n points for one-bend drawings of planar graphs with n vertices. Discrete and Computational Geometry 43, 272–288 (2010)

Fink, M., Haunert, J.-H., Mchedlidze, T., Spoerhase, J., Wolff, A.: Drawing graphs with vertices at specified positions and crossings at large angles. pre-print, arXiv:1107.4970v1 (July 2011)

Di Giacomo, E., Frati, F., Fulek, R., Grilli, L., Krug, M.: Orthogeodesic point-set embedding of trees. Technical Report 2011-24, Kalrsruhe Institute of Technology, KIT (2011)

Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified points. Amer. Math. Monthly 98(2), 165–166 (1991)

Katz, B., Krug, M., Rutter, I., Wolff, A.: Manhattan-Geodesic Embedding of Planar Graphs. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 207–218. Springer, Heidelberg (2010)

Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications 6(1), 115–129 (2002)

Kurowski, M.: A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs. Information Processing Letters 92(2), 95–98 (2004)