×

zbMATH — the first resource for mathematics

Compact grid representation of graphs. (English) Zbl 1374.68350
Márquez, Alberto (ed.) et al., Computational geometry. XIV Spanish meeting on computational geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of his 60th birthday, Alcalá de Henares, Spain, June 27–30, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 166-174 (2012).
Summary: A graph \(G\) is said to be grid locatable if it admits a representation such that vertices are mapped to grid points and edges to line segments that avoid grid points but the extremes. Additionally \(G\) is said to be properly embeddable in the grid if it is grid locatable and the segments representing edges do not cross each other. We study the area needed to obtain those representations for some graph families.
For the entire collection see [Zbl 1253.68016].
Reviewer: Reviewer (Berlin)
MSC:
68R10 Graph theory (including graph drawing) in computer science
05C62 Graph representations (geometric and intersection representations, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balko, M.: Grid Representations and the Chromatic Number. In: 28th European Workshop on Computational Geometry, pp. 45–48 (2012)
[2] Barrière, L., Huemer, C.: 4-Labelings and Grid Embeddings of Plane Quadrangulations. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 413–414. Springer, Heidelberg (2010) · Zbl 05702353 · doi:10.1007/978-3-642-11805-0_41
[3] Brooks, R.L.: On colouring the nodes of a network. Cambridge Philosophical Society, Math. Phys. Sci. 37, 194–197 (1941) · JFM 67.0733.02 · doi:10.1017/S030500410002168X
[4] Chrobak, M., Nakano, S.: Minimum width grid drawings of plane graphs. Computational Geometry 11(1), 29–54 (1998) · Zbl 0904.68177 · doi:10.1016/S0925-7721(98)00016-9
[5] Cornelsen, S., Schank, T., Wagner, D.: Drawing Graphs on Two and Three Lines. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 31–41. Springer, Heidelberg (2002) · Zbl 1037.68574 · doi:10.1007/3-540-36151-0_4
[6] Dolve, D., Leighton, F.T., Trickey, H.: Planar embedding of planar graphs. Advances in Computing Research. VLSI Theory, vol. 2. JAI Press, Inc., Greenwich (1984)
[7] Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990) · Zbl 0728.05016 · doi:10.1007/BF02122694
[8] Flores-Peñaloza, D., Santos, F., Zaragoza, F.J.: Encajes primitivos de gráficas aplanables. In: XXVII Coloquio Víctor Neumann (2012)
[9] Flores-Peñaloza, D., Zaragoza, F.J.: Every four-colorable graph is isomorphic to a subgraph of the visibility graph of the integer lattice. In: 21st Canadian Conference on Computational Geometry, CCCG 2009, pp. 91–94 (2009)
[10] Hardy, G.H., Wright, E.M.: An introduction to the theory of numbers. Oxford University Press (1979) · Zbl 0423.10001
[11] Kára, J., Pór, A., Wood, D.R.: On the chromatic number of the visibility graph of a set of points in the plane. Discrete and Computational Geometry 34(3), 497–506 (2005) · Zbl 1074.05036 · doi:10.1007/s00454-005-1177-z
[12] Por, A., Wood, D.R.: On visibility and blockers. J. Computational Geometry 1(1), 29–40 (2010) · Zbl 1408.52027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.