Embedding Four-Directional Paths on Convex Point Sets

Aichholzer, Oswin and Hackl, Thomas and Lutteropp, Sarah and Mchedlidze, Tamara and Vogtenhuber, Birgit (2014) Embedding Four-Directional Paths on Convex Point Sets. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 355-366 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_30).

Full text not available from this repository.


A directed path whose edges are assigned labels “up”, “down”, “right”, or “left” is called four-directional, and three-directional if at most three out of the four labels are used. A direction-consistent embedding of an n-vertex four-directional path P on a set S of n points in the plane is a straight-line drawing of P where each vertex of P is mapped to a distinct point of S and every edge points to the direction specified by its label. We study planar direction-consistent embeddings of three- and four-directional paths and provide a complete picture of the problem for convex point sets.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_30
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.560 Geometry
G Algorithms and Complexity > G.630 Labeling
P Styles > P.720 Straight-line
Z Theory > Z.750 Topology
ID Code:1446

Repository Staff Only: item control page


Aichholzer, O., Hackl, T., Lutteropp, S., Mchedlidze, T., Vogtenhuber, B.: Embedding four-directional paths on convex point sets. arXiv e-prints arXiv:1408.4933 [cs.CG] (2014)

Aichholzer, O., Krasser, H.: The point set order type data base: A collection of applications and results. In: 13th Annual Canadian Conference on Computational Geometry (CCCG 2001), pp. 17–20 (2001)

Aichholzer, O., Hackl, T., Huemer, C., Hurtado, F., Krasser, H., Vogtenhuber, B.: On the number of plane geometric graphs. Graphs and Comb. 23(1), 67–84 (2007)

Alspach, B., Rosenfeld, M.: Realization of certain generalized paths in tournaments. Discrete Math 34, 199–202 (1981)

Angelini, P., Frati, F., Geyer, M., Kaufmann, M., Mchedlidze, T., Symvonis, A.: Upward geometric graph embeddings into point sets. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 25–37. Springer, Heidelberg (2011)

Bannister, M.J., Cheng, Z., Devanny, W.E., Eppstein, D.: Superpatterns and universal point sets. J. Graph Alg. Appl. 18(2), 177–209 (2014)

Bannister, M.J., Devanny, W.E., Eppstein, D.: Small superpatterns for dominance drawing. CoRR abs/1310.3770 (2013)

Biedl, T., Vatshelle, M.: The point-set embeddability problem for plane graphs. In: 28th Annual Symposium on Computational Geometry (SoCG 2012), pp. 41–50. ACM (2012)

Binucci, C., Di Giacomo, E., Didimo, W., Estrella-Balderrama, A., Frati, F., Kobourov, S., Liotta, G.: Upward straight-line embeddings of directed graphs into point sets. Computat. Geom. Th. Appl. 43, 219–232 (2010)

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

Durocher, S., Mondal, D.: On the hardness of point-set embeddability. In: Rahman, M.S., Nakano, S.-I. (eds.) WALCOM 2012. LNCS, vol. 7157, pp. 148–159. Springer, Heidelberg (2012)

Forcade, R.: Parity of paths and circuits in tournaments. Discrete Math. 6(2), 115 (1973)

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

Kaufmann, M., Mchedlidze, T., Symvonis, A.: On upward point set embeddability. Comput. Geom. 46(6), 774–804 (2013)

Mchedlidze, T.: Upward planar embedding of an n-vertex oriented path on O(n2) points. Comp. Geom.: Theory and Appl. 47(3), 493–498 (2014)

Reid, K., Wormald, N.: Embedding oriented n-trees in tournaments. Studia Sci. Math. Hungarica 18, 377–387 (1983)

Rosenfeld, M.: Antidirected hamiltonian circuits in tournaments. Journal of Comb. Theory, Ser. B 16(3), 234–242 (1974)

Straight, J.: The existence of certain type of semi-walks in tournaments. Congr. Numer. 29, 901–908 (1980)

Thomason, A.: Paths and cycles in tournaments. Trans. of the American Math. Society 296(1), 167–180 (1986)

Zhang, C.Q.: Some results on tournaments. J. Qufu Teachers College (1), 51–53 (1985)