Small Point Sets for Simply-Nested Planar Graphs

Angelini, Patrizio and Di Battista, Giuseppe and Kaufmann, Michael and Mchedlidze, Tamara and Roselli, Vincenzo and Squarcella, Claudio (2012) Small Point Sets for Simply-Nested Planar Graphs. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 75-85 (Official URL: http://dx.doi.org/ 10.1007/978-3-642-25878-7_8).

Full text not available from this repository.

Abstract

A point set P ⊆ R2 is universal for a class G if every graph of G has a planar straight-line embedding into P. We prove that there exists a log n O(n( log log n )2 ) size universal point set for the class of simply-nested n-vertex planar graphs. This is a step towards a full answer for the well-known open problem on the size of the smallest universal point sets for planar graphs.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_8
Classifications:G Algorithms and Complexity > G.490 Embeddings
M Methods > M.600 Planar
ID Code:1242

Repository Staff Only: item control page

References

Open problem garden, http://garden.irmacs.sfu.ca

Bachmaier, C., Brandenburg, F.J., Forster, M.: Radial level planarity testing and embedding in linear time. Journal of Graph Algorithms and Applications 9 (2005)

Baker, B.S.: Approximation algorithms for np-complete problems on planar graphs. J.ACM 41, 153–180 (1994)

Bose, P.: On embedding an outer-planar graph in a point set. Computat. Geom. Th. Appl. 23(3), 303–312 (2002)

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)

Chrobak, M., Karloff, H.: A lower bound on the size of universal sets for planar graphs 20, 83–86 (1989)

Chrobak, M., Nakano, S.: Minimum-width grid drawings of plane graphs. Computational Geometry 11(1), 29–54 (1998)

Cimikowski, R.J.: Finding hamiltonian cycles in certain planar graphs. Information Processing Letters 35(5), 249–254 (1990)

Demaine, E.D., Mitchell, J.S.B., O’Rourke, J.: The open problems project, http://maven.smith.edu/ ̃orourke/TOPP/

Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10, 41–51 (1990)

Gritzmann, P., Pach, B.M.J., Pollack, R.: Embedding a planar triangulation with vertices at specified positions. Amer. Math. Mont. 98, 165–166 (1991)

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)

Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990, pp. 138–148 (1990)

Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38, 36–67 (1989)