Planar embedding of trees on point sets without the general position assumption

The problem of point-set embedding of a planar graph $G$ on a point set $P$ in the plane is defined as finding a straight-line planar drawing of $G$ such that the nodes of $G$ are mapped one to one on the points of $P$. Previous works in this area mostly assume that the points of $P$ are in general position, i.e. $P$ does not contain any three collinear points. However, in most of the real applications we cannot assume the general position assumption. In this paper, we show that deciding the point-set embeddability of trees without the general position assumption is NP-complete. Then we introduce an algorithm for point-set embedding of $n$-node binary trees with at most $\frac{n}{3}$ total bends on any point set. We also give some results when the problem is limited to degree-constrained trees and point sets having constant number of collinear points.

Anahtar Kelimeler:

Point-set embedding, tree embedding, general position assumption, graph drawing, minimum bend embedding

Planar embedding of trees on point sets without the general position assumption

Keywords:

Point-set embedding, tree embedding, general position assumption, graph drawing, minimum bend embedding,

PDF

___

partition P\{p} to point sets P1, P2, and P3of sizes respectively|T1|, |T2|, and |T3| with disjoint convex hulls such that each partition contains at least one point visible from p . We embed r on p and for each subtree Ti, 1≤ i ≤ 3, we recursively embed T
Note that, when|Ti| = 3, 4, 5, we should embed rion the suitable convex hull point of Pias described before.2 ion Pisuch that riis embedded on a convex hull point of Pivisible from p . The example point set shown in Figure
We have shown that embeddability of trees on point sets is NP-complete. Our results also show that the embedding is always possible when the problem is limited to ternary trees and point sets without four collinear points, and this result cannot be strengthened any further. We also introduced an algorithm for embedding n -node binary trees on any set of n points with at most
n 3 total bends. As future works, we suggest research on the problems of point-set embeddability of degree constrained trees and embeddability of planar graphs on point sets that have few collinear points.
Badent M, Di Giacomo E, Liotta G. Drawing colored graphs on colored points. Theor Comput Sci 2008; 408: 129–142.
Bose P. On embedding an outer-planar graph in a point set. Comp Geom-Theor Appl 2002; 23: 303–312.
Bose P, McAllister M, Snoeyink J. Optimal algorithms to embed trees in a point set. J Graph Algorithms Appl 1997; 2: 1–15.
Brass P, Cenek E, Duncan CA, Efrat A, Erten C, Ismailescu DP, Kobourov SG, Lubiw A, Mitchell JSB. On simultaneous planar graph embeddings. Comp Geom-Theor Appl 2007; 36: 117–130.
Cabello S. Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J Graph Algorithms Appl 2006; 10: 353–366.
Casta˜neda N, Urrutia J. Straight line embeddings of planar graphs on point sets. In: Fiala F, Kranakis E, Sack JR, editors. Proceedings of the 8th Canadian Conference on Computational Geometry; 12–15 August 1996; Ottawa, Ontario, Canada. Ottawa: Carleton University Press, 1996, pp. 312–318.
Di Giacomo E, Liotta G, Trotta F. On embedding a graph on two sets of points. Int J Found Comput S 2006; 17: 1071–1094.
Erten C, Kobourov SG. Simultaneous embedding of planar graphs with few bends. In: Pach J, editor. 12th International Symposium on Graph Drawing; 29 September–2 October 2004; New York, NY, USA. Berlin: Springer, 2005, pp. 195–205.
Estrella-Balderrama A, Gassner E, J¨unger M, Percan M, Schaefer M, Schulz M. Simultaneous geometric graph embeddings. In: Hong SH, Nishizeki T, Quan W,editors. 15th International Symposium on Graph drawing; 24–26 September 2007; Sydney, Australia. Berlin: Springer, 2008, pp. 280–290.
Gassner E, J¨unger M, Percan M, Schaefer M, Schulz M. Simultaneous graph embeddings with fixed edges. In: Fomin, FV, editor. 32nd Workshop on Graph-Theoretic Concepts in Computer Science, 22–24 June 2006; Bergen, Norway. Berlin: Springer, 2006, pp. 325–335.
Ikebe Y, Perles MA, Tamura A, Tokunaga S. The rooted tree embedding problem into points in the plane. Discrete Comput Geom 1994; 11: 51–63.
Kaufmann M, Wiese R. Embedding vertices at points: few bends suﬃce for planar graphs. J Graph Algorithms Appl 2002; 6: 115–129.
Pach J, Wenger R. Embedding planar graphs at fixed vertex locations. Graph Combinator 2001; 17: 717–728.
Pack J, Torocsik J. Layout of rooted trees. In: Trotter WT, editor. Planar Graphs, volume 9 of DIMACS Series. USA: American Mathematical Society, 1993, pp. 131–137.