×

\(\mathsf{T}\)-shape visibility representations of 1-planar graphs. (English) Zbl 1381.05048

Summary: A shape visibility representation displays a graph so that each vertex is represented by an orthogonal polygon of a particular shape and for each edge there is a horizontal or vertical line of sight of width \(\varepsilon>0\) between the polygons assigned to its endvertices. Special shapes are rectangles, \(\mathsf{L}\), \(\mathsf{T}\), \(\mathsf{E}\), and \(\mathsf{H}\)-shapes, and caterpillars. A graph is 1-planar if there is a drawing in the plane such that each edge is crossed at most once and is IC-planar if in addition no two crossed edges share a vertex.
We show that every IC-planar graph has a flat rectangle visibility representation, in which each rectangle has height \(\epsilon\), and that every 1-planar graph has a \(\mathsf{T}\)-shape visibility representation. The representations use quadratic area and can be computed in linear time from a given embedding.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alam, M. J.; Brandenburg, F. J.; Kobourov, S. G., Straight-line drawings of 3-connected 1-planar graphs, (Wismath, S.; Wolff, A., GD 2013. GD 2013, Lect. Notes Comput. Sci., vol. 8242 (2013), Springer), 83-94 · Zbl 1406.68054
[2] Albertson, M., Chromatic number, independence ratio, and crossing number, Ars Math. Contemp., 1, 1, 1-6 (2008) · Zbl 1181.05032
[3] Andreae, T., Some results on visibility graphs, Discrete Appl. Math., 40, 1, 5-17 (1992) · Zbl 0781.05013
[4] Auer, C.; Brandenburg, F. J.; Gleißner, A.; Reislhuber, J., 1-planarity of graphs with a rotation system, J. Graph Algorithms Appl., 19, 1, 67-86 (2015) · Zbl 1307.05057
[5] Bachmaier, C.; Brandenburg, F. J.; Hanauer, K.; Neuwirth, D.; Reislhuber, J., NIC-planar graphs, Discrete Appl. Math., 232, 23-40 (2017) · Zbl 1372.05047
[6] Badent, M.; Brandes, U.; Cornelsen, S., More canonical ordering, J. Graph Algorithms Appl., 15, 1, 97-126 (2011) · Zbl 1217.05066
[7] Biedl, T. C., Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs, Discrete Comput. Geom., 45, 1, 141-160 (2011) · Zbl 1251.05111
[8] Biedl, T. C.; Liotta, G.; Montecchiani, F., On visibility representations of non-planar graphs, (Fekete, S. P.; Lubiw, A., SoCG 2016. SoCG 2016, LIPIcs, vol. 51 (2016), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), 19:1-19:16 · Zbl 1387.68241
[9] Bodendiek, R.; Schumacher, H.; Wagner, K., Bemerkungen zu einem Sechsfarbenproblem von G. Ringel, Abh. Math. Semin. Univ. Hamb., 53, 41-52 (1983) · Zbl 0495.05020
[10] Bodendiek, R.; Schumacher, H.; Wagner, K., Über 1-optimale Graphen, Math. Nachr., 117, 323-339 (1984) · Zbl 0558.05017
[11] Borodin, O. V., A new proof of the 6 color theorem, J. Graph Theory, 19, 4, 507-521 (1995) · Zbl 0826.05027
[12] Brandenburg, F. J., 1-visibility representation of 1-planar graphs, J. Graph Algorithms Appl., 18, 3, 421-438 (2014) · Zbl 1301.05238
[13] Brandenburg, F. J., On 4-map graphs and 1-planar graphs and their recognition problem (2015), CoRR
[14] Brandenburg, F. J., Recognizing optimal 1-planar graphs in linear time, Algorithmica (2016), published online October 2016
[15] Brandenburg, F. J.; Didimo, W.; Evans, W. S.; Kindermann, P.; Liotta, G.; Montecchiani, F., Recognizing and drawing IC-planar graphs, Theor. Comput. Sci., 636, 1-16 (2016) · Zbl 1342.68251
[16] Brandenburg, F. J.; Eppstein, D.; Gleißner, A.; Goodrich, M. T.; Hanauer, K.; Reislhuber, J., On the density of maximal 1-planar graphs, (van Kreveld, M.; Speckmann, B., GD 2012. GD 2012, Lect. Notes Comput. Sci., vol. 7704 (2013), Springer), 327-338 · Zbl 1377.68165
[17] Brandenburg, F. J.; Heinsohn, N.; Kaufmann, M.; Neuwirth, D., On bar \((1, j)\)-visibility graphs, (Rahman, M. S.; Tomita, E., WALCOM 2015. WALCOM 2015, Lect. Notes Comput. Sci., vol. 8973 (2015), Springer), 246-257, (extended abstract) · Zbl 1432.68342
[18] Chen, Z.; Grigni, M.; Papadimitriou, C. H., Recognizing hole-free 4-map graphs in cubic time, Algorithmica, 45, 2, 227-262 (2006) · Zbl 1095.68076
[19] de Fraysseix, H.; Pach, J.; Pollack, R., How to draw a planar graph on a grid, Combinatorica, 10, 41-51 (1990) · Zbl 0728.05016
[20] Dean, A. M.; Evans, W.; Gethner, E.; Laison, J. D.; Safari, M. A.; Trotter, W. T., Bar \(k\)-visibility graphs, J. Graph Algorithms Appl., 11, 1, 45-59 (2007) · Zbl 1161.68651
[21] Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, I. G., Graph Drawing: Algorithms for the Visualization of Graphs (1999), Prentice Hall · Zbl 1057.68653
[22] Di Battista, G.; Tamassia, R., On-line planarity testing, SIAM J. Comput., 25, 5, 956-997 (1996) · Zbl 0858.68063
[23] Di Giacomo, E.; Didimo, W.; Evans, W. S.; Liotta, G.; Meijer, H.; Montecchiani, F.; Wismath, S. K., Ortho-polygon visibility representations of embedded graphs, (Hu, Y.; Nöllenburg, M., GD 2016. GD 2016, Lect. Notes Comput. Sci., vol. 9801 (2016), Springer), 280-294 · Zbl 1390.68497
[24] Didimo, W.; Eades, P.; Liotta, G., Drawing graphs with right angle crossings, Theor. Comput. Sci., 412, 39, 5156-5166 (2011) · Zbl 1225.68134
[25] Duchet, P.; Hamidoune, Y. O.; Vergnas, M. L.; Meyniel, H., Representing a planar graph by vertical lines joining different levels, Discrete Math., 46, 3, 319-321 (1983) · Zbl 0516.05023
[26] Eades, P.; Liotta, G., Right angle crossing graphs and 1-planarity, Discrete Appl. Math., 161, 7-8, 961-969 (2013) · Zbl 1408.05042
[27] Evans, W. S.; Kaufmann, M.; Lenhart, W.; Mchedlidze, T.; Wismath, S. K., Bar 1-visibility graphs vs. other nearly planar graphs, J. Graph Algorithms Appl., 18, 5, 721-739 (2014) · Zbl 1305.05160
[28] Evans, W. S.; Liotta, G.; Montecchiani, F., Simultaneous visibility representations of plane st-graphs using L-shapes, (Mayr, E. W., WG 2016. WG 2016, Lect. Notes Comput. Sci., vol. 9224 (2016), Springer), 252-265 · Zbl 1417.05134
[29] Even, S.; Tarjan, R. E., Computing an st-numbering, Theor. Comput. Sci., 2, 3, 339-344 (1976) · Zbl 0341.68029
[30] Felsner, S.; Massow, M., Parameters of bar \(k\)-visibility graphs, J. Graph Algorithms Appl., 12, 1, 5-27 (2008) · Zbl 1161.68666
[31] Grigoriev, A.; Bodlaender, H. L., Algorithms for graphs embeddable with few crossings per edge, Algorithmica, 49, 1, 1-11 (2007) · Zbl 1131.68120
[32] Gutwenger, C.; Mutzel, P., A linear time implementation of SPQR-trees, (Marks, J., GD 2000. GD 2000, Lect. Notes Comput. Sci., vol. 1984 (2001), Springer), 77-90 · Zbl 1043.68621
[33] Harel, D.; Sardas, M., An algorithm for straight-line drawing of planar graphs, Algorithmica, 20, 119-135 (1998) · Zbl 0895.68105
[34] Hutchinson, J. P.; Shermer, T.; Vince, A., On representations of some thickness-two graphs, Comput. Geom., 13, 161-171 (1999) · Zbl 0953.68116
[35] Kant, G., Drawing planar graphs using the canonical ordering, Algorithmica, 16, 4-32 (1996) · Zbl 0851.68086
[36] Kant, G., A more compact visibility representation, Int. J. Comput. Geom. Appl., 7, 3, 197-210 (1997)
[37] Kobourov, S. G.; Liotta, G.; Montecchiani, F., An annotated bibliography on 1-planarity, Comput. Sci. Rev. (2017) · Zbl 1398.68402
[38] Korzhik, V. P.; Mohar, B., Minimal obstructions for 1-immersion and hardness of 1-planarity testing, J. Graph Theory, 72, 30-71 (2013) · Zbl 1259.05046
[39] Král, D.; Stacho, L., Coloring plane graphs with independent crossings, J. Graph Theory, 64, 3, 184-205 (2010) · Zbl 1208.05019
[40] Liotta, G.; Montecchiani, F., L-visibility drawings of IC-planar graphs, Inf. Process. Lett., 116, 3, 217-222 (2016) · Zbl 1328.68263
[41] Otten, R.; van Wijk, J. G., Graph representation in interactive layout design, (Proc. IEEE Int. Symp. on Circuits and Systems (1978)), 914-918
[42] Ringel, G., Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hamb., 29, 107-117 (1965) · Zbl 0132.20701
[43] Rosenstiehl, P.; Tarjan, R. E., Rectilinear planar layouts and bipolar orientations of planar graphs, Discrete Comput. Geom., 1, 343-353 (1986) · Zbl 0607.05027
[44] Schumacher, H., Zur Struktur 1-planarer Graphen, Math. Nachr., 125, 291-300 (1986) · Zbl 0594.05026
[45] Shermer, T. C., On rectangle visibility graphs. III. External visibility and complexity, (Fiala, F.; Kranakis, E.; Sack, J., 8th CCCG (1996), Carleton University Press), 234-239
[46] Suzuki, Y., Re-embeddings of maximum 1-planar graphs, SIAM J. Discrete Math., 24, 4, 1527-1540 (2010) · Zbl 1221.05099
[47] Tamassia, R.; Tollis, I. G., A unified approach a visibility representation of planar graphs, Discrete Comput. Geom., 1, 321-341 (1986) · Zbl 0607.05026
[48] Thomassen, C., Rectilinear drawings of graphs, J. Graph Theory, 12, 3, 335-341 (1988) · Zbl 0649.05051
[49] Wismath, S., Characterizing bar line-of-sight graphs, (Proc. 1st ACM Symp. Comput. Geom (1985), ACM Press), 147-152
[50] Zhang, X.; Liu, G., The structure of plane graphs with independent crossings and its application to coloring problems, Cent. Eur. J. Math., 11, 2, 308-321 (2013) · Zbl 1258.05028
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.