×

Drawings of planar graphs with few slopes and segments. (English) Zbl 1129.65010

Some results on planar graphs are proved in this paper. One is a characterization of plane drawings with a segment between every pair of vertices, which are the ones with the least number of segments. The article is mainly devoted to obtain lower and upper bounds on the minimum number of segments and slopes in (plane) drawings of graphs. The results are summarized in a table for nine graph families. The main result for \(3\)-connected plane graphs states that all of them with \(n\) vertices have a plane drawing with at most \(5n/2-3\) segments and at most \(2n-10\) slopes.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
05C10 Planar graphs; geometric and topological aspects of graph theory
68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Barát, J.; Matoušek, J.; Wood, D. R., Bounded-degree graphs have arbitrarily large geometric thickness, Electron. J. Combin., 13, 1, R3 (2006) · Zbl 1080.05063
[2] Bhasker, J.; Sahni, S., A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph, Networks, 17, 3, 307-317 (1987) · Zbl 0672.05025
[3] Bhasker, J.; Sahni, S., A linear algorithm to find a rectangular dual of a planar triangulated graph, Algorithmica, 3, 2, 247-278 (1988) · Zbl 0635.68074
[4] Czyzowicz, J.; Kranakis, E.; Urrutia, J., A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments, Inform. Process. Lett., 66, 3, 125-126 (1998) · Zbl 0925.68337
[5] de Castro, N.; Cobos, F. J.; Dana, J. C.; Márquez, A.; Noy, M., Triangle-free planar graphs as segment intersection graphs, J. Graph Algorithms Appl., 6, 1, 7-26 (2002) · Zbl 0999.68163
[6] de Fraysseix, H.; Ossona de Mendez, P., Contact and intersection representations, (Pach, J., Proc. 12th International Symp. on Graph Drawing (GD ’04). Proc. 12th International Symp. on Graph Drawing (GD ’04), Lecture Notes in Comput. Sci., vol. 3383 (2004), Springer: Springer Berlin), 217-227 · Zbl 1111.68603
[7] de Fraysseix, H.; Ossona de Mendez, P.; Pach, J., A left-first search algorithm for planar graphs, Discrete Comput. Geom., 13, 3-4, 459-468 (1995) · Zbl 0826.68090
[8] de Fraysseix, H.; Pach, J.; Pollack, R., How to draw a planar graph on a grid, Combinatorica, 10, 1, 41-51 (1990) · Zbl 0728.05016
[9] Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71-76 (1961) · Zbl 0098.14703
[10] Dujmović, V.; Suderman, M.; Wood, D. R., Graph drawings with few slopes, Comput. Geom., 38, 3, 181-193 (2007), this issue · Zbl 1128.65020
[11] Dujmović, V.; Wood, D. R., Graph treewidth and geometric thickness parameters, (Healy, P.; Nikolov, N. S., Proc. 13th International Symp. on Graph Drawing (GD ’05). Proc. 13th International Symp. on Graph Drawing (GD ’05), Lecture Notes in Comput. Sci., vol. 3843 (2006), Springer: Springer Berlin), 129-140 · Zbl 1171.05371
[12] Fáry, I., On straight line representation of planar graphs, Acta Univ. Szeged. Sect. Sci. Math., 11, 229-233 (1948) · Zbl 0030.17902
[13] Garg, A.; Tamassia, R., On the computational complexity of upward and rectilinear planarity testing, SIAM J. Comput., 31, 2, 601-625 (2001) · Zbl 0996.68130
[14] Ben-Arroyo Hartman, I.; Newman, I.; Ziv, R., On grid intersection graphs, Discrete Math., 87, 1, 41-52 (1991) · Zbl 0739.05081
[15] Kant, G., Hexagonal grid drawings, (Mayr, E. W., Proc. 18th International Workshop in Graph-Theoretic Concepts in Computer Science (WG ’92). Proc. 18th International Workshop in Graph-Theoretic Concepts in Computer Science (WG ’92), Lecture Notes in Comput. Sci., vol. 657 (1993), Springer: Springer Berlin), 263-276, Also see Tech. Rep. RUU-CS-92-06, Universiteit Utrecht, Netherlands, 1992 · Zbl 0925.05056
[16] Kant, G., Drawing planar graphs using the canonical ordering, Algorithmica, 16, 1, 4-32 (1996) · Zbl 0851.68086
[17] Ossona de Mendez, P.; de Fraysseix, H., Intersection graphs of Jordan arcs, (Contemporary Trends in Discrete Mathematics. Contemporary Trends in Discrete Mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 49 (1999), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 11-28 · Zbl 0934.05047
[18] Pach, J.; Pálvölgyi, D., Bounded-degree graphs can have arbitrarily large slope numbers, Electron. J. Combin., 13, 1, N1 (2006) · Zbl 1080.05064
[19] Rahman, Md. S.; Nakano, S.-I.; Nishizeki, T., Rectangular grid drawings of plane graphs, Comput. Geom., 10, 3, 203-220 (1998) · Zbl 0901.68202
[20] Rahman, Md. S.; Nakano, S.-I.; Nishizeki, T., A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs, J. Graph Algorithms Appl., 3, 31-62 (1999) · Zbl 0946.05078
[21] Rahman, Md. S.; Nakano, S.-I.; Nishizeki, T., Box-rectangular drawings of plane graphs, J. Algorithms, 37, 2, 363-398 (2000) · Zbl 0964.68103
[22] Rahman, Md. S.; Nakano, S.-I.; Nishizeki, T., Rectangular drawings of plane graphs without designated corners, Comput. Geom., 21, 3, 121-138 (2002) · Zbl 0993.68131
[23] Rahman, Md. S.; Nishizeki, T.; Ghosh, S., Rectangular drawings of planar graphs, J. Algorithms, 50, 62-78 (2004) · Zbl 1075.68065
[24] Thomassen, C., Plane representations of graphs, (Progress in Graph Theory (1984), Academic Press: Academic Press Toronto), 43-69 · Zbl 0554.05021
[25] Ungar, P., On diagrams representing maps, J. London Math. Soc., 28, 336-342 (1953) · Zbl 0050.18001
[26] Wagner, K., Bemerkung zum Vierfarbenproblem, Jber. Deutsch. Math.-Verein., 46, 26-32 (1936) · Zbl 0014.18102
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.